1. HashMap概述

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)（Hashtable跟HashMap很像，唯一的區(qū)別是Hashtalbe中的方法是線(xiàn)程安全的，也就是同步的）。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類(lèi)不保證映射的順序，特別是它不保證該順序恒久不變。

2. 四個(gè)關(guān)注點(diǎn)在HashMap上的答案

關(guān)注點(diǎn)結(jié)論

HashMap是否允許空	Key和Value都允許為空
HashMap是否允許重復(fù)數(shù)據(jù)	Key重復(fù)會(huì)覆蓋、Value允許重復(fù)
HashMap是否有序	無(wú)序，特別說(shuō)明這個(gè)無(wú)序指的是遍歷HashMap的時(shí)候，得到的元素的順序基本不可能是put的順序
HashMap是否線(xiàn)程安全	非線(xiàn)程安全

3. HashMap的數(shù)據(jù)結(jié)構(gòu)

在java編程語(yǔ)言中，最基本的結(jié)構(gòu)就是兩種，一個(gè)是數(shù)組，另外一個(gè)是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來(lái)構(gòu)造的，HashMap也不例外。HashMap實(shí)際上是一個(gè)“鏈表的數(shù)組”的數(shù)據(jù)結(jié)構(gòu)，每個(gè)元素存放鏈表頭結(jié)點(diǎn)的數(shù)組，即數(shù)組和鏈表的結(jié)合體。

從上圖中可以看出，HashMap底層就是一個(gè)數(shù)組結(jié)構(gòu)，數(shù)組中的每一項(xiàng)又是一個(gè)鏈表。當(dāng)新建一個(gè)HashMap的時(shí)候，就會(huì)初始化一個(gè)數(shù)組。源碼如下：

/*** The table, resized as necessary. Length MUST Always be a power of two.*/ transient Entry[] table;static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;final int hash;…… }

可以看出，Entry就是數(shù)組中的元素，每個(gè) Map.Entry 其實(shí)就是一個(gè)key-value對(duì)，它持有一個(gè)指向下一個(gè)元素的引用，這就構(gòu)成了鏈表。

HashMap的底層主要是基于數(shù)組和鏈表來(lái)實(shí)現(xiàn)的，它之所以有相當(dāng)快的查詢(xún)速度主要是因?yàn)樗峭ㄟ^(guò)計(jì)算散列碼來(lái)決定存儲(chǔ)的位置。HashMap中主要是通過(guò)key的hashCode來(lái)計(jì)算hash值的，只要hashCode相同，計(jì)算出來(lái)的hash值就一樣。如果存儲(chǔ)的對(duì)象對(duì)多了，就有可能不同的對(duì)象所算出來(lái)的hash值是相同的，這就出現(xiàn)了所謂的hash沖突。學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)都知道，解決hash沖突的方法有很多，HashMap底層是通過(guò)鏈表來(lái)解決hash沖突的。

圖中，紫色部分即代表哈希表，也稱(chēng)為哈希數(shù)組，數(shù)組的每個(gè)元素都是一個(gè)單鏈表的頭節(jié)點(diǎn)，鏈表是用來(lái)解決沖突的，如果不同的key映射到了數(shù)組的同一位置處，就將其放入單鏈表中。

對(duì)于 HashMap 及其子類(lèi)而言，它們采用 Hash 算法來(lái)決定集合中元素的存儲(chǔ)位置。當(dāng)系統(tǒng)開(kāi)始初始化 HashMap 時(shí)，系統(tǒng)會(huì)創(chuàng)建一個(gè)長(zhǎng)度為 capacity 的 Entry 數(shù)組，這個(gè)數(shù)組里可以存儲(chǔ)元素的位置被稱(chēng)為“桶（bucket）”，每個(gè) bucket 都有其指定索引，系統(tǒng)可以根據(jù)其索引快速訪(fǎng)問(wèn)該 bucket 里存儲(chǔ)的元素。

