您的位置：首頁>設計>正文

乾貨！JAVA容器

技術棧 2017-10-19 0
前言

這次我和大家一起學習HashMap， HashMap我們在工作中經常會使用， 而且面試中也很頻繁會問到， 因為它裡面蘊含著很多知識點， 可以很好的考察個人基礎。 但一個這麼重要的東西， 我為什麼沒有在一開始就去學習它呢， 因為它是由多種基礎的資料結構和一些代碼設計思想組成的。 我們要學習了這些基礎， 再學習HashMap， 這樣我們才能更好的去理解它。 古人雲：無欲速， 無見小利。 欲速則不達， 見小利則大事不成。 HashMap其實就是ArrayList和LinkedList的資料結構加上hashCode和equals方法的思想設計出來的。 沒有理解上述說的知識點的同學可以翻開我過往的文章記錄。

下面我就以面試問答的形式學習我們的——HashMap（源碼分析基於JDK8， 輔以JDK7）， 問答內容只是對HashMap的一個總結歸納。

問答內容

1.問：HashMap有用過嗎？您能給我說說他的主要用途嗎？

答：

HashMap是基於Map介面實現的一種鍵-值對的存儲結構， 允許null值， 同時非有序， 非同步(即執行緒不安全)。 HashMap的底層實現是陣列 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分）。 它存儲和查找資料時， 是根據鍵key的hashCode的值計算出具體的存儲位置。 HashMap最多只允許一條記錄的鍵key為null， HashMap增刪改查等常規操作都有不錯的執行效率， 是ArrayList和LinkedList等資料結構的一種折中實現。

示例代碼：

// 創建一個HashMap， 如果沒有指定初始大小， 預設底層hash表陣列的大小為16 HashMap hashMap = new HashMap(); // 往容器裡面添加元素 hashMap.put("小明", "好帥"); hashMap.put("老王", "坑爹貨"); hashMap.put("老鐵", "沒毛病"); hashMap.put("掘金", "好地方"); hashMap.put("王五", "別搞事"); // 獲取key為小明的元素 好帥 String element = hashMap.get("小明"); // value : 好帥 System.out.println(element); // 移除key為王五的元素 String removeElement = hashMap.remove("王五"); // value : 別搞事 System.out.println(removeElement); // 修改key為小明的元素的值value 為 其實有點醜 hashMap.replace("小明", "其實有點醜"); // {老鐵=沒毛病, 小明=其實有點醜, 老王=坑爹貨, 掘金=好地方} System.out.println(hashMap); // 通過put方法也可以達到修改對應元素的值的效果 hashMap.put("小明", "其實還可以啦,開玩笑的"); // {老鐵=沒毛病, 小明=其實還可以啦,開玩笑的, 老王=坑爹貨, 掘金=好地方} System.out.println(hashMap); // 判斷key為老王的元素是否存在(捉姦老王) boolean isExist = hashMap.containsKey("老王"); // true , 老王竟然來搞事 System.out.println(isExist); // 判斷是否有 value = "坑爹貨" 的人 boolean isHasSomeOne = hashMap.containsValue("坑爹貨"); // true 老王是坑爹貨 System.out.println(isHasSomeOne); // 查看這個容器裡面還有幾個傢伙 value : 4 System.out.println(hashMap.size());

HashMap的底層實現是陣列 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分），

核心組成元素有：

int size;用於記錄HashMap實際存儲元素的個數；

float loadFactor;負載因數（預設是0.75， 此屬性後面詳細解釋）。

int threshold;下一次擴容時的閾值， 達到閾值便會觸發擴容機制resize（閾值 threshold = 容器容量 capacity * 負載因數 load factor）。 也就是說， 在容器定義好容量之後， 負載因數越大， 所能容納的鍵值對元素個數就越多。

Node[] table;底層陣列， 充當雜湊表的作用， 用於存儲對應hash位置的元素Node， 此陣列長度總是2的N次冪。 （具體原因後面詳細解釋）

示例代碼：

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {····· /* ---------------- Fields -------------- */ /** * 雜湊表， 在第一次使用到時進行初始化， 重置大小是必要的操作， * 當分配容量時， 長度總是2的N次冪。 */ transient Node[] table; /** * 實際存儲的key - value 鍵值對 個數 */ transient int size; /** * 下一次擴容時的閾值 * (閾值 threshold = 容器容量 capacity * 負載因數 load factor). * @serial */ int threshold; /** * 雜湊表的負載因數 * * @serial */ final float loadFactor;·····}

其中Node[] table;雜湊表存儲的核心元素是Node,Node包含：

final int hash;元素的雜湊值， 決定元素存儲在Node[] table;雜湊表中的位置。 由final修飾可知， 當hash的值確定後， 就不能再修改。

final K key鍵， 由final修飾可知，

當key的值確定後， 就不能再修改。

V value;值

Node next;記錄下一個元素結點(單鏈表結構， 用於解決hash衝突)

示例代碼：

