面試專題-刨根問底篇

1.HashMap底層原理

1.1.HashMap概述

HashMap是基于哈希表的Map接口的非同步實作。此實作提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特别是它不保證該順序恒久不變。

1.2.HashMap的資料結構

HashMap實際上是一個“數組+連結清單+紅黑樹”的資料結構

1.3.HashMap的存取實作：

1.8之前的

當我們往HashMap中put元素的時候，先根據key的hashCode重新計算hash值，根據hash值得到這個元素在數組中的位置（即下标），如果數組該位置上已經存放有其他元素了，那麼在這個位置上的元素将以連結清單的形式存放，新加入的放在鍊頭，最先加入的放在鍊尾。如果數組該位置上沒有元素，就直接将該元素放到此數組中的該位置上。

1.8

put():

1. 根據key計算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)；
2. 根據key.hash計算得到桶數組的索引index = key.hash & (table.length - 1)，這樣就找到該key的存放位置了：
① 如果該位置沒有資料，用該資料新生成一個節點儲存新資料，傳回null；
② 如果該位置有資料是一個紅黑樹，那麼執行相應的插入 / 更新操作
③ 如果該位置有資料是一個連結清單，分兩種情況一是該連結清單沒有這個節點，另一個是該連結清單上有這個節點，注意這裡判斷的依據是key.hash是否一樣： 如果該連結清單沒有這個節點，那麼采用尾插法新增節點儲存新資料，傳回null； 如果該連結清單已經有這個節點了，那麼找到該節點并更新新資料，傳回老資料。 注意： HashMap的put會傳回key的上一次儲存的資料。      

get():

計算需擷取資料的hash值（計算過程跟put一樣），計算存放在數組table中的位置（計算過程跟put一樣），然後依次在數組，紅黑樹，連結清單中查找（通過equals（）判斷），最後再判斷擷取的資料是否為空，若為空傳回null否則傳回該資料

1.4.樹化與還原

• 哈希表的最小樹形化容量
• 當哈希表中的容量大于這個值時（64），表中的桶才能進行樹形化
• 否則桶内元素太多時會擴容，而不是樹形化
• 為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
• 一個桶的樹化門檻值
• 當桶中元素個數超過這個值時(8)，需要使用紅黑樹節點替換連結清單節點
• 這個值必須為 8，要不然頻繁轉換效率也不高
• 一個樹的連結清單還原門檻值
• 當擴容時，桶中元素個數小于這個值（6），就會把樹形的桶元素 還原（切分）為連結清單結構
• 這個值應該比上面那個小，至少為 6，避免頻繁轉換

條件1. 如果目前桶數組為null或者桶數組的長度 < MIN_TREEIFY_CAPACITY（64），則進行擴容處理.

條件2. 當不滿足條件1的時候則将桶中連結清單内的元素轉換成紅黑樹！！！

1.5.擴容機制的實作

1. 擴容(resize)就是重新計算容量。當向HashMap對象裡不停的添加元素，而HashMap對象内部的桶數組無法裝載更多的元素時，HashMap對象就需要擴大桶數組的長度，以便能裝入更多的元素。

2. capacity 就是數組的長度/大小，loadFactor 是這個數組填滿程度的最大比比例。 

3. size表示目前HashMap中已經儲存的Node<key,value>的數量，包括桶數組和連結清單 / 紅黑樹中的的Node<key,value>。

4. threshold表示擴容的臨界值，如果size大于這個值，則必需調用resize()方法進行擴容。 

5. 在jdk1.7及以前，threshold = capacity * loadFactor，其中 capacity 為桶數組的長度。 這裡需要說明一點，預設負載因子0.75是是對空間和時間(縱向橫向)效率的一個平衡選擇，建議大家不要修改。 jdk1.8對threshold值進行了改進，通過一系列位移操作算法最後得到一個power of two size的值      

1.6.什麼時候擴容

當向容器添加元素的時候，會判斷目前容器的元素個數，如果大于等于門檻值—即目前數組的長度乘以加載因子的值的時候，就要自動擴容啦。

擴容必須滿足兩個條件：

1、 存放新值的時候   目前已有元素的個數  (size) 必須大于等于門檻值
2、 存放新值的時候目前存放資料發生hash碰撞（目前key計算的hash值換算出來的數組下标位置已經存在值）      

//如果計算的哈希位置有值（及hash沖突），且key值一樣，則覆寫原值value，并傳回原值value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
　　　V oldValue = e.value;
　　  e.value = value;
　　　e.recordAccess(this);
　　　return oldValue;
}      

resize()方法： 該函數有2種使用情況

1.初始化哈希表 
2.目前數組容量過小，需擴容      

1.6.擴容過程

插入鍵值對時發現容量不足，調用resize（）方法方法，

1.首先進行異常情況的判斷，如是否需要初始化，二是若目前容量》最大值則不擴容，

2.然後根據新容量（是就容量的2倍）建立數組，将舊數組上的資料（鍵值對）轉移到新的數組中，這裡包括：（周遊舊數組的每個元素，重新計算每個資料在數組中的存放位置（原位置或者原位置+舊容量），将舊數組上的每個資料逐個轉移到新數組中，這裡采用的是尾插法。）

3.新數組table引用到HashMap的table屬性上

4.最後重新設定擴容阙值，此時哈希表table=擴容後（2倍）&轉移了舊資料的新table      

2.HashSet底層原理

2.1.HashSet概述

HashSet實作Set接口，由哈希表（實際上是一個HashMap執行個體）支援。它不保證set 的疊代順序；特别是它不保證該順序恒久不變。此類允許使用null元素。

2.2.HashSet的實作

對于HashSet而言，它是基于HashMap實作的，HashSet底層使用HashMap來儲存所有元素，是以HashSet 的實作比較簡單，相關HashSet的操作，基本上都是直接調用底層HashMap的相關方法來完成， （實際底層會初始化一個空的HashMap，并使用預設初始容量為16和加載因子0.75。）

對于HashSet中儲存的對象，請注意正确重寫其equals和hashCode方法，以保證放入的對象的唯一性。

2.3.插入

當有新值加入時，底層的HashMap會判斷Key值是否存在，如果不存在，則插入新值，同時這個插入的細節會依照HashMap插入細節；如果存在就不插入

3.ConcurrentHashMap的工作原理

變化：

ConcurrentHashMap的JDK8與JDK7版本的并發實作相比，最大的差別在于JDK8的鎖粒度更細，理想情況下talbe數組元素的大小就是其支援并發的最大個數      

實作：

改進一：取消segments字段，直接采用transient volatile HashEntry<K,V>[] table儲存資料，采用table數組元素作為鎖，進而實作了對每一行資料進行加鎖，進一步減少并發沖突的機率。      

改進二：将原先table數組＋單向連結清單的資料結構，變更為table數組＋單向連結清單＋紅黑樹的結構。對于hash表來說，最核心的能力在于将key hash之後能均勻的分布在數組中。      

JDK1.8的實作已經摒棄了Segment的概念，而是直接用Node數組+連結清單+紅黑樹的資料結構來實作，并發控制使用Synchronized和CAS來操作，整個看起來就像是優化過且線程安全的HashMap，雖然在JDK1.8中還能看到Segment的資料結構，但是已經簡化了屬性，隻是為了相容舊版本。