HashMap

關于hash表的基礎內容，請看文章

【數據結構-查找】3.散列表詳解
【Java自頂向下】HashMap面試題（2021最新版）

頂層應用

public class HashMapTest {public static void main(String[] args) {HashMap<String, String> stringStringHashMap = new HashMap<>();// 1.put存儲鍵值對stringStringHashMap.put("ffideal","宇定");stringStringHashMap.put("床前明月光","疑是地上霜");// 2.get利用key獲取valueString name = stringStringHashMap.get("ffideal");System.out.println(name);// 3.containsKey是否存在某個鍵值if (stringStringHashMap.containsKey("ffideal")) {System.out.println("ffideal存在");} else {System.out.println("ffideal不存在");}// 4.replace修改key-valuestringStringHashMap.replace("ffideal","宇定2");String name3 = stringStringHashMap.get("ffideal");System.out.println(name3);// 5.遍歷HashMap中的鍵值對Set<String> strings = stringStringHashMap.keySet();for (String s: strings) {System.out.println("遍歷數據：" + s);}// 6.clear清空HashMap中的元素stringStringHashMap.clear();Set<String> strings2 = stringStringHashMap.keySet();for (String s: strings2) {System.out.println("清空后的數據" + s);}} }

底層原理

put => key => HashCode => 位置index

get => key => HashCode => 位置index

問：HashMap數組大小初始值是多少？最大是多少？如果為給定初始值，初始大小是多少？

答：16（$2^4$）；$2^{30}$；大于等于參數的最小2的冪次方

private static final int tableSizeFor(int c) {// 傳入32或20int n = c - 1;// n=31或19n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;// 此時n=31或31，最后經過兩次判斷后返回值為32return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

問：HashMap 在 Java 7 與Java 8 中底層的不同？

答：Java 7 中的HashMap的底層是一個數組+鏈表的設計，每個hash值的第一個值放在數組里，之后經過hash運算得到相同的hash值鎖定數組下標，數組中的每一個元素都是一個單向鏈表（碰撞，列表）。

capacity：當前數組容量，始終保持 $2^n$，可以擴容，擴容后數組大小為當前的 2 倍。

loadFactor：負載因子，默認為 0.75。

threshold：擴容的閾值，等于 capacity * loadFactor。

HashMap的數據插入原理

存儲結構的變化

Java 8 中的HashMap的底層是數組+鏈表+紅黑樹的方式實現。

為什么要使用紅黑樹而不使用AVL樹

紅黑樹犧牲了一些查找性能 但其本身并不是完全平衡的二叉樹。因此插入刪除操作效率略高于AVL樹

AVL樹用于自平衡的計算犧牲了插入刪除性能，但是因為最多只有一層的高度差，查詢效率會高一些。

改進的是在數據量較大的情況下（Java8 中，當鏈表中的元素超過了 8 個以后，會將鏈表轉換為紅黑樹）單向鏈表的時間復雜是O(N)，采用紅黑樹將時間復雜度降到O(logN)。

static final int TREEIFY_THRESHOLD = 8;

那么， 如果我們在刪除容器中的元素的時候，刪到多少才使得紅黑樹的存儲結構轉為鏈表呢？答案是6。

static final int UNTREEIFY_THRESHOLD = 6;

也就是說，在JDK8之后，創建HashMap對象=>添加數組中同一個位置元素超過8個=>該位置鏈表轉為紅黑樹=>刪除數組中同一個位置元素少于6個=>該位置紅黑樹轉為列表。

最小樹形化的策略

最小樹形化容量閾值：即 當哈希表中的容量 > 該值時，才允許樹形化鏈表 （即 將鏈表 轉換成紅黑樹）， 否則，若桶內元素太多時，則直接擴容，而不是樹形化。為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD。

也就是說，當數組中某個桶中的元素大于8，數組容量小于64時，使用容量進行兩倍擴容（其實就是用擴容代替鏈表轉紅黑樹操作）。當數組中某個桶中的元素大于8且數組容量大于64時，鏈表轉紅黑樹操作。

hashMap并不是在鏈表元素個數大于8就一定會轉換為紅黑樹，而是先考慮擴容，擴容達到默認限制后才轉換

hashMap的紅黑樹不一定小于等于6的時候就會轉換為鏈表，而是只有在resize的時候才會根據 UNTREEIFY_THRESHOLD（6） 進行轉換

HashMap怎么解決碰撞問題的?

Java中HashMap是利用“拉鏈法”處理HashCode的碰撞問題。

在調用HashMap的put方法或get方法時，都會首先調用hashcode方法，去查找相關的key，當有沖突時，再調用equals方法。

hashMap基于hasing原理，我們通過put和get方法存取對象。當我們將鍵值對傳遞給put方法時，他調用鍵對象的hashCode()方法來計算hashCode，然后找到bucket（哈希桶）位置來存儲對象。

當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。

HashMap使用鏈表來解決碰撞問題，當碰撞發生了，對象將會存儲在鏈表的下一個節點中。hashMap在每個鏈表節點存儲鍵值對對象。當兩個不同的鍵卻有相同的hashCode時，他們會存儲在同一個bucket位置的鏈表中。

鍵對象的equals()來找到鍵值對。

HashMap的一些特點

HashMap的5個特點

HashMap鍵不可重復，值可重復

底層hash表

具有很快的訪問速度，遍歷順序不確定

線程不安全，若需要線程安全則需要使用Collections中的synchronizedMap方法來保障

允許key值為null，value值也為null

一些誤區

問1：是否可以兩個key值為null？

答1：不可以，后者會把前者覆蓋

問2：HashMap插入時，使用頭插法還是尾插法？

答2：在插入時采用尾插法（1.7是頭插法），在并發場景下導致鏈表成環的問題。而在jdk1.8中采用尾插入法，在擴容時會保持鏈表元素原本的順序，就不會出現鏈表成環的問題了。

頭插法和尾插法

頭插法帶來的環狀

一些不足和解決方式

HashMap不是線程安全的.

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以實現線程安全的Map。

HashTable是直接在操作方法上加synchronized關鍵字，鎖住整個數組，粒度比較大。因為synchronized關鍵字每次執行都會調用操作系統的鎖來保證線程安全，也就是每次執行代碼塊，都要涉及 “用戶態” 到 “內核態” 的轉變，十分消耗資源。

Collections.synchronizedMap是使用 Collections集合工具的內部類，通過傳入Map封裝出一個SynchronizedMap對象，內部定義了一個對象鎖，方法內通過對象鎖實現。

ConcurrentHashMap使用分段鎖，降低了鎖粒度，讓并發度大大提高我們一般都會使用HashTable或者ConcurrentHashMap，但是因為前者的并發度的原因基本上沒啥使用場景了，所以存在線程不安全的場景我們都使用的是ConcurrentHashMap。

HashTable我看過他的源碼，很簡單粗暴，直接在方法上鎖，并發度很低，最多同時允許一個線程訪問，ConcurrentHashMap就好很多了，1.7和1.8有較大的不同，不過并發度都比前者好太多了

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

總結

以上是生活随笔為你收集整理的【Java自顶向下】面试官：HashMap源码看过吗？我：看过！面试官：好极了，那么来扒一扒吧！的全部內容，希望文章能夠幫你解決所遇到的問題。

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