/** * 定義HashMap存儲元素結點的底層實現 */ static class Node implements Map.Entry { final int hash;//元素的雜湊值 由final修飾可知， 當hash的值確定後， 就不能再修改 final K key;// 鍵， 由final修飾可知， 當key的值確定後， 就不能再修改 V value; // 值 Node next; // 記錄下一個元素結點(單鏈表結構， 用於解決hash衝突) /** * Node結點構造方法 */ Node(int hash, K key, V value, Node next) { this.hash = hash;//元素的雜湊值 this.key = key;// 鍵 this.value = value; // 值 this.next = next;// 記錄下一個元素結點 } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } /** * 為Node重寫hashCode方法， 值為：key的hashCode 異或 value的hashCode * 運算作用就是將2個hashCode的二進位中， 同一位置相同的值為0， 不同的為1。 */ public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } /** * 修改某一元素的值 */ public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } /** * 為Node重寫equals方法 */ public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

hashMap記憶體結構圖

2.

問：您能說說HashMap常用操作的底層實現原理嗎？如存儲put(K key, V value)， 查找get(Object key)， 刪除remove(Object key)， 修改replace(K key, V value)等操作。

答：

調用put(K key, V value)操作添加key-value鍵值對時， 進行了如下操作：

判斷雜湊表Node[] table是否為空或者null， 是則執行resize()方法進行擴容。

根據插入的鍵值key的hash值， 通過(n - 1) & hash當前元素的hash值 &hash表長度 - 1（實際就是hash值 %hash表長度） 計算出存儲位置table[i]。 如果存儲位置沒有元素存放， 則將新增結點存儲在此位置table[i]。

如果存儲位置已經有鍵值對元素存在， 則判斷該位置元素的hash值和key值是否和當前操作元素一致， 一致則證明是修改value操作，覆蓋value即可。

當前存儲位置即有元素，又不和當前操作元素一致，則證明此位置table[i]已經發生了hash衝突，則通過判斷頭結點是否是treeNode，如果是treeNode則證明此位置的結構是紅黑樹，已紅黑樹的方式新增結點。

如果不是紅黑樹，則證明是單鏈表，將新增結點插入至鏈表的最後位置，隨後判斷當前鏈表長度是否 大於等於 8，是則將當前存儲位置的鏈表轉化為紅黑樹。遍歷過程中如果發現key已經存在，則直接覆蓋value。

插入成功後，判斷當前存儲鍵值對的數量 大於 閾值threshold是則擴容。

hashMap put方法執行流程圖

示例代碼：

/** * 添加key-value鍵值對 * * @param key 鍵 * @param value 值 * @return 如果原本存在此key，則返回舊的value值，如果是新增的key- * value，則返回nulll */ public V put(K key, V value) { //實際調用putVal方法進行添加 key-value 鍵值對操作 return putVal(hash(key), key, value, false, true); } /** * 根據key 鍵 的 hashCode 通過 “擾動函數” 生成對應的 hash值 * 經過此操作後，使每一個key對應的hash值生成的更均勻， * 減少元素之間的碰撞幾率（後面詳細說明） */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * 添加key-value鍵值對的實際調用方法（重點） * * @param hash key 鍵的hash值 * @param key 鍵 * @param value 值 * @param onlyIfAbsent 此值如果是true, 則如果此key已存在value，則不執 * 行修改操作 * @param evict 此值如果是false，雜湊表是在初始化模式 * @return 返回原本的舊值, 如果是新增，則返回null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 用於記錄當前的hash表 Node[] tab; // 用於記錄當前的鏈表結點 Node p; // n用於記錄hash表的長度，i用於記錄當前操作索引index int n, i; // 當前hash表為空 if ((tab = table) == null || (n = tab.length) == 0) // 初始化hash表，並把初始化後的hash表長度值賦值給n n = (tab = resize()).length; // 1）通過 (n - 1) & hash 當前元素的hash值 & hash表長度 - 1 // 2）確定當前元素的存儲位置，此運算等價於 當前元素的hash值 % hash表的長度 // 3）計算出的存儲位置沒有元素存在 if ((p = tab[i = (n - 1) & hash]) == null) // 4) 則新建一個Node結點，在該位置存儲此元素 tab[i] = newNode(hash, key, value, null); else { // 當前存儲位置已經有元素存在了(不考慮是修改的情況的話，就代表發生hash衝突了) // 用於存放新增結點 Node e; // 用於臨時存在某個key值 K k; // 1)如果當前位置已存在元素的hash值和新增元素的hash值相等 // 2)並且key也相等，則證明是同一個key元素，想執行修改value操作 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;// 將當前結點引用賦值給e else if (p instanceof TreeNode) // 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構，則已紅黑樹結點結構新增元素 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else {// 排除上述情況，則證明已發生hash衝突，並hash衝突位置現時的結構是單鏈表結構 for (int binCount = 0; ; ++binCount) { //遍歷單鏈表，將新元素結點放置此鏈表的最後一位 if ((e = p.next) == null) { // 將新元素結點放在此鏈表的最後一位 p.next = newNode(hash, key, value, null); // 新增結點後，當前結點數量是否大於等於 閾值 8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 大於等於8則將鏈表轉換成紅黑樹 treeifyBin(tab, hash); break; } // 如果鏈表中已經存在對應的key，則覆蓋value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // 已存在對應key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //如果允許修改，則修改value為新值 e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 當前存儲鍵值對的數量 大於 閾值 是則擴容 if (++size > threshold) // 重置hash大小，將舊hash表的資料逐一複製到新的hash表中（後面詳細講解） resize(); afterNodeInsertion(evict); // 返回null，則證明是新增操作，而不是修改操作 return null; }

調用get(Object key)操作根據鍵key查找對應的key-value鍵值對時，進行了如下操作：

先調用hash(key)方法計算出key的hash值

根據查找的鍵值key的hash值，通過(n - 1) & hash當前元素的hash值 &hash表長度 - 1（實際就是hash值 %hash表長度）計算出存儲位置table[i]，判斷存儲位置是否有元素存在 。

如果存儲位置有元素存放，但是頭結點元素不是要查找的元素，則需要遍歷該位置進行查找。

先判斷頭結點是否是treeNode，如果是treeNode則證明此位置的結構是紅黑樹，以紅色樹的方式遍歷查找該結點，沒有則返回null。

如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較鏈表結點，鏈表結點的key的hash值和要獲取的key的hash
值相等，並且 鏈表結點的key本身和要獲取的key相等，則返回該結點，遍歷結束仍未找到對應key的結點，則返回null。

示例代碼：

/** * 返回指定 key 所映射的 value 值 * 或者 返回 null 如果容器裡不存在對應的key * * 更確切地講，如果此映射包含一個滿足 (key==null ? k==null :key.equals(k)) * 的從 k 鍵到 v 值的映射關係， * 則此方法返回 v；否則返回 null。（最多只能有一個這樣的映射關係。） * * 返回 null 值並不一定 表明該映射不包含該鍵的映射關係； * 也可能該映射將該鍵顯示地映射為 null。可使用containsKey操作來區分這兩種情況。 * * @see #put(Object, Object) */ public V get(Object key) { Node e; // 1.先調用 hash(key)方法計算出 key 的 hash值 // 2.隨後調用getNode方法獲取對應key所映射的value值 return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 獲取雜湊表結點的方法實現 * * @param hash key 鍵的hash值 * @param key 鍵 * @return 返回對應的結點，如果結點不存在，則返回null */ final Node getNode(int hash, Object key) { // 用於記錄當前的hash表 Node[] tab; // first用於記錄對應hash位置的第一個結點，e充當工作結點的作用 Node first, e; // n用於記錄hash表的長度 int n; // 用於臨時存放Key K k; // 通過 (n - 1) & hash 當前元素的hash值 & hash表長度 - 1 // 判斷當前元素的存儲位置是否有元素存在 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//元素存在的情況 // 如果頭結點的key的hash值 和 要獲取的key的hash值相等 // 並且 頭結點的key本身 和要獲取的 key 相等 if (first.hash == hash && // always check first node 總是檢查頭結點 ((k = first.key) == key || (key != null && key.equals(k)))) // 返回該位置的頭結點 return first; if ((e = first.next) != null) {// 頭結點不相等 if (first instanceof TreeNode) // 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構 // 通過紅黑樹結點的方式獲取對應key結點 return ((TreeNode)first).getTreeNode(hash, key); do {// 當前位置不是紅黑樹，則證明是單鏈表 // 遍歷單鏈表，逐一比較鏈表結點 // 鏈表結點的key的hash值 和 要獲取的key的hash值相等 // 並且 鏈表結點的key本身 和要獲取的 key 相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 找到對應的結點則返回 return e; } while ((e = e.next) != null); } } // 通過上述查找均無找到，則返回null return null; }

調用remove(Object key)操作根據鍵key刪除對應的key-value鍵值對時，進行了如下操作：

先調用hash(key)方法計算出key的hash值

根據查找的鍵值key的hash值，通過(n - 1) & hash當前元素的hash值 &hash表長度 - 1（實際就是hash值 %hash表長度） 計算出存儲位置table[i]，判斷存儲位置是否有元素存在 。

如果存儲位置有元素存放，但是頭結點元素不是要刪除的元素，則需要遍歷該 位置進行查找。

先判斷頭結點是否是treeNode，如果是treeNode則證明此位置的結構是紅黑樹，以紅色樹的方式遍歷查找並刪除該結點，沒有則返回null。

如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較鏈表結點，鏈表結點的key的hash值和要獲取的key的hash
值相等，並且鏈表結點的key本身和要獲取的key相等，則此為要刪除的結點，記錄此結點至變數node中，遍歷結束仍未找到對應key的結點，則返回null。

如果找到要刪除的結點node，則判斷是否需要比較value也是否一致，如果value值一致或者不需要比較value
值，則執行刪除結點操作，刪除操作根據不同的情況與結構進行不同的處理。

如果當前結點是樹結點，則證明當前位置的鏈表已變成紅黑樹結構，通過紅黑樹結點的方式刪除對應結點。

如果不是紅黑樹，則證明是單鏈表。如果要刪除的是頭結點，則當前存儲位置table[i]的頭結點指向刪除結點的下一個結點。

如果要刪除的結點不是頭結點，則將要刪除的結點的後繼結點node.next賦值給要刪除結點的前驅結點的next
域，即p.next = node.next;。

7.HashMap當前存儲鍵值對的數量 - 1，並返回刪除結點。

示例代碼：

/** * 從此映射中移除指定鍵的映射關係（如果存在）。 * * @param key 其映射關係要從映射中移除的鍵 * @return 與 key 關聯的舊值；如果 key 沒有任何映射關係，則返回 null。 * （返回 null 還可能表示該映射之前將 null 與 key 關聯。） */ public V remove(Object key) { Node e; // 1.先調用 hash(key)方法計算出 key 的 hash值 // 2.隨後調用removeNode方法刪除對應key所映射的結點 return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * 刪除雜湊表結點的方法實現 * * @param hash 鍵的hash值 * @param key 鍵 * @param value 用於比較的value值，當matchValue 是 true時才有效, 否則忽略 * @param matchValue 如果是 true 只有當value相等時才會移除 * @param movable 如果是 false當執行移除操作時，不刪除其他結點 * @return 返回刪除結點node，不存在則返回null */ final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { // 用於記錄當前的hash表 Node[] tab; // 用於記錄當前的鏈表結點 Node p; // n用於記錄hash表的長度，index用於記錄當前操作索引index int n, index; // 通過 (n - 1) & hash 當前元素的hash值 & hash表長度 - 1 // 判斷當前元素的存儲位置是否有元素存在 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {// 元素存在的情況 // node 用於記錄找到的結點，e為工作結點 Node node = null, e; K k; V v; // 如果頭結點的key的hash值 和 要獲取的key的hash值相等 // 並且 頭結點的key本身 和要獲取的 key 相等 // 則證明此頭結點就是要刪除的結點 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 記錄要刪除的結點的引用地址至node中 node = p; else if ((e = p.next) != null) {// 頭結點不相等 if (p instanceof TreeNode)// 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構 // 通過紅黑樹結點的方式獲取對應key結點 // 記錄要刪除的結點的引用地址至node中 node = ((TreeNode)p).getTreeNode(hash, key); else {// 當前位置不是紅黑樹，則證明是單鏈表 do { // 遍歷單鏈表，逐一比較鏈表結點 // 鏈表結點的key的hash值 和 要獲取的key的hash值相等 // 並且 鏈表結點的key本身 和要獲取的 key 相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { // 找到則記錄要刪除的結點的引用地址至node中，中斷遍歷 node = e; break; } p = e; } while ((e = e.next) != null); } } // 如果找到要刪除的結點，則判斷是否需要比較value也是否一致 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // value值一致或者不需要比較value值，則執行刪除結點操作 if (node instanceof TreeNode) // 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構 // 通過紅黑樹結點的方式刪除對應結點 ((TreeNode)node).removeTreeNode(this, tab, movable); else if (node == p) // node 和 p相等，則證明刪除的是頭結點 // 當前存儲位置的頭結點指向刪除結點的下一個結點 tab[index] = node.next; else // 刪除的不是頭結點 // p是刪除結點node的前驅結點，p的next改為記錄要刪除結點node的後繼結點 p.next = node.next; ++modCount; // 當前存儲鍵值對的數量 - 1 --size; afterNodeRemoval(node); // 返回刪除結點 return node; } } // 不存在要刪除的結點，則返回null return null; }

調用replace(K key, V value)操作根據鍵key查找對應的key-value鍵值對，隨後替換對應的值value，進行了如下操作：

先調用hash(key)方法計算出key的hash值

隨後調用getNode方法獲取對應key所映射的value值 。

記錄元素舊值，將新值賦值給元素，返回元素舊值，如果沒有找到元素，則返回null。

示例代碼：

/** * 替換指定 key 所映射的 value 值 * * @param key 對應要替換value值元素的key鍵 * @param value 要替換對應元素的新value值 * @return 返回原本的舊值，如果沒有找到key對應的元素，則返回null * @since 1.8 JDK1.8新增方法 */ public V replace(K key, V value) { Node e; // 1.先調用 hash(key)方法計算出 key 的 hash值 // 2.隨後調用getNode方法獲取對應key所映射的value值 if ((e = getNode(hash(key), key)) != null) {// 如果找到對應的元素 // 元素舊值 V oldValue = e.value; // 將新值賦值給元素 e.value = value; afterNodeAccess(e); // 返回元素舊值 return oldValue; } // 沒有找到元素，則返回null return null; }

3.

問 1：您上面說，存放一個元素時，先計算它的hash值確定它的存儲位置，然後再把這個元素放到對應的位置上，那萬一這個位置上面已經有元素存在呢，新增的這個元素怎麼辦？

問 2：hash衝突（或者叫hash碰撞）是什麼？為什麼會出現這種現象，如何解決hash衝突？

答：

hash衝突： 當我們調用put(K key, V value)操作添加key-value鍵值對，這個key-value鍵值對存放在的位置是通過擾動函數(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)計算鍵key的hash值。隨後將這個hash值%模上雜湊表Node[] table的長度得到具體的存放位置。所以put(K key, V value)多個元素，是有可能計算出相同的存放位置。此現象就是hash衝突或者叫hash碰撞。

例子如下：

元素A的hash值為 9，元素B的hash值為17。雜湊表Node[] table的長度為8。則元素 A 的存放位置為9 % 8 = 1
，元素 B 的存放位置為17 % 8 = 1。兩個元素的存放位置均為table[1]，發生了hash衝突。

hash衝突的避免：既然會發生hash衝突，我們就應該想辦法避免此現象的發生，解決這個問題最關鍵就是如果生成元素的hash值。Java是使用“擾動函數”生成元素的hash值。

示例代碼：

/** * JDK 7 的 hash方法 */ final int hash(int h) { h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * JDK 8 的 hash方法 */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

Java7做了4次16位右位移異或混合，Java 8中這步已經簡化了，只做一次16位右位移異或混合，而不是四次，但原理是不變的。例子如下：

擾動函數執行例子

右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始雜湊碼的高位和低位元，以此來加大低位的隨機性。而且混合後的低位元摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來。

上述擾動函數的解釋參考自：JDK 源碼中 HashMap 的 hash 方法原理是什麼？

hash衝突解決：解決hash衝突的方法有很多，常見的有：開發定址法，再散列法，鏈地址法，公共溢位區域法（詳細說明請查看我的文章JAVA基礎-自問自答學hashCode和equals）。HashMap是使用鏈位址法解決hash衝突的，當有衝突元素放進來時，會將此元素插入至此位置鏈表的最後一位，形成單鏈表。但是由於是單鏈表的緣故，每當通過hash % length找到該位置的元素時，均需要從頭遍歷鏈表，通過逐一比較hash值，找到對應元素。如果此位置元素過多，造成鏈表過長，遍歷時間會大大增加，最壞情況下的時間複雜度為O(N)，造成查找效率過低。所以當存在位置的鏈表長度 大於等於 8 時，HashMap會將鏈表 轉變為 紅黑樹，紅黑樹最壞情況下的時間複雜度為O(logn)。以此提高查找效率。

4.

問：HashMap的容量為什麼一定要是2的n次方？

答：

因為調用put(K key, V value)操作添加key-value鍵值對時，具體確定此元素的位置是通過hash值%模上雜湊表Node[] table的長度hash % length計算的。但是"模"運算的消耗相對較大，通過位運算h & (length-1)也可以得到取模後的存放位置，而位運算的運行效率高，但只有length的長度是2的n次方時，h & (length-1)才等價於h % length
。

而且當陣列長度為2的n次冪的時候，不同的key算出的index相同的幾率較小，那麼資料在陣列上分佈就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。

例子：

hash & (length-1)運算過程

上圖中，左邊兩組的陣列長度是16（2的4次方），右邊兩組的陣列長度是15。兩組的hash值均為8和9。

當陣列長度是15時，當它們和1110進行&與運算（相同為1，不同為0）時，計算的結果都是1000
，所以他們都會存放在相同的位置table[8]中，這樣就發生了hash衝突，那麼查詢時就要遍歷鏈表，逐一比較hash
值，降低了查詢的效率。

同時，我們可以發現，當陣列長度為15的時候，hash值均會與14（1110）進行&與運算，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，陣列可以使用的位置比陣列長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率。

所以，HashMap的容量是2的n次方，有利於提高計算元素存放位置時的效率，也降低了hash衝突的幾率。因此，我們使用HashMap存儲大量資料的時候，最好先預先指定容器的大小為2的n次方，即使我們不指定為2的n次方，HashMap
也會把容器的大小設置成最接近設置數的2的n次方，如，設置HashMap的大小為 7 ，則HashMap會將容器大小設置成最接近7的一個2的n次方數，此值為 8 。

示例代碼：

/** * 返回一個比指定數cap大的，並且大小是2的n次方的數 * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

5.

問：HashMap的負載因數是什麼，有什麼作用？

答：負載因數表示雜湊表空間的使用程度（或者說是雜湊表空間的利用率）。

例子如下：

底層雜湊表Node[] table的容量大小capacity為16，負載因數load factor為0.75，則當存儲的元素個數size = capacity 16 * load factor 0.75等於 12 時，則會觸發HashMap的擴容機制，調用resize()方法進行擴容。

當負載因數越大，則HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發生hash碰撞的幾率就會加大，從而鏈表就會拉長，此時的查詢效率就會降低。

當負載因數越小，則鏈表中的資料量就越稀疏，此時會對空間造成浪費，但是此時查詢效率高。

我們可以在創建HashMap時根據實際需要適當地調整load factor的值；如果程式比較關心空間開銷、記憶體比較緊張，可以適當地增加負載因數；如果程式比較關心時間開銷，記憶體比較寬裕則可以適當的減少負載因數。通常情況下，預設負載因數 (0.75) 在時間和空間成本上尋求一種折衷，程式師無需改變負載因數的值。

因此，如果我們在初始化HashMap時，就預估知道需要裝載key-value鍵值對的容量size，我們可以通過size / load factor計算出我們需要初始化的容量大小initialCapacity，這樣就可以避免HashMap因為存放的元素達到閾值threshold而頻繁調用resize()方法進行擴容。從而保證了較好的性能。

6.

問：您能說說HashMap和HashTable的區別嗎？

答：HashMap和HashTable有如下區別：

1）容器整體結構：

2） 容量設定與擴容機制：

3） 散列分佈方式（計算存儲位置）：

HashMap是先將key鍵的hashCode經過擾動函數擾動後得到hash值，然後再利用hash & (length - 1)的方式代替取模，得到元素的存儲位置。

Hashtable則是除留餘數法進行計算存儲位置的（因為其預設容量也不是2的n次方。所以也無法用位運算替代模運算），int index = (hash & 0x7FFFFFFF) % tab.length;。

由於HashMap的容器容量一定是2的n次方，所以能使用hash & (length - 1)的方式代替取模的方式計算元素的位置提高運算效率，但Hashtable的容器容量不一定是2的n次方，所以不能使用此運算方式代替。

4）執行緒安全（最重要）：

HashMap不是執行緒安全，如果想執行緒安全，可以通過調用synchronizedMap(Map m)使其執行緒安全。但是使用時的運行效率會下降，所以建議使用ConcurrentHashMap容器以此達到執行緒安全。

Hashtable則是執行緒安全的，每個操作方法前都有synchronized修飾使其同步，但運行效率也不高，所以還是建議使用容器以此達到執行緒安全。

因此，Hashtable是一個遺留容器，如果我們不需要執行緒同步，則建議使用HashMap，如果需要執行緒同步，則建議使用ConcurrentHashMap。

7.

問：您說HashMap不是執行緒安全的，那如果多執行緒下，它是如何處理的？並且什麼情況下會發生執行緒不安全的情況？

答：

HashMap不是執行緒安全的，如果多個執行緒同時對同一個HashMap更改資料的話，會導致資料不一致或者資料污染。如果出現執行緒不安全的操作時，HashMap會盡可能的拋出ConcurrentModificationException防止資料異常，當我們在對一個HashMap進行遍歷時，在遍歷期間，我們是不能對HashMap進行添加，刪除等更改資料的操作的，否則也會拋出ConcurrentModificationException異常，此為fail-fast（快速失敗）機制。從源碼上分析，我們在put,remove
等更改HashMap資料時，都會導致modCount的改變，當expectedModCount != modCount時，則拋出ConcurrentModificationException。如果想要執行緒安全，可以考慮使用ConcurrentHashMap。

而且，在多執行緒下操作HashMap，由於存在擴容機制，當HashMap調用resize()進行自動擴容時，可能會導致閉環的發生。限於篇幅，我暫不帶著大家一起去分析resize()方法導致閉環發生的現象造成原因了，遲點有空我會再補充上去，請見諒，大家可以參考如下文章：

8.

問：我們在使用HashMap時，選取什麼物件作為key鍵比較好，為什麼？

答：

可變對象：指創建後自身狀態能改變的物件。換句話說，可變物件是該物件在創建後它的雜湊值可能被改變。

我們在使用HashMap時，最好選擇不可變物件作為key。例如String，Integer等不可變類型作為key
是非常明智的。如果key物件是可變的，那麼key的雜湊值就可能改變。在HashMap中可變物件作為Key會造成資料丟失。因為我們再進行hash & (length - 1)取模運算計算位置查找對應元素時，位置可能已經發生改變，導致資料丟失。

總結

HashMap是基於Map介面實現的一種鍵-值對的存儲結構，允許null值，同時非有序，非同步(即執行緒不安全)。HashMap的底層實現是陣列 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分）。

HashMap定位元素位置是通過鍵key經過擾動函數擾動後得到hash值，然後再通過hash & (length - 1)代替取模的方式進行元素定位的。

HashMap是使用鏈位址法解決hash衝突的，當有衝突元素放進來時，會將此元素插入至此位置鏈表的最後一位，形成單鏈表。當存在位置的鏈表長度 大於等於 8 時，HashMap會將鏈表 轉變為 紅黑樹，以此提高查找效率。

HashMap的容量是2的n次方，有利於提高計算元素存放位置時的效率，也降低了hash衝突的幾率。因此，我們使用HashMap。存儲大量資料的時候，最好先預先指定容器的大小為2的n次方，即使我們不指定為2的n次方，HashMap也會把容器的大小設置成最接近設置數的2的n次方，如，設置HashMap的大小為 7 ，則HashMap會將容器大小設置成最接近7的一個2的n次方數，此值為 8 。

HashMap的負載因數表示雜湊表空間的使用程度（或者說是雜湊表空間的利用率）。當負載因數越大，則HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發生hash碰撞的幾率就會加大，從而鏈表就會拉長，此時的查詢效率就會降低。當負載因數越小， 則鏈表中的資料量就越稀疏，此時會對空間造成浪費，但是此時查詢效率高。

HashMap不是執行緒安全的，Hashtable則是執行緒安全的。但Hashtable是一個遺留容器，如果我們不需要執行緒同步，則建議使用HashMap，如果需要執行緒同步，則建議使用ConcurrentHashMap。

在多執行緒下操作HashMap，由於存在擴容機制，當HashMap調用resize()進行自動擴容時，可能會導致閉環的發生。

我們在使用HashMap時，最好選擇不可變物件作為key。例如String，Integer等不可變類型作為key是非常明智的。

由於最近工作較忙，也有拖延症發作的問題，所以文章遲遲未能完成發佈，現時完成的文章其實對我而言，也不算太好，但還是打算先發出來讓大家看看，一起學習學習，看有什麼不好的地方，我再慢慢改進，如果此文對你有幫助，請給個贊，謝謝大家。

一致則證明是修改value操作，覆蓋value即可。

當前存儲位置即有元素，又不和當前操作元素一致，則證明此位置table[i]已經發生了hash衝突，則通過判斷頭結點是否是treeNode，如果是treeNode則證明此位置的結構是紅黑樹，已紅黑樹的方式新增結點。

如果不是紅黑樹，則證明是單鏈表，將新增結點插入至鏈表的最後位置，隨後判斷當前鏈表長度是否 大於等於 8，是則將當前存儲位置的鏈表轉化為紅黑樹。遍歷過程中如果發現key已經存在，則直接覆蓋value。

插入成功後，判斷當前存儲鍵值對的數量 大於 閾值threshold是則擴容。

hashMap put方法執行流程圖

示例代碼：

/** * 添加key-value鍵值對 * * @param key 鍵 * @param value 值 * @return 如果原本存在此key，則返回舊的value值，如果是新增的key- * value，則返回nulll */ public V put(K key, V value) { //實際調用putVal方法進行添加 key-value 鍵值對操作 return putVal(hash(key), key, value, false, true); } /** * 根據key 鍵 的 hashCode 通過 “擾動函數” 生成對應的 hash值 * 經過此操作後，使每一個key對應的hash值生成的更均勻， * 減少元素之間的碰撞幾率（後面詳細說明） */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * 添加key-value鍵值對的實際調用方法（重點） * * @param hash key 鍵的hash值 * @param key 鍵 * @param value 值 * @param onlyIfAbsent 此值如果是true, 則如果此key已存在value，則不執 * 行修改操作 * @param evict 此值如果是false，雜湊表是在初始化模式 * @return 返回原本的舊值, 如果是新增，則返回null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 用於記錄當前的hash表 Node[] tab; // 用於記錄當前的鏈表結點 Node p; // n用於記錄hash表的長度，i用於記錄當前操作索引index int n, i; // 當前hash表為空 if ((tab = table) == null || (n = tab.length) == 0) // 初始化hash表，並把初始化後的hash表長度值賦值給n n = (tab = resize()).length; // 1）通過 (n - 1) & hash 當前元素的hash值 & hash表長度 - 1 // 2）確定當前元素的存儲位置，此運算等價於 當前元素的hash值 % hash表的長度 // 3）計算出的存儲位置沒有元素存在 if ((p = tab[i = (n - 1) & hash]) == null) // 4) 則新建一個Node結點，在該位置存儲此元素 tab[i] = newNode(hash, key, value, null); else { // 當前存儲位置已經有元素存在了(不考慮是修改的情況的話，就代表發生hash衝突了) // 用於存放新增結點 Node e; // 用於臨時存在某個key值 K k; // 1)如果當前位置已存在元素的hash值和新增元素的hash值相等 // 2)並且key也相等，則證明是同一個key元素，想執行修改value操作 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;// 將當前結點引用賦值給e else if (p instanceof TreeNode) // 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構，則已紅黑樹結點結構新增元素 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else {// 排除上述情況，則證明已發生hash衝突，並hash衝突位置現時的結構是單鏈表結構 for (int binCount = 0; ; ++binCount) { //遍歷單鏈表，將新元素結點放置此鏈表的最後一位 if ((e = p.next) == null) { // 將新元素結點放在此鏈表的最後一位 p.next = newNode(hash, key, value, null); // 新增結點後，當前結點數量是否大於等於 閾值 8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 大於等於8則將鏈表轉換成紅黑樹 treeifyBin(tab, hash); break; } // 如果鏈表中已經存在對應的key，則覆蓋value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // 已存在對應key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //如果允許修改，則修改value為新值 e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 當前存儲鍵值對的數量 大於 閾值 是則擴容 if (++size > threshold) // 重置hash大小，將舊hash表的資料逐一複製到新的hash表中（後面詳細講解） resize(); afterNodeInsertion(evict); // 返回null，則證明是新增操作，而不是修改操作 return null; }

調用get(Object key)操作根據鍵key查找對應的key-value鍵值對時，進行了如下操作：

先調用hash(key)方法計算出key的hash值

根據查找的鍵值key的hash值，通過(n - 1) & hash當前元素的hash值 &hash表長度 - 1（實際就是hash值 %hash表長度）計算出存儲位置table[i]，判斷存儲位置是否有元素存在 。

如果存儲位置有元素存放，但是頭結點元素不是要查找的元素，則需要遍歷該位置進行查找。

先判斷頭結點是否是treeNode，如果是treeNode則證明此位置的結構是紅黑樹，以紅色樹的方式遍歷查找該結點，沒有則返回null。

如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較鏈表結點，鏈表結點的key的hash值和要獲取的key的hash
值相等，並且 鏈表結點的key本身和要獲取的key相等，則返回該結點，遍歷結束仍未找到對應key的結點，則返回null。

示例代碼：

/** * 返回指定 key 所映射的 value 值 * 或者 返回 null 如果容器裡不存在對應的key * * 更確切地講，如果此映射包含一個滿足 (key==null ? k==null :key.equals(k)) * 的從 k 鍵到 v 值的映射關係， * 則此方法返回 v；否則返回 null。（最多只能有一個這樣的映射關係。） * * 返回 null 值並不一定 表明該映射不包含該鍵的映射關係； * 也可能該映射將該鍵顯示地映射為 null。可使用containsKey操作來區分這兩種情況。 * * @see #put(Object, Object) */ public V get(Object key) { Node e; // 1.先調用 hash(key)方法計算出 key 的 hash值 // 2.隨後調用getNode方法獲取對應key所映射的value值 return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 獲取雜湊表結點的方法實現 * * @param hash key 鍵的hash值 * @param key 鍵 * @return 返回對應的結點，如果結點不存在，則返回null */ final Node getNode(int hash, Object key) { // 用於記錄當前的hash表 Node[] tab; // first用於記錄對應hash位置的第一個結點，e充當工作結點的作用 Node first, e; // n用於記錄hash表的長度 int n; // 用於臨時存放Key K k; // 通過 (n - 1) & hash 當前元素的hash值 & hash表長度 - 1 // 判斷當前元素的存儲位置是否有元素存在 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//元素存在的情況 // 如果頭結點的key的hash值 和 要獲取的key的hash值相等 // 並且 頭結點的key本身 和要獲取的 key 相等 if (first.hash == hash && // always check first node 總是檢查頭結點 ((k = first.key) == key || (key != null && key.equals(k)))) // 返回該位置的頭結點 return first; if ((e = first.next) != null) {// 頭結點不相等 if (first instanceof TreeNode) // 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構 // 通過紅黑樹結點的方式獲取對應key結點 return ((TreeNode)first).getTreeNode(hash, key); do {// 當前位置不是紅黑樹，則證明是單鏈表 // 遍歷單鏈表，逐一比較鏈表結點 // 鏈表結點的key的hash值 和 要獲取的key的hash值相等 // 並且 鏈表結點的key本身 和要獲取的 key 相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 找到對應的結點則返回 return e; } while ((e = e.next) != null); } } // 通過上述查找均無找到，則返回null return null; }

調用remove(Object key)操作根據鍵key刪除對應的key-value鍵值對時，進行了如下操作：

先調用hash(key)方法計算出key的hash值

根據查找的鍵值key的hash值，通過(n - 1) & hash當前元素的hash值 &hash表長度 - 1（實際就是hash值 %hash表長度） 計算出存儲位置table[i]，判斷存儲位置是否有元素存在 。

如果存儲位置有元素存放，但是頭結點元素不是要刪除的元素，則需要遍歷該 位置進行查找。

先判斷頭結點是否是treeNode，如果是treeNode則證明此位置的結構是紅黑樹，以紅色樹的方式遍歷查找並刪除該結點，沒有則返回null。

如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較鏈表結點，鏈表結點的key的hash值和要獲取的key的hash
值相等，並且鏈表結點的key本身和要獲取的key相等，則此為要刪除的結點，記錄此結點至變數node中，遍歷結束仍未找到對應key的結點，則返回null。

如果找到要刪除的結點node，則判斷是否需要比較value也是否一致，如果value值一致或者不需要比較value
值，則執行刪除結點操作，刪除操作根據不同的情況與結構進行不同的處理。

如果當前結點是樹結點，則證明當前位置的鏈表已變成紅黑樹結構，通過紅黑樹結點的方式刪除對應結點。

如果不是紅黑樹，則證明是單鏈表。如果要刪除的是頭結點，則當前存儲位置table[i]的頭結點指向刪除結點的下一個結點。

如果要刪除的結點不是頭結點，則將要刪除的結點的後繼結點node.next賦值給要刪除結點的前驅結點的next
域，即p.next = node.next;。

7.HashMap當前存儲鍵值對的數量 - 1，並返回刪除結點。

示例代碼：

/** * 從此映射中移除指定鍵的映射關係（如果存在）。 * * @param key 其映射關係要從映射中移除的鍵 * @return 與 key 關聯的舊值；如果 key 沒有任何映射關係，則返回 null。 * （返回 null 還可能表示該映射之前將 null 與 key 關聯。） */ public V remove(Object key) { Node e; // 1.先調用 hash(key)方法計算出 key 的 hash值 // 2.隨後調用removeNode方法刪除對應key所映射的結點 return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * 刪除雜湊表結點的方法實現 * * @param hash 鍵的hash值 * @param key 鍵 * @param value 用於比較的value值，當matchValue 是 true時才有效, 否則忽略 * @param matchValue 如果是 true 只有當value相等時才會移除 * @param movable 如果是 false當執行移除操作時，不刪除其他結點 * @return 返回刪除結點node，不存在則返回null */ final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { // 用於記錄當前的hash表 Node[] tab; // 用於記錄當前的鏈表結點 Node p; // n用於記錄hash表的長度，index用於記錄當前操作索引index int n, index; // 通過 (n - 1) & hash 當前元素的hash值 & hash表長度 - 1 // 判斷當前元素的存儲位置是否有元素存在 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {// 元素存在的情況 // node 用於記錄找到的結點，e為工作結點 Node node = null, e; K k; V v; // 如果頭結點的key的hash值 和 要獲取的key的hash值相等 // 並且 頭結點的key本身 和要獲取的 key 相等 // 則證明此頭結點就是要刪除的結點 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 記錄要刪除的結點的引用地址至node中 node = p; else if ((e = p.next) != null) {// 頭結點不相等 if (p instanceof TreeNode)// 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構 // 通過紅黑樹結點的方式獲取對應key結點 // 記錄要刪除的結點的引用地址至node中 node = ((TreeNode)p).getTreeNode(hash, key); else {// 當前位置不是紅黑樹，則證明是單鏈表 do { // 遍歷單鏈表，逐一比較鏈表結點 // 鏈表結點的key的hash值 和 要獲取的key的hash值相等 // 並且 鏈表結點的key本身 和要獲取的 key 相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { // 找到則記錄要刪除的結點的引用地址至node中，中斷遍歷 node = e; break; } p = e; } while ((e = e.next) != null); } } // 如果找到要刪除的結點，則判斷是否需要比較value也是否一致 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // value值一致或者不需要比較value值，則執行刪除結點操作 if (node instanceof TreeNode) // 如果當前結點是樹結點 // 則證明當前位置的鏈表已變成紅黑樹結構 // 通過紅黑樹結點的方式刪除對應結點 ((TreeNode)node).removeTreeNode(this, tab, movable); else if (node == p) // node 和 p相等，則證明刪除的是頭結點 // 當前存儲位置的頭結點指向刪除結點的下一個結點 tab[index] = node.next; else // 刪除的不是頭結點 // p是刪除結點node的前驅結點，p的next改為記錄要刪除結點node的後繼結點 p.next = node.next; ++modCount; // 當前存儲鍵值對的數量 - 1 --size; afterNodeRemoval(node); // 返回刪除結點 return node; } } // 不存在要刪除的結點，則返回null return null; }

調用replace(K key, V value)操作根據鍵key查找對應的key-value鍵值對，隨後替換對應的值value，進行了如下操作：

先調用hash(key)方法計算出key的hash值

隨後調用getNode方法獲取對應key所映射的value值 。

記錄元素舊值，將新值賦值給元素，返回元素舊值，如果沒有找到元素，則返回null。

示例代碼：

/** * 替換指定 key 所映射的 value 值 * * @param key 對應要替換value值元素的key鍵 * @param value 要替換對應元素的新value值 * @return 返回原本的舊值，如果沒有找到key對應的元素，則返回null * @since 1.8 JDK1.8新增方法 */ public V replace(K key, V value) { Node e; // 1.先調用 hash(key)方法計算出 key 的 hash值 // 2.隨後調用getNode方法獲取對應key所映射的value值 if ((e = getNode(hash(key), key)) != null) {// 如果找到對應的元素 // 元素舊值 V oldValue = e.value; // 將新值賦值給元素 e.value = value; afterNodeAccess(e); // 返回元素舊值 return oldValue; } // 沒有找到元素，則返回null return null; }

3.

問 1：您上面說，存放一個元素時，先計算它的hash值確定它的存儲位置，然後再把這個元素放到對應的位置上，那萬一這個位置上面已經有元素存在呢，新增的這個元素怎麼辦？

問 2：hash衝突（或者叫hash碰撞）是什麼？為什麼會出現這種現象，如何解決hash衝突？

答：

hash衝突： 當我們調用put(K key, V value)操作添加key-value鍵值對，這個key-value鍵值對存放在的位置是通過擾動函數(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)計算鍵key的hash值。隨後將這個hash值%模上雜湊表Node[] table的長度得到具體的存放位置。所以put(K key, V value)多個元素，是有可能計算出相同的存放位置。此現象就是hash衝突或者叫hash碰撞。

例子如下：

元素A的hash值為 9，元素B的hash值為17。雜湊表Node[] table的長度為8。則元素 A 的存放位置為9 % 8 = 1
，元素 B 的存放位置為17 % 8 = 1。兩個元素的存放位置均為table[1]，發生了hash衝突。

hash衝突的避免：既然會發生hash衝突，我們就應該想辦法避免此現象的發生，解決這個問題最關鍵就是如果生成元素的hash值。Java是使用“擾動函數”生成元素的hash值。

示例代碼：

/** * JDK 7 的 hash方法 */ final int hash(int h) { h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * JDK 8 的 hash方法 */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

Java7做了4次16位右位移異或混合，Java 8中這步已經簡化了，只做一次16位右位移異或混合，而不是四次，但原理是不變的。例子如下：

擾動函數執行例子

右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始雜湊碼的高位和低位元，以此來加大低位的隨機性。而且混合後的低位元摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來。

上述擾動函數的解釋參考自：JDK 源碼中 HashMap 的 hash 方法原理是什麼？

hash衝突解決：解決hash衝突的方法有很多，常見的有：開發定址法，再散列法，鏈地址法，公共溢位區域法（詳細說明請查看我的文章JAVA基礎-自問自答學hashCode和equals）。HashMap是使用鏈位址法解決hash衝突的，當有衝突元素放進來時，會將此元素插入至此位置鏈表的最後一位，形成單鏈表。但是由於是單鏈表的緣故，每當通過hash % length找到該位置的元素時，均需要從頭遍歷鏈表，通過逐一比較hash值，找到對應元素。如果此位置元素過多，造成鏈表過長，遍歷時間會大大增加，最壞情況下的時間複雜度為O(N)，造成查找效率過低。所以當存在位置的鏈表長度 大於等於 8 時，HashMap會將鏈表 轉變為 紅黑樹，紅黑樹最壞情況下的時間複雜度為O(logn)。以此提高查找效率。

4.

問：HashMap的容量為什麼一定要是2的n次方？

答：

因為調用put(K key, V value)操作添加key-value鍵值對時，具體確定此元素的位置是通過hash值%模上雜湊表Node[] table的長度hash % length計算的。但是"模"運算的消耗相對較大，通過位運算h & (length-1)也可以得到取模後的存放位置，而位運算的運行效率高，但只有length的長度是2的n次方時，h & (length-1)才等價於h % length
。

而且當陣列長度為2的n次冪的時候，不同的key算出的index相同的幾率較小，那麼資料在陣列上分佈就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。

例子：

hash & (length-1)運算過程

上圖中，左邊兩組的陣列長度是16（2的4次方），右邊兩組的陣列長度是15。兩組的hash值均為8和9。

當陣列長度是15時，當它們和1110進行&與運算（相同為1，不同為0）時，計算的結果都是1000
，所以他們都會存放在相同的位置table[8]中，這樣就發生了hash衝突，那麼查詢時就要遍歷鏈表，逐一比較hash
值，降低了查詢的效率。

同時，我們可以發現，當陣列長度為15的時候，hash值均會與14（1110）進行&與運算，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，陣列可以使用的位置比陣列長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率。

所以，HashMap的容量是2的n次方，有利於提高計算元素存放位置時的效率，也降低了hash衝突的幾率。因此，我們使用HashMap存儲大量資料的時候，最好先預先指定容器的大小為2的n次方，即使我們不指定為2的n次方，HashMap
也會把容器的大小設置成最接近設置數的2的n次方，如，設置HashMap的大小為 7 ，則HashMap會將容器大小設置成最接近7的一個2的n次方數，此值為 8 。

示例代碼：

/** * 返回一個比指定數cap大的，並且大小是2的n次方的數 * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

5.

問：HashMap的負載因數是什麼，有什麼作用？

答：負載因數表示雜湊表空間的使用程度（或者說是雜湊表空間的利用率）。

例子如下：

底層雜湊表Node[] table的容量大小capacity為16，負載因數load factor為0.75，則當存儲的元素個數size = capacity 16 * load factor 0.75等於 12 時，則會觸發HashMap的擴容機制，調用resize()方法進行擴容。

當負載因數越大，則HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發生hash碰撞的幾率就會加大，從而鏈表就會拉長，此時的查詢效率就會降低。

當負載因數越小，則鏈表中的資料量就越稀疏，此時會對空間造成浪費，但是此時查詢效率高。

我們可以在創建HashMap時根據實際需要適當地調整load factor的值；如果程式比較關心空間開銷、記憶體比較緊張，可以適當地增加負載因數；如果程式比較關心時間開銷，記憶體比較寬裕則可以適當的減少負載因數。通常情況下，預設負載因數 (0.75) 在時間和空間成本上尋求一種折衷，程式師無需改變負載因數的值。

因此，如果我們在初始化HashMap時，就預估知道需要裝載key-value鍵值對的容量size，我們可以通過size / load factor計算出我們需要初始化的容量大小initialCapacity，這樣就可以避免HashMap因為存放的元素達到閾值threshold而頻繁調用resize()方法進行擴容。從而保證了較好的性能。

6.

問：您能說說HashMap和HashTable的區別嗎？

答：HashMap和HashTable有如下區別：

1）容器整體結構：

2） 容量設定與擴容機制：

3） 散列分佈方式（計算存儲位置）：

HashMap是先將key鍵的hashCode經過擾動函數擾動後得到hash值，然後再利用hash & (length - 1)的方式代替取模，得到元素的存儲位置。

Hashtable則是除留餘數法進行計算存儲位置的（因為其預設容量也不是2的n次方。所以也無法用位運算替代模運算），int index = (hash & 0x7FFFFFFF) % tab.length;。

由於HashMap的容器容量一定是2的n次方，所以能使用hash & (length - 1)的方式代替取模的方式計算元素的位置提高運算效率，但Hashtable的容器容量不一定是2的n次方，所以不能使用此運算方式代替。

4）執行緒安全（最重要）：

HashMap不是執行緒安全，如果想執行緒安全，可以通過調用synchronizedMap(Map m)使其執行緒安全。但是使用時的運行效率會下降，所以建議使用ConcurrentHashMap容器以此達到執行緒安全。

Hashtable則是執行緒安全的，每個操作方法前都有synchronized修飾使其同步，但運行效率也不高，所以還是建議使用容器以此達到執行緒安全。

因此，Hashtable是一個遺留容器，如果我們不需要執行緒同步，則建議使用HashMap，如果需要執行緒同步，則建議使用ConcurrentHashMap。

7.

問：您說HashMap不是執行緒安全的，那如果多執行緒下，它是如何處理的？並且什麼情況下會發生執行緒不安全的情況？

答：

HashMap不是執行緒安全的，如果多個執行緒同時對同一個HashMap更改資料的話，會導致資料不一致或者資料污染。如果出現執行緒不安全的操作時，HashMap會盡可能的拋出ConcurrentModificationException防止資料異常，當我們在對一個HashMap進行遍歷時，在遍歷期間，我們是不能對HashMap進行添加，刪除等更改資料的操作的，否則也會拋出ConcurrentModificationException異常，此為fail-fast（快速失敗）機制。從源碼上分析，我們在put,remove
等更改HashMap資料時，都會導致modCount的改變，當expectedModCount != modCount時，則拋出ConcurrentModificationException。如果想要執行緒安全，可以考慮使用ConcurrentHashMap。

而且，在多執行緒下操作HashMap，由於存在擴容機制，當HashMap調用resize()進行自動擴容時，可能會導致閉環的發生。限於篇幅，我暫不帶著大家一起去分析resize()方法導致閉環發生的現象造成原因了，遲點有空我會再補充上去，請見諒，大家可以參考如下文章：

8.

問：我們在使用HashMap時，選取什麼物件作為key鍵比較好，為什麼？

答：

可變對象：指創建後自身狀態能改變的物件。換句話說，可變物件是該物件在創建後它的雜湊值可能被改變。

我們在使用HashMap時，最好選擇不可變物件作為key。例如String，Integer等不可變類型作為key
是非常明智的。如果key物件是可變的，那麼key的雜湊值就可能改變。在HashMap中可變物件作為Key會造成資料丟失。因為我們再進行hash & (length - 1)取模運算計算位置查找對應元素時，位置可能已經發生改變，導致資料丟失。

總結

HashMap是基於Map介面實現的一種鍵-值對的存儲結構，允許null值，同時非有序，非同步(即執行緒不安全)。HashMap的底層實現是陣列 + 鏈表 + 紅黑樹（JDK1.8增加了紅黑樹部分）。

HashMap定位元素位置是通過鍵key經過擾動函數擾動後得到hash值，然後再通過hash & (length - 1)代替取模的方式進行元素定位的。

HashMap是使用鏈位址法解決hash衝突的，當有衝突元素放進來時，會將此元素插入至此位置鏈表的最後一位，形成單鏈表。當存在位置的鏈表長度 大於等於 8 時，HashMap會將鏈表 轉變為 紅黑樹，以此提高查找效率。

HashMap的容量是2的n次方，有利於提高計算元素存放位置時的效率，也降低了hash衝突的幾率。因此，我們使用HashMap。存儲大量資料的時候，最好先預先指定容器的大小為2的n次方，即使我們不指定為2的n次方，HashMap也會把容器的大小設置成最接近設置數的2的n次方，如，設置HashMap的大小為 7 ，則HashMap會將容器大小設置成最接近7的一個2的n次方數，此值為 8 。

HashMap的負載因數表示雜湊表空間的使用程度（或者說是雜湊表空間的利用率）。當負載因數越大，則HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發生hash碰撞的幾率就會加大，從而鏈表就會拉長，此時的查詢效率就會降低。當負載因數越小， 則鏈表中的資料量就越稀疏，此時會對空間造成浪費，但是此時查詢效率高。

HashMap不是執行緒安全的，Hashtable則是執行緒安全的。但Hashtable是一個遺留容器，如果我們不需要執行緒同步，則建議使用HashMap，如果需要執行緒同步，則建議使用ConcurrentHashMap。

在多執行緒下操作HashMap，由於存在擴容機制，當HashMap調用resize()進行自動擴容時，可能會導致閉環的發生。

我們在使用HashMap時，最好選擇不可變物件作為key。例如String，Integer等不可變類型作為key是非常明智的。

由於最近工作較忙，也有拖延症發作的問題，所以文章遲遲未能完成發佈，現時完成的文章其實對我而言，也不算太好，但還是打算先發出來讓大家看看，一起學習學習，看有什麼不好的地方，我再慢慢改進，如果此文對你有幫助，請給個贊，謝謝大家。

上一篇：Dior總裁合影趙麗穎baby，手的位置有深意，網友：舉動代表人品
同類文章
精品文章
Next Article
喜欢就按个赞吧!!!
点击关闭提示