無(wú)論何時(shí)，HashMap 的每個(gè)“桶”只存儲(chǔ)一個(gè)元素（也就是一個(gè) Entry），由于 Entry 對(duì)象可以包含一個(gè)引用變量（就是 Entry 構(gòu)造器的的最后一個(gè)參數(shù)）用于指向下一個(gè) Entry，因此可能出現(xiàn)的情況是：HashMap 的 bucket 中只有一個(gè) Entry，但這個(gè) Entry 指向另一個(gè) Entry ——這就形成了一個(gè) Entry 鏈。

4. HashMap的構(gòu)造函數(shù)

HashMap提供了三個(gè)構(gòu)造函數(shù)：

• HashMap()：構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。
• HashMap(int initialCapacity)：構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。
• HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap。

在這里提到了兩個(gè)參數(shù)：初始容量，加載因子。這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時(shí)的容量，加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿(mǎn)的一種尺度，它衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對(duì)于使用鏈表法的散列表來(lái)說(shuō)，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大，對(duì)空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過(guò)于稀疏，對(duì)空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為0.75，一般情況下我們是無(wú)需修改的。

若:加載因子越大,填滿(mǎn)的元素越多,好處是,空間利用率高了,但:沖突的機(jī)會(huì)加大了.鏈表長(zhǎng)度會(huì)越來(lái)越長(zhǎng),查找效率降低。
反之,加載因子越小,填滿(mǎn)的元素越少,好處是:沖突的機(jī)會(huì)減小了,但:空間浪費(fèi)多了.表中的數(shù)據(jù)將過(guò)于稀疏（很多空間還沒(méi)用，就開(kāi)始擴(kuò)容了）

當(dāng)哈希表中條目數(shù)超出了當(dāng)前容量*加載因子(其實(shí)就是HashMap的實(shí)際容量)時(shí)，則對(duì)該哈希表進(jìn)行rehash操作，將哈希表擴(kuò)充至兩倍的桶數(shù)。

5. HashMap的存取實(shí)現(xiàn)

5.1 存儲(chǔ)

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()); ------(1)//計(jì)算key hash 值在 table 數(shù)組中的位置int i = indexFor(hash, table.length); ------(2)//從i出開(kāi)始迭代 e,找到 key 保存的位置for (Entry<K, V> e = table[i]; e != null; e = e.next) {Object k;//判斷該條鏈上是否存在相同的key值//若存在相同，則直接覆蓋value，返回舊valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value; //舊值 = 新值e.value = value;e.recordAccess(this);return oldValue; //返回舊值}}//修改次數(shù)增加1modCount++;//將key、value添加至i位置處addEntry(hash, key, value, i);return null; }

通過(guò)源碼我們可以清晰看到HashMap保存數(shù)據(jù)的過(guò)程為：首先判斷key是否為null，若為null，則直接調(diào)用putForNullKey方法，將value放置在數(shù)組第一個(gè)位置上。若不為空則根據(jù)key的hashCode重新計(jì)算hash值，然后根據(jù)hash值得到這個(gè)元素在table數(shù)組中的位置（即下標(biāo)），如果table數(shù)組在該位置處已經(jīng)存放有其他元素了，則通過(guò)比較是否存在相同的key，若存在則覆蓋原來(lái)key的value，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。若table在該處沒(méi)有元素，就直接將該元素放到此數(shù)組中的該位置上。這個(gè)過(guò)程看似比較簡(jiǎn)單，其實(shí)深有內(nèi)幕。有如下幾點(diǎn)：

1、先看迭代處。此處迭代原因就是為了防止存在相同的key值，若發(fā)現(xiàn)兩個(gè)key值相同時(shí)，HashMap的處理方式是用新value替換舊value，這里并沒(méi)有處理key，這就解釋了HashMap中沒(méi)有兩個(gè)相同的key。另外，注意一點(diǎn)，對(duì)比Key是否相同，是先比HashCode是否相同，HashCode相同再判斷equals是否為true，這樣大大增加了HashMap的效率。

2、在看（1）、（2）處。這里是HashMap的精華所在。首先是hash方法，該方法為一個(gè)純粹的數(shù)學(xué)計(jì)算，就是計(jì)算h的hash值。此算法加入了高位計(jì)算，防止低位不變，高位變化時(shí)，造成的hash沖突。

