5月安卓手機好評榜：魅族20 Pro奪冠
性能榜和性價比榜之后，我們來看最后的安卓手機好評榜，數據來源安兔兔評測，收集時間2023年5月1日至5月31日，僅限國內市場。第一名：魅族20 Pro好評率：97.50%不得不感慨魅族老品牌還
HashMap的實現原理是什么？
HashMap是一個高頻的面試題，那么如何才能回答的比較合適呢？
以下是jdk1.7與jdk1.8中hashmap的區別：
概括下可以從以下幾個方面來回答：
HashMap是一個基于Hash散列技術，以鍵值對形式存儲的數據結構。
JDK 1.8 之前的 HashMap 使用的數組+鏈表的結構，插入時使用頭插法。
JDK 1.8 之后的 HashMap 使用的數組+鏈表/紅黑樹的結構，插入時使用頭插法。
JDK 1.8 之前的 HashMap 使用的是拉鏈法（Chaining）作為沖突解決策略。
JDK 1.8 引入了紅黑樹作為替代鏈表的沖突解決策略。
當哈希表中的元素數量超過一定閾值時，HashMap 會自動進行擴容，以保持較低的負載因子，從而提高性能。
可以從以下幾個方面來回答：
HashMap是一個基于Hash散列技術，以鍵值對形式存儲的數據結構。
HashMap內部維護一個數組，這個數組的每個位置都是一個鏈表或紅黑樹的頭節點。這些節點用于存儲鍵值對。
jdk1.8之前 | jdk1.8之后(含1.8) | |
結構 | 數組+鏈表 | 數組+鏈表/紅黑樹 |
數組類型 | Entry數組 | Node數組 |
JDK1.8之前的 HashMap 由 Entry 數組組成，Entry 類是 HashMap 中存儲鍵值對的類。Entry 類包含 key、value 和 next 三個屬性。key 是鍵，value 是值，next 是指向下一個 Entry 對象的指針，出現 hash 沖突存放到鏈表中。具體源碼是通過 put() 方法實現的。
public V put(K key, V value) { // 如果哈希表為空，則對其進行申請數組空間 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 如果 key 為 null，則將其放入 null 鍵的特殊位置 if (key == null) { return putForNullKey(value); } // 計算 key 的哈希值 int hash = hash(key); // 根據哈希值和哈希表的長度計算索引位置 int i = indexFor(hash, table.length); // 遍歷索引位置上的鏈表，尋找 key for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 如果 key 相同，則更新 value 并返回舊值 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果 key 不存在，則添加一個新的鏈表成員 modCount++; addEntry(hash, key, value, i); return null;}put() 方法首先計算 key 的 hash 值，然后定位到數組索引位置。如果數組索引位置上已經存在 Entry 對象，則判斷 key 是否相同。如果相同則直接覆蓋value，否則添加到鏈表中。如果數組索引位置上不存在 Entry 對象，則直接添加到數組中。
static class Entry<K, V> implements Map.Entry<K, V> { final int hash; final K key; V value; Entry<K, V> next; Entry(int hash, K key, V value) { this.hash = hash; this.key = key; this.value = value; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Entry<?, ?> entry = (Entry<?, ?>) o; return hash == entry.hash && Objects.equals(key, entry.key) && Objects.equals(value, entry.value); } @Override public int hashCode() { return Objects.hash(hash, key, value); } @Override public String toString() { return key + "=" + value; }}鏈表的每個元素是一個 Entry 對象，Entry 對象包含 key、value、hash 和 next 四個屬性。key 是鍵，value 是值，hash 是 key 的 hash 值，next 是指向下一個 Entry 對象的指針。
當 HashMap 出現 hash 沖突時，會將新的 Entry 對象添加到鏈表的尾部。鏈表的查詢性能較差，當鏈表長度過長時，會影響 HashMap 的查詢性能。
關鍵一：
先通過indexFor下標定位到的數組元素位置，再遍歷這個元素(鏈表)，依次和鏈表中的key比較，如果 key 相同就直接覆蓋，不同就采用頭插法插入元素。
關鍵二：
頭插法的實現主要涉及到兩個方法：addEntry 和 createEntry。addEntry 方法用于判斷是否需要擴容，并調用 createEntry 方法將鍵值對存入數組中。createEntry 方法用于創建一個新的節點，并將其 next 屬性指向原來的鏈表頭節點，然后將新節點賦值給數組對應位置，完成頭插法。
插入元素使用createEntry，新元素會的next指向table[bucketIndex]也就是鏈表的頭節點。
JDK1.8的 HashMap 由 Node 數組組成，Node 類是 HashMap 中存儲鍵值對的類。Node 類包含 key、value、hash、next 和 prev 五個屬性。key 是鍵，value 是值，hash 是 key 的 hash 值，next 是指向下一個 Node 對象的指針，prev 是指向前一個 Node 對象的指針。
JDK1.8之后的 HashMap 由 Node 數組組成，出現 hash 沖突存放到鏈表中同時滿足條件的情況下會生成紅黑樹。具體源碼是通過 put() 方法實現的。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 獲取哈希表 Node<K,V>[] tab = table; // 如果哈希表為空或長度為0，則進行擴容 if (tab == null || tab.length == 0) { tab = resize(); } // 計算索引位置 int n = tab.length; int i = (n - 1) & hash; // 如果索引位置上的節點為空，則添加一個新的節點 Node<K,V> p = tab[i]; if (p == null) { tab[i] = newNode(hash, key, value, null); } else { // 如果索引位置上的節點存在，則遍歷鏈表，尋找 key 相同的節點 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { e = p; } else if (p instanceof TreeNode) { // 如果索引位置上的節點是紅黑樹節點，則調用紅黑樹的 putTreeVal() 方法添加新的節點 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); } else { // 如果索引位置上的節點是鏈表節點，則遍歷鏈表，尋找 key 相同的節點 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 如果沒有找到 key 相同的節點，則在鏈表尾部添加一個新的節點 p.next = newNode(hash, key, value, null); // 如果鏈表長度超過閾值，則將鏈表轉換為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); } break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { // 如果找到 key 相同的節點，則停止遍歷 break; } p = e; } } if (e != null) { // 找到 key 相同的節點 // 獲取舊值 V oldValue = e.value; // 如果只有 key 不存在才添加新的節點，則僅當舊值為 null 時才更新值 if (!onlyIfAbsent || oldValue == null) { e.value = value; } // 調用 afterNodeAccess() 方法更新節點的訪問時間 afterNodeAccess(e); return oldValue; } } // 添加新的節點后，更新 HashMap 的大小和修改次數 ++modCount; if (++size > threshold) { resize(); } // 調用 afterNodeInsertion() 方法更新節點的插入狀態 afterNodeInsertion(evict); return null;}put() 方法在添加元素時，會先判斷數組索引位置上是否已經存在 Node 對象。如果已經存在，則判斷 key 是否相同。如果相同則更新 value，否則添加到鏈表中。
如果鏈表長度超過閾值，則將鏈表轉換為紅黑樹。閾值的默認值是 8。
treeifyBin() 方法的實現如下：
final void treeifyBin(Node<K,V>[] tab, int hash) { // 如果哈希表為空或長度小于 MIN_TREEIFY_CAPACITY，則進行擴容 int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { resize(); } else if ((e = tab[index = (n - 1) & hash]) != null) { // 獲取索引位置上的節點 TreeNode<K,V> hd = null, tl = null; // 遍歷鏈表，將每個節點轉換為紅黑樹節點 do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) { hd = p; } else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); // 將轉換后的紅黑樹節點添加到哈希表中 if ((tab[index] = hd) != null) { hd.treeify(tab); } }}treeifyBin() 方法首先判斷鏈表的長度是否超過閾值。如果超過閾值，則將鏈表的第一個元素作為紅黑樹的根節點。
然后，將鏈表中的所有元素添加到紅黑樹中。
最后，將紅黑樹的根節點添加到數組中。
這樣，當 HashMap 出現 hash 沖突存放到鏈表中同時滿足條件的情況下，會將鏈表轉換為紅黑樹，提高查詢性能。
當鏈表的節點數量達到閾值(默認為 8 )，執行 treeifyBin 方法。
關鍵二：
進入treeifyBin方法后還有一個邏輯就是當數組長度大于或者等于 64 的情況下，才會執行轉換紅黑樹操作，以減少搜索時間。否則，就是只是對數組擴容。所以鏈表長度大于閾值不是轉為紅黑樹的唯一條件。
關鍵三：
區別于jdk1.7，jdk1.8已經使用了尾插法實現鏈表元素的插入。
主要是因為頭插法在多線程擴容情況下會引起鏈表環。那什么是鏈表環呢？
線程1，第一節點為A，第二節點為B后面就沒有了，遍歷過程為A->B然后B沒有后面節點即遍歷結束。
這時線程1掛起。線程2引發擴容，擴容后為B->A。這時線程1遍歷就會發現A的下一節點是B，會發現遍歷B時B還有后續的節點為A，這樣就出樣鏈表環了。
在 Java 的 HashMap 中，Node 和 Entry 都是用于表示鍵值對的數據結構，但它們在不同版本的 HashMap 中有一些區別：
Node 和 Entry 都用于表示鍵值對，但它們的命名和實現方式在不同的 Java 版本中有所不同。Node 主要用于 JDK 1.8 及之后的 HashMap，而 Entry 主要用于 JDK 1.7 及之前的 HashMap。Node 進一步改進了哈希沖突的處理方式，引入了紅黑樹來提高性能。
JDK 1.8 之前的 HashMap 使用的是拉鏈法（Chaining）作為沖突解決策略。
HashMap 通過 key 的 hashCode 經過擾動函數處理過后得到 hash 值，然后通過 (n - 1) & hash 判斷當前元素存放的位置，如果當前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鏈法解決沖突。以下就是JDK1.7中的hashcode擾動函數。
JDK 1.8 中，HashMap 使用了拉鏈法和紅黑樹兩種沖突解決策略。當鏈表長度超過一定閾值時，會將鏈表轉換為紅黑樹。紅黑樹是一種自平衡二叉樹，具有較高的查詢性能。以下就是JDK1.8中的hashcode擾動函數。
JDK1.8 中的 HashMap 在查詢性能上比 JDK1.7 中的 HashMap 有一定的提升。
以下是 JDK1.7 和 JDK1.8 中 HashMap 解決哈希沖突方法的具體對比：
JDK1.8 中的 HashMap 解決哈希沖突的方法更加靈活，可以適應不同的場景。
當哈希表中的元素數量超過一定閾值時，HashMap 會自動進行擴容，以保持較低的負載因子，從而提高性能。
Java HashMap 使用負載因子來控制擴容。負載因子是指 HashMap 中鍵值對數與 HashMap 容量的比值。
HashMap 的初始容量為 16，負載因子為 0.75。這意味著，當 HashMap 中鍵值對數達到 16 * 0.75 = 12 時，HashMap 就會進行擴容。
HashMap 的擴容方式是將容量擴大為原來的 2 倍。例如，當 HashMap 的容量為 16 時，擴容后容量為 32。
HashMap 擴容的原因是，當 HashMap 的負載因子達到一定值時，HashMap 的查詢性能會下降。這是因為，當 HashMap 的容量較小，并且鍵值對數較多時，會導致哈希沖突的概率增加。
因此，HashMap 會在負載因子達到一定值時進行擴容，以提高查詢性能。
以下是 HashMap 擴容的具體步驟：
本文鏈接：http://www.www897cc.com/showinfo-26-25478-0.htmlHashMap高頻面試題，讓你掌握青銅回答與王者級回答，你值得擁有
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： SpringBoot2.7升級到3.0注意事項及相關變化
下一篇： Python迭代器和生成器的實際應用場景
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號