什么？HashMap竟然也有懶加載？
作者：帥氣的小飯飯
前幾天H同學和我聊了下去谷歌的面試經驗，令我詫異的是，沒想到谷歌也問集合之后，我便覺得需要再整理一波集合相關的了。
前幾天H同學和我聊了下去谷歌的面試經驗，令我詫異的是，沒想到谷歌也問集合之后，我便覺得需要再整理一波集合相關的了。
看文章前可以先看看以下高頻考點，如果覺得莫得問題，可以直接跳過該篇文章了，不用浪費時間。
- new HashMap() 和 new HashMap(int initialCapacity) ，具體有什么區別?
- HashMap中的數據多于多少個時才會進行擴容?
- HashMap中的鏈表結構什么時候轉成紅黑樹?一定會轉嗎?
- 紅黑樹結構又什么時候才會轉回鏈表?
- 說說看HashMap的懶加載?負載因子的作用?
特征解析
為了搞清楚一個概念，這篇文章引入竹籃和雞蛋的概念，緩存的數據就是雞蛋，而節點就是竹籃，HashMap底層是一個竹籃數組，每個竹籃是一個鏈表或者紅黑樹的結構，每個竹籃也可以放多個雞蛋，因此其實可以當成二維數組來看待，只是在這里的第二維數組是一個鏈表或者紅黑樹，至于這個竹籃的結構是鏈表還是紅黑樹，就看竹籃內的的雞蛋個數有多少，并且鏈表和紅黑樹之間可以進行轉換。
通過散列函數將雞蛋定位到表中的具體竹籃，以提升查詢速度，其底層用于存放數據的數組也叫散列表。所謂散列函數，簡單來說就是將一個無限大的集合(在 HashMap 中，key值是一個無限大集合)，經過 hash 運算取模，均勻的分布在一個有限的集合(我們定義的哈希表容量，比如長度 16 的數組)
源碼解析
成員變量和常量
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認的初始容量，預計所有竹籃累計可以放16個雞蛋
- static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量，所有竹籃最多可以放多少個雞蛋
- static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認加載因子，裝逼用，一般都會在應用探討bb的時候提一嘴
- static final int TREEIFY_THRESHOLD = 8; // 單個竹籃放的雞蛋個數超過8轉紅黑樹
- static final int UNTREEIFY_THRESHOLD = 6; // 單個竹籃放的雞蛋個數小于6則轉鏈表
- static final int MIN_TREEIFY_CAPACITY = 64; // 如果竹籃個數小于64個，會先進行擴容，而不會鏈表轉紅黑樹
- transient Node<K,V>[] table; // 哈希表數組，存儲數據的地方，每個竹籃結構可能為鏈表或者紅黑樹，總是2的冪次倍
- transient Set<Map.Entry<K,V>> entrySet; // 存放具體元素的集合，可用于遍歷Map
- transient int size; // 總的雞蛋個數
- transient int modCount; // 插入刪除元素，modCount++,用于記錄改變次數
- int threshold; // 容量閾值，所有竹籃允許緩存雞蛋的個數，超過這個值需要擴容，默認為0，看看后續是如何變化的，對理解擴容那塊很重要
- final float loadFactor; // 加載因子，能夠權衡時間復雜度和空間復雜度
筆試or面試需要記住幾個死記硬背的點，那就是：hashmap的默認初始容量為16，加載因子是0.75，鏈表長過8則轉紅黑樹，小于6則轉鏈表，容量低于64則先擴容，而不會鏈表轉紅黑樹。
看看構造方法
HashMap有四個構造方法，這里只列出我們常用的兩個
- 第一個是默認構造方法，我們不指定默認所有竹籃累計可以放16個雞蛋
- 第二個是指定初始容量，也是我們比較推薦的做法，根據需要設置大小，避免后面resize擴容開銷
日常開發中如果知道大小，我們都會用第二種，可以避免resize擴容開銷，新手開發經常會直接用第一種，一般我review代碼看到都會直接打回改，然后告訴他們為啥，想想看，如果你已經知道這個map容器要裝的元素是100個，你還不指定初始容量，那么就會導致在第一次put數據的時候進行擴容，此時第一次擴容因為沒有初始容量，計算出的容量閾值為默認大小16，16*加載因子0.75f就是12，之后當你繼續put值超過12個的時候又會繼續擴容，第二次擴容后容量閾值為24，循環剛剛的過程直到容量閾值大于100，而如果指定了默認大小則第一次擴容就夠用了，不用走后面那么多次擴容，可以節省性能;
其次是命名也要注意下，最好是直接用Map結合，比如xxxMap，這是規范。
擴容
我們先回顧下上面的一個成員變量threshold
「int threshold; // 容量閾值，所有竹籃允許放入雞蛋的個數」
ok了，繼續講擴容，擴容分為多種情況
- 如果我們使用了無參構造方法，可以看到
其中并未對成員變量threshold容量閾值進行初始化，反調threshold賦值的地方可以看到在put第一個元素的時候會調用resize方法，該方法有做了容量閾值的計算，計算方式為：DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY，也就是默認的加載因子 * 默認容量，即 0.75f * 16，即12
- 如果指定了初始容量
可以看到初始容量閾值的計算公式是：
這么一坨東西是啥呢，其實就是一個算法，看不懂也莫得關系，畢竟我也看不懂，記住就好，這個算法其實就是返回大于輸入參數且最近的2的整數次冪的數，比如設置的初始容量為10，那么這個算法則返回16。
但是，到了這里其實也并沒有分配好數組，可以看到resize方法，其實也是在put的時候才會真正進行數組的分配，也就是懶加載了。
- 二次擴容，最終都會走向resize方法，每次擴容量都會是原先的2倍。
我們可以看看resize方法
- final Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap > 0) {
- // 如果竹籃個數大于最大容量，則將容量閾值設置成int的最大值
- if (oldCap >= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- // 否則新閾值為舊閾值兩倍
- else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- oldCap >= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr << 1;
- }
- else if (oldThr > 0)
- newCap = oldThr;
- else {
- // 只有默認無參構造方法才會走到這個分支，閾值為默認算法，容量 * 0.75
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- @SuppressWarnings({"rawtypes","unchecked"})
- // 真正進行擴容的地方，也是凌亂的算法我大致講講，首先要創建一個新的哈希表，其容量為上面計算出來的
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- table = newTab;
- if (oldTab != null) {
- // 輪詢操作，對所有元素重哈希
- for (int j = 0; j < oldCap; ++j) {
- Node<K,V> e;
- if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- else if (e instanceof TreeNode)
- // 竹籃內內的雞蛋數據重hash，紅黑樹轉鏈表的地方，內部處理主要是當竹籃內的雞蛋個數小于等于6時，樹結構會還原成鏈表
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- else { // preserve order
- // 略：鏈表元素重hash
- }
- }
- }
- }
- return newTab;
- }
HashMap擴容可以分為三種：
- 使用默認構造方法初始化HashMap，從前文可以知道HashMap在一開始初始化的時候thershold容量閾值為0，默認值DEFAULT_INITIAL_CAPACITY也就是16，DEFAULT_LOAD_FACTOR為0.75f，因此在第一次put數據的時候會進行擴容，擴容后的容量閾值threshold為DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12;
- 指定初始容量的構造方法初始化HashMap，可以看到在初始化的時候便通過tableSizeFor進行計算，也就是返回大于輸入參數且最近的2的整數次冪的數;
- 當HashMap不是第一次擴容的時候，那么每次擴容的容量以及容量閾值threshold為原有的兩倍。
hash計算
HashCode是啥其實大家都知道，無非就是用來確定對象在HashMap中的存儲地址，目的也很簡單，為了快，貌似除了了那方面，其他都是越快越好，比如賺錢。
元素插入
我們先回顧下上面的一個成員變量table
「itransient Node<K,V>[] table; // 哈希表數組，存儲數據的地方，每個竹籃結構可能為鏈表或者紅黑樹，總是2的冪次倍」
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- // 這里如果發現動態數組為null則會初始化數組。
- if ((tab = table) == null || (n = tab.length) == 0)
- // 第一次放入值時會在這里初始化數組，并且通過resize方法進行擴容
- n = (tab = resize()).length;
- // 通過hash發現要放入的雞蛋的數組位置為null，說明沒有hash沖突，則直接把該雞蛋放在這里即可
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- // 如果要放入的位置已經有該雞蛋了
- Node<K,V> e; K k;
- // 判斷竹籃的第一個雞蛋否和新元素key以及hash值都完全一致，如果是則不用看代碼都知道進行覆蓋，覆蓋的邏輯在后面
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- // 確認是否為樹解點
- else if (p instanceof TreeNode)
- // 如果是的話則按照紅黑樹方法放入竹籃內
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {
- // 說明不是，則是列表，按照列表方法放入
- for (int binCount = 0; ; ++binCount) {
- // 一直向下取，直到找到空的位置
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- // 判斷鏈表長度是否大于8，這里其實減后為7，判斷的是binCount,但是因為插入了一個新節點了，所以其實為8
- if (binCount >= TREEIFY_THRESHOLD - 1)
- // 則將列表轉為紅黑樹，所以記住大于8的時候會轉成紅黑樹
- treeifyBin(tab, hash);
- break;
- }
- // 已經找到了hash值和key一樣的，則直接break，不用找了，同樣在后面進行覆蓋
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- // 覆蓋操作在這里，新值和舊值的key完全相同，進行覆蓋操作
- if (e != null) {
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- // 訪問后回調
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- // 當map中所有的雞蛋個數大于容量閾值時則進行擴容，二次擴容如上面所說，也就是兩倍
- if (++size > threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- // 這里如果發現動態數組為null則會初始化數組。
- if ((tab = table) == null || (n = tab.length) == 0)
- // 第一次放入值時會在這里初始化數組，并且通過resize方法進行擴容
- n = (tab = resize()).length;
- // 通過hash發現要放入的雞蛋的數組位置為null，說明沒有hash沖突，則直接把該雞蛋放在這里即可
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- // 如果要放入的位置已經有該雞蛋了
- Node<K,V> e; K k;
- // 判斷竹籃的第一個雞蛋否和新元素key以及hash值都完全一致，如果是則不用看代碼都知道進行覆蓋，覆蓋的邏輯在后面
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- // 確認是否為樹解點
- else if (p instanceof TreeNode)
- // 如果是的話則按照紅黑樹方法放入竹籃內
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {
- // 說明不是，則是列表，按照列表方法放入
- for (int binCount = 0; ; ++binCount) {
- // 一直向下取，直到找到空的位置
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- // 判斷鏈表長度是否大于8，這里其實減后為7，判斷的是binCount,但是因為插入了一個新節點了，所以其實為8
- if (binCount >= TREEIFY_THRESHOLD - 1)
- // 則將列表轉為紅黑樹，所以記住大于8的時候會轉成紅黑樹
- treeifyBin(tab, hash);
- break;
- }
- // 已經找到了hash值和key一樣的，則直接break，不用找了，同樣在后面進行覆蓋
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- // 覆蓋操作在這里，新值和舊值的key完全相同，進行覆蓋操作
- if (e != null) {
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- // 訪問后回調
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- // 當map中所有的雞蛋個數大于容量閾值時則進行擴容，二次擴容如上面所說，也就是兩倍
- if (++size > threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
- final void treeifyBin(Node<K,V>[] tab, int hash) {
- int n, index; Node<K,V> e;
- // 當tab為空或者竹籃個數小于64個，會先進行擴容，而不會鏈表轉紅黑樹
- 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);
- }
- }
put總體流程匯總如下：
羅列幾個該注意的點，分別是：
- HashMap中緩存數據的數組table，我們可以看到初始化的時候默認是null，是在第一次put數據的時候才進行初始化的，這也是所謂的懶加載，記住了，不要每次提HashMap的懶加載機制都二臉懵逼了。
- HashMap中單個竹籃存放的雞蛋個數大于8，并且當竹籃個數大于64個的時候則將列表轉為紅黑樹，否則進行擴容。
- 每次put數據時當map中存放的所有雞蛋個數大于容量閾值時則進行擴容，并且是先put數據，再擴容。
元素查詢
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- if ((tab = table) != null && (n = tab.length) > 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- // 如果計算hash值和第一個節點的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)
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
- do {
- //如果hash值相同，key不同，則遍歷鏈表找到相同的key，返回
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
查找這里，總結下來流程便是：
- 根據hash值從竹籃數組內找到竹籃，判斷頭節點key值與當前key相同，直接返回
- 如果該竹籃為TreeNode節點，以紅黑樹方式查找
- 如果不是則循環遍歷鏈表，直到查到對應的key相同
元素刪除
- final Node<K,V> removeNode(int hash, Object key, Object value,
- boolean matchValue, boolean movable) {
- Node<K,V>[] tab; Node<K,V> p; int n, index;
- if ((tab = table) != null && (n = tab.length) > 0 &&
- (p = tab[index = (n - 1) & hash]) != null) {
- Node<K,V> node = null, e; K k; V v;
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- node = p;
- else if ((e = p.next) != null) {
- //紅黑樹的查找方式
- if (p instanceof TreeNode)
- node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
- else {
- //鏈表遍歷查找方式
- do {
- if (e.hash == hash &&
- ((k = e.key) == key ||
- (key != null && key.equals(k)))) {
- node = e;
- break;
- }
- p = e;
- } while ((e = e.next) != null);
- }
- }
- //刪除node
- if (node != null && (!matchValue || (v = node.value) == value ||
- (value != null && value.equals(v)))) {
- //如果node為紅黑樹結點，采用紅黑樹刪除方式
- if (node instanceof TreeNode)
- ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
- // 如果是鏈表并且node為頭結點，當前數組下標元素直接替換為next
- else if (node == p)
- tab[index] = node.next;
- else
- //鏈表非頭元素刪除方式
- p.next = node.next;
- ++modCount;
- --size;
- afterNodeRemoval(node);
- return node;
- }
- }
- return null;
- }
刪除操作很簡單，先根據hash找到對應雞蛋，然后根據不同類型的節點進行刪除，沒什么注意的點，如果有，那就是如果是鏈表表頭的話，則需要將下一個節點賦值為表頭。
本文轉載自微信公眾號「稀飯下雪」，可以通過以下二維碼關注。轉載本文請聯系稀飯下雪公眾號。
責任編輯：姜華
來源：
稀飯下雪