static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4); }

為什么要經(jīng)過(guò)這樣的運(yùn)算呢？這就是HashMap的高明之處。先看個(gè)例子，一個(gè)十進(jìn)制數(shù)32768(二進(jìn)制1000 0000 0000 0000)，經(jīng)過(guò)上述公式運(yùn)算之后的結(jié)果是35080(二進(jìn)制1000 1001 0000 1000)。看出來(lái)了嗎？或許這樣還看不出什么，再舉個(gè)數(shù)字61440(二進(jìn)制1111 0000 0000 0000)，運(yùn)算結(jié)果是65263(二進(jìn)制1111 1110 1110 1111)，現(xiàn)在應(yīng)該很明顯了，它的目的是讓“1”變的均勻一點(diǎn)，散列的本意就是要盡量均勻分布。

我們知道對(duì)于HashMap的table而言，數(shù)據(jù)分布需要均勻（最好每項(xiàng)都只有一個(gè)元素，這樣就可以直接找到），不能太緊也不能太松，太緊會(huì)導(dǎo)致查詢(xún)速度慢，太松則浪費(fèi)空間。計(jì)算hash值后，怎么才能保證table元素分布均與呢？我們會(huì)想到取模，但是由于取模的消耗較大，HashMap是這樣處理的：調(diào)用indexFor方法。

static int indexFor(int h, int length) {return h & (length-1); }

HashMap的底層數(shù)組長(zhǎng)度總是2的n次方，在構(gòu)造函數(shù)中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數(shù)組長(zhǎng)度為2的n次方。當(dāng)length為2的n次方時(shí)，h&(length - 1)就相當(dāng)于對(duì)length取模，也就是h%length，但是&比%具有更高的效率，速度比直接取模快得多，這是HashMap在速度上的一個(gè)優(yōu)化。至于為什么是2的n次方下面解釋。

我們回到indexFor方法，該方法僅有一條語(yǔ)句：h&(length - 1)，這句話(huà)除了上面的取模運(yùn)算外還有一個(gè)非常重要的責(zé)任：均勻分布table數(shù)據(jù)和充分利用空間。這里我們假設(shè)length為16(2^n)和15，h為5、6、7。

當(dāng)length=15時(shí)，6和7的結(jié)果一樣，這樣表示他們?cè)趖able存儲(chǔ)的位置是相同的，也就是產(chǎn)生了碰撞，6、7就會(huì)在一個(gè)位置形成鏈表，這樣就會(huì)導(dǎo)致查詢(xún)速度降低。誠(chéng)然這里只分析三個(gè)數(shù)字不是很多，那么我們就看0-15。

從上面的圖表中我們看到總共發(fā)生了8此碰撞，同時(shí)發(fā)現(xiàn)浪費(fèi)的空間非常大，有1、3、5、7、9、11、13、15處沒(méi)有記錄，也就是沒(méi)有存放數(shù)據(jù)。這是因?yàn)樗麄冊(cè)谂c14進(jìn)行&運(yùn)算時(shí)，得到的結(jié)果最后一位永遠(yuǎn)都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲(chǔ)數(shù)據(jù)的，空間減少，進(jìn)一步增加碰撞幾率，這樣就會(huì)導(dǎo)致查詢(xún)速度慢。而當(dāng)數(shù)組長(zhǎng)度為16時(shí)，即為2的n次方時(shí)，2n-1得到的二進(jìn)制數(shù)的每個(gè)位上的值都為1（比如(24-1)2=1111），這使得在低位上&時(shí)，得到的和原h(huán)ash的低位相同，加之hash(int h)方法對(duì)key的hashCode的進(jìn)一步優(yōu)化，加入了高位計(jì)算，就使得只有相同的hash值的兩個(gè)值才會(huì)被放到數(shù)組中的同一個(gè)位置上形成鏈表。所以說(shuō)當(dāng)length = 2^n時(shí)，不同的hash值發(fā)生碰撞的概率比較小，這樣就會(huì)使得數(shù)據(jù)在table數(shù)組中分布較均勻，查詢(xún)速度也較快。

