在前面 LZ 詳細(xì)介紹了 HashMap 、HashTable 、TreeMap 的實(shí)現(xiàn)方法,從數(shù)據(jù)結(jié)構(gòu)、實(shí)現(xiàn)原理、源碼分析三個(gè)方面進(jìn)行闡述,對(duì)這個(gè)三個(gè)類應(yīng)該有了比較清晰的了解,下面 LZ 就 Map 做一個(gè)簡(jiǎn)單的總結(jié)。
推薦閱讀:
首先先看 Map 的結(jié)構(gòu)示意圖
http://wiki.jikexueyuan.com/project/java-enhancement/images/33-1.png" alt="fig.1" />
Map:“鍵值”對(duì)映射的抽象接口。該映射不包括重復(fù)的鍵,一個(gè)鍵對(duì)應(yīng)一個(gè)值。
SortedMap:有序的鍵值對(duì)接口,繼承 Map 接口。
NavigableMap:繼承 SortedMap,具有了針對(duì)給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法的接口。
AbstractMap:實(shí)現(xiàn)了 Map 中的絕大部分函數(shù)接口。它減少了“Map 的實(shí)現(xiàn)類”的重復(fù)編碼。
Dictionary:任何可將鍵映射到相應(yīng)值的類的抽象父類。目前被Map接口取代。
TreeMap:有序散列表,實(shí)現(xiàn) SortedMap 接口,底層通過紅黑樹實(shí)現(xiàn)。
HashMap:是基于“拉鏈法”實(shí)現(xiàn)的散列表。底層采用“數(shù)組+鏈表”實(shí)現(xiàn)。
WeakHashMap:基于“拉鏈法”實(shí)現(xiàn)的散列表。
HashTable:基于“拉鏈法”實(shí)現(xiàn)的散列表。
總結(jié)如下:
http://wiki.jikexueyuan.com/project/java-enhancement/images/33-2.png" alt="fig.2" />
他們之間的區(qū)別:
http://wiki.jikexueyuan.com/project/java-enhancement/images/33-3.png" alt="fig.3" />
幾乎所有通用 Map 都使用哈希映射技術(shù)。對(duì)于我們程序員來(lái)說我們必須要對(duì)其有所了解。
哈希映射技術(shù)是一種就元素映射到數(shù)組的非常簡(jiǎn)單的技術(shù)。由于哈希映射采用的是數(shù)組結(jié)果,那么必然存在一中用于確定任意鍵訪問數(shù)組的索引機(jī)制,該機(jī)制能夠提供一個(gè)小于數(shù)組大小的整數(shù),我們將該機(jī)制稱之為哈希函數(shù)。在 Java 中我們不必為尋找這樣的整數(shù)而大傷腦筋,因?yàn)槊總€(gè)對(duì)象都必定存在一個(gè)返回整數(shù)值的 hashCode 方法,而我們需要做的就是將其轉(zhuǎn)換為整數(shù),然后再將該值除以數(shù)組大小取余即可。如下
int hashValue = Maths.abs(obj.hashCode()) % size;
下面是 HashMap、HashTable 的:
----------HashMap------------
//計(jì)算hash值
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//計(jì)算key的索引位置
static int indexFor(int h, int length) {
return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length; //確認(rèn)該key的索引位置
位置的索引就代表了該節(jié)點(diǎn)在數(shù)組中的位置。下圖是哈希映射的基本原理圖:
http://wiki.jikexueyuan.com/project/java-enhancement/images/33-4.gif" alt="fig.4" />
在該圖中 1-4 步驟是找到該元素在數(shù)組中位置,5-8 步驟是將該元素插入數(shù)組中。在插入的過程中會(huì)遇到一點(diǎn)點(diǎn)小挫折。在眾多肯能存在多個(gè)元素他們的 hash 值是一樣的,這樣就會(huì)得到相同的索引位置,也就說多個(gè)元素會(huì)映射到相同的位置,這個(gè)過程我們稱之為“沖突”。解決沖突的辦法就是在索引位置處插入一個(gè)鏈接列表,并簡(jiǎn)單地將元素添加到此鏈接列表。當(dāng)然也不是簡(jiǎn)單的插入,在 HashMap 中的處理過程如下:獲取索引位置的鏈表,如果該鏈表為 null,則將該元素直接插入,否則通過比較是否存在與該 key 相同的 key,若存在則覆蓋原來(lái) key 的 value 并返回舊值,否則將該元素保存在鏈頭(最先保存的元素放在鏈尾)。下面是 HashMap 的 put 方法,該方法詳細(xì)展示了計(jì)算索引位置,將元素插入到適當(dāng)?shù)奈恢玫娜窟^程:
public V put(K key, V value) {
//當(dāng)key為null,調(diào)用putForNullKey方法,保存null與table第一個(gè)位置中,這是HashMap允許為null的原因
if (key == null)
return putForNullKey(value);
//計(jì)算key的hash值
int hash = hash(key.hashCode());
//計(jì)算key hash 值在 table 數(shù)組中的位置
int i = indexFor(hash, table.length);
//從i出開始迭代 e,判斷是否存在相同的key
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鏈上是否有hash值相同的(key相同)
//若存在相同,則直接覆蓋value,返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回舊值
}
}
//修改次數(shù)增加1
modCount++;
//將key、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}
HashMap 的 put 方法展示了哈希映射的基本思想,其實(shí)如果我們查看其它的 Map,發(fā)現(xiàn)其原理都差不多!
首先我們這樣假設(shè),假設(shè)哈希映射的內(nèi)部數(shù)組的大小只有1,所有的元素都將映射該位置(0),從而構(gòu)成一條較長(zhǎng)的鏈表。由于我們更新、訪問都要對(duì)這條鏈表進(jìn)行線性搜索,這樣勢(shì)必會(huì)降低效率。我們假設(shè),如果存在一個(gè)非常大數(shù)組,每個(gè)位置鏈表處都只有一個(gè)元素,在進(jìn)行訪問時(shí)計(jì)算其 index 值就會(huì)獲得該對(duì)象,這樣做雖然會(huì)提高我們搜索的效率,但是它浪費(fèi)了控件。誠(chéng)然,雖然這兩種方式都是極端的,但是它給我們提供了一種優(yōu)化思路:使用一個(gè)較大的數(shù)組讓元素能夠均勻分布。在 Map 有兩個(gè)會(huì)影響到其效率,一是容器的初始化大小、二是負(fù)載因子。
在哈希映射表中,內(nèi)部數(shù)組中的每個(gè)位置稱作“存儲(chǔ)桶”(bucket),而可用的存儲(chǔ)桶數(shù)(即內(nèi)部數(shù)組的大小)稱作容量 (capacity),我們?yōu)榱耸?Map 對(duì)象能夠有效地處理任意數(shù)的元素,將 Map 設(shè)計(jì)成可以調(diào)整自身的大小。我們知道當(dāng) Map 中的元素達(dá)到一定量的時(shí)候就會(huì)調(diào)整容器自身的大小,但是這個(gè)調(diào)整大小的過程其開銷是非常大的。調(diào)整大小需要將原來(lái)所有的元素插入到新數(shù)組中。我們知道 index = hash(key) % length。這樣可能會(huì)導(dǎo)致原先沖突的鍵不在沖突,不沖突的鍵現(xiàn)在沖突的,重新計(jì)算、調(diào)整、插入的過程開銷是非常大的,效率也比較低下。所以,如果我們開始知道 Map 的預(yù)期大小值,將 Map 調(diào)整的足夠大,則可以大大減少甚至不需要重新調(diào)整大小,這很有可能會(huì)提高速度。下面是 HashMap 調(diào)整容器大小的過程,通過下面的代碼我們可以看到其擴(kuò)容過程的復(fù)雜性:
void resize(int newCapacity) {
Entry[] oldTable = table; //原始容器
int oldCapacity = oldTable.length; //原始容器大小
if (oldCapacity == MAXIMUM_CAPACITY) { //是否超過最大值:1073741824
threshold = Integer.MAX_VALUE;
return;
}
//新的數(shù)組:大小為 oldCapacity * 2
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
/*
* 重新計(jì)算閥值 = newCapacity * loadFactor > MAXIMUM_CAPACITY + 1 ?
* newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
*/
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//將元素插入到新數(shù)組中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
為了確認(rèn)何時(shí)需要調(diào)整 Map 容器,Map 使用了一個(gè)額外的參數(shù)并且粗略計(jì)算存儲(chǔ)容器的密度。在 Map 調(diào)整大小之前,使用”負(fù)載因子”來(lái)指示 Map 將會(huì)承擔(dān)的“負(fù)載量”,也就是它的負(fù)載程度,當(dāng)容器中元素的數(shù)量達(dá)到了這個(gè)“負(fù)載量”,則 Map 將會(huì)進(jìn)行擴(kuò)容操作。負(fù)載因子、容量、Map 大小之間的關(guān)系如下:負(fù)載因子 * 容量 > map 大小 —–>調(diào)整 Map 大小。
例如:如果負(fù)載因子大小為 0.75(HashMap 的默認(rèn)值),默認(rèn)容量為 11,則 11 * 0.75 = 8.25 = 8,所以當(dāng)我們?nèi)萜髦胁迦氲诎藗€(gè)元素的時(shí)候,Map 就會(huì)調(diào)整大小。
負(fù)載因子本身就是在控件和時(shí)間之間的折衷。當(dāng)我使用較小的負(fù)載因子時(shí),雖然降低了沖突的可能性,使得單個(gè)鏈表的長(zhǎng)度減小了,加快了訪問和更新的速度,但是它占用了更多的控件,使得數(shù)組中的大部分控件沒有得到利用,元素分布比較稀疏,同時(shí)由于 Map 頻繁的調(diào)整大小,可能會(huì)降低性能。但是如果負(fù)載因子過大,會(huì)使得元素分布比較緊湊,導(dǎo)致產(chǎn)生沖突的可能性加大,從而訪問、更新速度較慢。所以我們一般推薦不更改負(fù)載因子的值,采用默認(rèn)值 0.75.