1. HashMap概述

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

2. 四個關注點在HashMap上的答案

關注點結論

HashMap是否允許空	Key和Value都允許為空
HashMap是否允許重復數據	Key重復會覆蓋、Value允許重復
HashMap是否有序	無序，特別說明這個無序指的是遍歷HashMap的時候，得到的元素的順序基本不可能是put的順序
HashMap是否線程安全	非線程安全

3. HashMap的數據結構

在java編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“鏈表的數組”的數據結構，每個元素存放鏈表頭結點的數組，即數組和鏈表的結合體。

從上圖中可以看出，HashMap底層就是一個數組結構，數組中的每一項又是一個鏈表。當新建一個HashMap的時候，就會初始化一個數組。源碼如下：

/*** 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就是數組中的元素，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用，這就構成了鏈表。

HashMap的底層主要是基于數組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash沖突。學過數據結構的同學都知道，解決hash沖突的方法有很多，HashMap底層是通過鏈表來解決hash沖突的。

圖中，紫色部分即代表哈希表，也稱為哈希數組，數組的每個元素都是一個單鏈表的頭節點，鏈表是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就將其放入單鏈表中。

對于 HashMap 及其子類而言，它們采用 Hash 算法來決定集合中元素的存儲位置。當系統開始初始化 HashMap 時，系統會創建一個長度為 capacity 的 Entry 數組，這個數組里可以存儲元素的位置被稱為“桶（bucket）”，每個 bucket 都有其指定索引，系統可以根據其索引快速訪問該 bucket 里存儲的元素。

無論何時，HashMap 的每個“桶”只存儲一個元素（也就是一個 Entry），由于 Entry 對象可以包含一個引用變量（就是 Entry 構造器的的最后一個參數）用于指向下一個 Entry，因此可能出現的情況是：HashMap 的 bucket 中只有一個 Entry，但這個 Entry 指向另一個 Entry ——這就形成了一個 Entry 鏈。

4. HashMap的構造函數

HashMap提供了三個構造函數：

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

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

若:加載因子越大,填滿的元素越多,好處是,空間利用率高了,但:沖突的機會加大了.鏈表長度會越來越長,查找效率降低。
反之,加載因子越小,填滿的元素越少,好處是:沖突的機會減小了,但:空間浪費多了.表中的數據將過于稀疏（很多空間還沒用，就開始擴容了）

當哈希表中條目數超出了當前容量*加載因子(其實就是HashMap的實際容量)時，則對該哈希表進行rehash操作，將哈希表擴充至兩倍的桶數。

5. HashMap的存取實現

5.1 存儲

public V put(K key, V value) {//當key為null，調用putForNullKey方法，保存null與table第一個位置中，這是HashMap允許為null的原因if (key == null)return putForNullKey(value);//計算key的hash值int hash = hash(key.hashCode()); ------(1)//計算key hash 值在 table 數組中的位置int i = indexFor(hash, table.length); ------(2)//從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; //返回舊值}}//修改次數增加1modCount++;//將key、value添加至i位置處addEntry(hash, key, value, i);return null; }

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

1、先看迭代處。此處迭代原因就是為了防止存在相同的key值，若發現兩個key值相同時，HashMap的處理方式是用新value替換舊value，這里并沒有處理key，這就解釋了HashMap中沒有兩個相同的key。另外，注意一點，對比Key是否相同，是先比HashCode是否相同，HashCode相同再判斷equals是否為true，這樣大大增加了HashMap的效率。

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

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

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

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

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

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

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

當length=15時，6和7的結果一樣，這樣表示他們在table存儲的位置是相同的，也就是產生了碰撞，6、7就會在一個位置形成鏈表，這樣就會導致查詢速度降低。誠然這里只分析三個數字不是很多，那么我們就看0-15。

從上面的圖表中我們看到總共發生了8此碰撞，同時發現浪費的空間非常大，有1、3、5、7、9、11、13、15處沒有記錄，也就是沒有存放數據。這是因為他們在與14進行&運算時，得到的結果最后一位永遠都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲數據的，空間減少，進一步增加碰撞幾率，這樣就會導致查詢速度慢。而當數組長度為16時，即為2的n次方時，2n-1得到的二進制數的每個位上的值都為1（比如(24-1)2=1111），這使得在低位上&時，得到的和原hash的低位相同，加之hash(int h)方法對key的hashCode的進一步優化，加入了高位計算，就使得只有相同的hash值的兩個值才會被放到數組中的同一個位置上形成鏈表。所以說當length = 2^n時，不同的hash值發生碰撞的概率比較小，這樣就會使得數據在table數組中分布較均勻，查詢速度也較快。

這里我們再來復習put的流程：當我們想一個HashMap中添加一對key-value時，系統首先會計算key的hash值，然后根據hash值確認在table中存儲的位置。若該位置沒有元素，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節點的value。如果兩個hash值相等但key值不等 ，則將該節點插入該鏈表的鏈頭。具體的實現過程見addEntry方法，如下：

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

這個方法中有兩點需要注意：

6. 鏈的產生

這是一個非常優雅的設計。系統總是將新的Entry對象添加到bucketIndex處。如果bucketIndex處已經有了對象，那么新添加的Entry對象將指向原有的Entry對象，形成一條Entry鏈，但是若bucketIndex處沒有Entry對象，也就是e==null,那么新添加的Entry對象指向null，也就不會產生Entry鏈了。

7. 擴容問題

隨著HashMap中元素的數量越來越多，發生碰撞的概率就越來越大，所產生的鏈表長度就會越來越長，這樣勢必會影響HashMap的速度，為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數量等于table數組長度*加載因子。但是擴容是一個非常耗時的過程，因為它需要重新計算這些數據在新table數組中的位置并進行復制處理。所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能。

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

8. 讀取

相對于HashMap的存而言，取就顯得比較簡單了。通過key的hash值找到在table數組中的索引處的Entry，然后返回該key對應的value即可。

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

有了上面存儲時的hash算法作為基礎，理解起來這段代碼就很容易了。從上面的源代碼中可以看出：從HashMap中get元素時，首先計算key的hashCode，找到數組中對應位置的某一元素，然后通過key的equals方法在對應位置的鏈表中找到需要的元素。

當 HashMap 的每個 bucket 里存儲的 Entry 只是單個 Entry ——也就是沒有通過指針產生 Entry 鏈時，此時的 HashMap 具有最好的性能：當程序通過 key 取出對應 value 時，系統只要先計算出該 key 的 hashCode() 返回值，在根據該 hashCode 返回值找出該 key 在 table 數組中的索引，然后取出該索引處的 Entry，最后返回該 key 對應的 value 即可。

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

3) 歸納起來簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，也會根據hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。

9. 再談HashCode的重要性

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

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

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

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

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

看到，由于采用了”&&”運算符，因此先比較HashCode，HashCode都不相同就直接pass了，不會再進行equals比較了。HashCode因為是int值，比較速度非常快，而equals方法往往會對比一系列的內容，速度會慢一些。Hash沖突的概率大，意味著equals比較的次數勢必增多，必然降低了HashMap的效率了。

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

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。