這里我們?cè)賮?lái)復(fù)習(xí)put的流程：當(dāng)我們想一個(gè)HashMap中添加一對(duì)key-value時(shí)，系統(tǒng)首先會(huì)計(jì)算key的hash值，然后根據(jù)hash值確認(rèn)在table中存儲(chǔ)的位置。若該位置沒(méi)有元素，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。如果兩個(gè)hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來(lái)節(jié)點(diǎn)的value。如果兩個(gè)hash值相等但key值不等 ，則將該節(jié)點(diǎn)插入該鏈表的鏈頭。具體的實(shí)現(xiàn)過(guò)程見(jiàn)addEntry方法，如下：

void addEntry(int hash, K key, V value, int bucketIndex) {//獲取bucketIndex處的EntryEntry<K, V> e = table[bucketIndex];//將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來(lái)的 Entry table[bucketIndex] = new Entry<K, V>(hash, key, value, e);//若HashMap中元素的個(gè)數(shù)超過(guò)極限了，則容量擴(kuò)大兩倍if (size++ >= threshold)resize(2 * table.length); }

這個(gè)方法中有兩點(diǎn)需要注意：

6. 鏈的產(chǎn)生

這是一個(gè)非常優(yōu)雅的設(shè)計(jì)。系統(tǒng)總是將新的Entry對(duì)象添加到bucketIndex處。如果bucketIndex處已經(jīng)有了對(duì)象，那么新添加的Entry對(duì)象將指向原有的Entry對(duì)象，形成一條Entry鏈，但是若bucketIndex處沒(méi)有Entry對(duì)象，也就是e==null,那么新添加的Entry對(duì)象指向null，也就不會(huì)產(chǎn)生Entry鏈了。

7. 擴(kuò)容問(wèn)題

隨著HashMap中元素的數(shù)量越來(lái)越多，發(fā)生碰撞的概率就越來(lái)越大，所產(chǎn)生的鏈表長(zhǎng)度就會(huì)越來(lái)越長(zhǎng)，這樣勢(shì)必會(huì)影響HashMap的速度，為了保證HashMap的效率，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理。該臨界點(diǎn)在當(dāng)HashMap中元素的數(shù)量等于table數(shù)組長(zhǎng)度*加載因子。但是擴(kuò)容是一個(gè)非常耗時(shí)的過(guò)程，因?yàn)樗枰匦掠?jì)算這些數(shù)據(jù)在新table數(shù)組中的位置并進(jìn)行復(fù)制處理。所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。

根據(jù)上面 put 方法的源代碼可以看出，當(dāng)程序試圖將一個(gè) key-value 對(duì)放入 HashMap 中時(shí)，程序首先根據(jù)該 key 的 hashCode() 返回值決定該 Entry 的存儲(chǔ)位置：如果兩個(gè) Entry 的 key 的 hashCode() 返回值相同，那它們的存儲(chǔ)位置相同。如果這兩個(gè) Entry 的 key 通過(guò) equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value，但 key 不會(huì)覆蓋。如果這兩個(gè) Entry 的 key 通過(guò) equals 比較返回 false，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部。

8. 讀取

相對(duì)于HashMap的存而言，取就顯得比較簡(jiǎn)單了。通過(guò)key的hash值找到在table數(shù)組中的索引處的Entry，然后返回該key對(duì)應(yīng)的value即可。

public V get(Object key) {// 若為null，調(diào)用getForNullKey方法返回相對(duì)應(yīng)的valueif (key == null)return getForNullKey();// 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼 int hash = hash(key.hashCode());// 取出 table 數(shù)組中指定索引處的值for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k;//若搜索的key與查找的key相同，則返回相對(duì)應(yīng)的valueif (e.hash == hash && ((k = e.key) == key || key.equals(k)))return e.value;}return null; }

有了上面存儲(chǔ)時(shí)的hash算法作為基礎(chǔ)，理解起來(lái)這段代碼就很容易了。從上面的源代碼中可以看出：從HashMap中g(shù)et元素時(shí)，首先計(jì)算key的hashCode，找到數(shù)組中對(duì)應(yīng)位置的某一元素，然后通過(guò)key的equals方法在對(duì)應(yīng)位置的鏈表中找到需要的元素。

當(dāng) HashMap 的每個(gè) bucket 里存儲(chǔ)的 Entry 只是單個(gè) Entry ——也就是沒(méi)有通過(guò)指針產(chǎn)生 Entry 鏈時(shí)，此時(shí)的 HashMap 具有最好的性能：當(dāng)程序通過(guò) key 取出對(duì)應(yīng) value 時(shí)，系統(tǒng)只要先計(jì)算出該 key 的 hashCode() 返回值，在根據(jù)該 hashCode 返回值找出該 key 在 table 數(shù)組中的索引，然后取出該索引處的 Entry，最后返回該 key 對(duì)應(yīng)的 value 即可。

從上面代碼中可以看出，如果 HashMap 的每個(gè) bucket 里只有一個(gè) Entry 時(shí)，HashMap 可以根據(jù)索引、快速地取出該 bucket 里的 Entry；在發(fā)生“Hash 沖突”的情況下，單個(gè) bucket 里存儲(chǔ)的不是一個(gè) Entry，而是一個(gè) Entry 鏈，系統(tǒng)只能必須按順序遍歷每個(gè) Entry，直到找到想搜索的 Entry 為止——如果恰好要搜索的 Entry 位于該 Entry 鏈的最末端（該 Entry 是最早放入該 bucket 中），那系統(tǒng)必須循環(huán)到最后才能找到該元素。

3) 歸納起來(lái)簡(jiǎn)單地說(shuō)，HashMap 在底層將 key-value 當(dāng)成一個(gè)整體進(jìn)行處理，這個(gè)整體就是一個(gè) Entry 對(duì)象。HashMap 底層采用一個(gè) Entry[] 數(shù)組來(lái)保存所有的 key-value 對(duì)，當(dāng)需要存儲(chǔ)一個(gè) Entry 對(duì)象時(shí)，會(huì)根據(jù)hash算法來(lái)決定其在數(shù)組中的存儲(chǔ)位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲(chǔ)位置；當(dāng)需要取出一個(gè)Entry時(shí)，也會(huì)根據(jù)hash算法找到其在數(shù)組中的存儲(chǔ)位置，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。

9. 再談HashCode的重要性

前面講到了，HashMap中對(duì)Key的HashCode要做一次rehash，防止一些糟糕的Hash算法生成的糟糕的HashCode，那么為什么要防止糟糕的HashCode？

糟糕的HashCode意味著的是Hash沖突，即多個(gè)不同的Key可能得到的是同一個(gè)HashCode，糟糕的Hash算法意味著的就是Hash沖突的概率增大，這意味著HashMap的性能將下降，表現(xiàn)在兩方面：

(1)、有10個(gè)Key，可能6個(gè)Key的HashCode都相同，另外四個(gè)Key所在的Entry均勻分布在table的位置上，而某一個(gè)位置上卻連接了6個(gè)Entry。這就失去了HashMap的意義，HashMap這種數(shù)據(jù)結(jié)構(gòu)性高性能的前提是，Entry均勻地分布在table位置上，但現(xiàn)在確是1 1 1 1 6的分布。所以，我們要求HashCode有很強(qiáng)的隨機(jī)性，這樣就盡可能地可以保證了Entry分布的隨機(jī)性，提升了HashMap的效率。

(2)、HashMap在一個(gè)某個(gè)table位置上遍歷鏈表的時(shí)候的代碼：

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

看到，由于采用了”&&”運(yùn)算符，因此先比較HashCode，HashCode都不相同就直接pass了，不會(huì)再進(jìn)行equals比較了。HashCode因?yàn)槭莍nt值，比較速度非常快，而equals方法往往會(huì)對(duì)比一系列的內(nèi)容，速度會(huì)慢一些。Hash沖突的概率大，意味著equals比較的次數(shù)勢(shì)必增多，必然降低了HashMap的效率了。

原文鏈接：博客園@平凡希 http://www.cnblogs.com/xiaoxi/p/5822209.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Java数据结构和算法：HashMap，哈希表，哈希函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。