Java數(shù)據(jù)結構 之 HashMap 重溫學習
個人能力有限饲窿，暫時不整理溫習 紅黑二叉樹
該篇文章主要講述 HashMap 逾雄、ConcurrentHashMap 部分區(qū)別（從擴容消耗內(nèi)存方面 介紹下ArrayMap）银锻，在文章末尾會簡單的提到 List 部分的面試知識點击纬。
update time 2019年12月09日13:33:53
1. HashMap
這里的HashMap 主要針對 JDK 1.8 版本更振，JDK1.7 沒有引入紅黑樹概念
HashMap 實際上是一個“鏈表散列”的數(shù)據(jù)結構殃饿，即數(shù)組和鏈表的結合體乎芳。它是基于哈希表的 Map 接口的非同步實現(xiàn)奈惑。
數(shù)組：存儲區(qū)間連續(xù)肴甸，占用內(nèi)存嚴重原在，尋址容易庶柿，插入刪除困難浮庐；
鏈表：存儲區(qū)間離散审残，占用內(nèi)存比較寬松搅轿，尋址困難璧坟，插入刪除容易；
Hashmap 綜合應用了這兩種數(shù)據(jù)結構，實現(xiàn)了尋址容易褐澎，插入刪除也容易工三。
效果圖
主要參數(shù)說明
/**
* 主要參數(shù) 同 JDK 1.7
* 即：容量俭正、加載因子掸读、擴容閾值（要求儿惫、范圍均相同）
*/
// 1. 容量（capacity）： 必須是2的冪 & <最大容量（2的30次方）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十進制的2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 = 2的30次方（若傳入的容量過大肾请，將被最大值替換）
// 2. 加載因子(Load factor)：HashMap在其容量自動增加前可達到多滿的一種尺度
final float loadFactor; // 實際加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認加載因子 = 0.75
// 3. 擴容閾值（threshold）：當哈希表的大小 ≥ 擴容閾值時铛铁，就會擴容哈希表（即擴充HashMap的容量）
// a. 擴容 = 對哈希表進行resize操作（即重建內(nèi)部數(shù)據(jù)結構）饵逐，從而哈希表將具有大約兩倍的桶數(shù)
// b. 擴容閾值 = 容量 x 加載因子
int threshold;
// 4. 其他
transient Node<K,V>[] table; // 存儲數(shù)據(jù)的Node類型 數(shù)組梳毙，長度 = 2的冪账锹；數(shù)組的每個元素 = 1個單鏈表
transient int size;// HashMap的大小奸柬，即 HashMap中存儲的鍵值對的數(shù)量
/**
* 與紅黑樹相關的參數(shù)
*/
// 1. 桶的樹化閾值：即 鏈表轉成紅黑樹的閾值廓奕，在存儲數(shù)據(jù)時桌粉，當鏈表長度 > 該值時铃肯，則將鏈表轉換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 2. 桶的鏈表還原閾值：即 紅黑樹轉為鏈表的閾值押逼，當在擴容（resize（））時（此時HashMap的數(shù)據(jù)存儲位置會重新計算）挑格，在重新計算存儲位置后雾消，當原有的紅黑樹內(nèi)數(shù)量 < 6時显歧，則將 紅黑樹轉換成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小樹形化容量閾值：即 當哈希表中的容量 > 該值時士骤，才允許樹形化鏈表 （即 將鏈表 轉換成紅黑樹）
// 否則拷肌，若桶內(nèi)元素太多時巨缘，則直接擴容，而不是樹形化
// 為了避免進行擴容搁骑、樹形化選擇的沖突仲器，這個值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
核心參數(shù)圖解
2. hash() 方法
hash方法其實在java8中也做了優(yōu)化：只向右移動一次使高位移動向低位乏冀，和hash值做 異或處理昼捍，使高位添加到運算 但是由于計算出來的值太大妒茬，hashmap初始大小只有16，所以要和（長度-1）做一次并運算，保留長度內(nèi)的數(shù)據(jù)以此來達到降低key沖突的百分比
測試的運算過程
3. HashMap 的put方法
流程圖如下
（唉 那里都有二叉樹么）
- 判斷鍵值對數(shù)組table[i]是否為空或為null熬丧，否則執(zhí)行resize()進行擴容析蝴，設置容量 闕值等初始化工作闷畸，（注意 若哈希表的數(shù)組tab為空盾沫，則 通過resize() 創(chuàng)建赴精，所以蕾哟，初始化哈希表的時機 = 第1次調(diào)用put函數(shù)時谭确，即調(diào)用resize() 初始化創(chuàng)建）
- 根據(jù)鍵值key計算hash值得到插入的數(shù)組索引i琼富，如果table[i]==null庄新，直接新建節(jié)點添加，轉向第六步出皇，如果table[i]不為空，轉向第三部纱注；
- 判斷table[i]的首個元素是否和key一樣狞贱，如果相同直接覆蓋value瞎嬉，否則轉向第四步氧枣，這里的相同指的是hashCode以及equals便监；
- 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹解藻，如果是紅黑樹螟左，則直接在樹中插入鍵值對胶背，否則轉向第五步；
- 遍歷table[i]窘拯，判斷鏈表長度是否大于8暇番，大于8的話把鏈表轉換為紅黑樹次酌，在紅黑樹中執(zhí)行插入操作，否則進行鏈表的插入操作舆乔；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可岳服；
- 插入成功后，判斷實際存在的鍵值對數(shù)量size是否超過了最大容量threshold希俩，如果超過派阱，進行擴容，然后結束整個流程斜纪。
4. HashMap擴容
hashmap 添加的時候 如果長度沒有大于8，保持鏈表插入 文兑，插入后判斷是否轉換為紅黑樹(前提Hash表的數(shù)量已經(jīng)超過數(shù)組最小)盒刚，如果依然為鏈表，判斷長度是否大于闕值，如果擴容則直接長度 *2 拒名，至于擴容后的位置則通過計算方式來計算
部分源碼：
/**
* resize（）
* 該函數(shù)有2種使用情況：1.初始化哈希表 2.當前數(shù)組容量過小，需擴容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 擴容前的數(shù)組（當前數(shù)組）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 擴容前的數(shù)組的容量 = 長度
int oldThr = threshold;// 擴容前的數(shù)組的閾值
int newCap, newThr = 0;
// 針對情況2：若擴容前的數(shù)組容量超過最大值，則不再擴充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 針對情況2：若無超過最大值旱易，就擴充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通過右移擴充2倍
}
// 針對情況1：初始化哈希表（采用指定 or 默認值）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize上限
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) {
// 把每個bucket都移動到新的buckets中
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)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 鏈表優(yōu)化重hash的代碼塊
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
通過圖表說明：
擴容位置算法示意圖
相對與 JDK 1.7在計算新元素的存儲位置有很大區(qū)別：JDK 1.7在擴容后登淘，都需按照原來方法重新計算流妻，即
hashCode（）->> 擾動處理 ->>（h & length-1））证薇，JDK 1.8 做了部分的優(yōu)化寇窑，提高了擴容效率横漏。
讀完以上內(nèi)容 我們知道HashMap中默認的存儲大小就是一個容量為16的數(shù)組赴肚，所以當我們創(chuàng)建出一個HashMap對象時，即使里面沒有任何元素，也要分別一塊內(nèi)存空間給它，而且，我們再不斷的向HashMap里put數(shù)據(jù)時上真，當達到一定的容量限制時（這個容量滿足這樣的一個關系時候?qū)U容：HashMap中的數(shù)據(jù)量>容量加載因子，而HashMap中默認的加載因子是0.75），HashMap的空間將會擴大，而且擴大后新的空間一定是原來的2倍，所以我們建議在知道數(shù)據(jù)大小的時候,初始化HashMap時就設置好數(shù)據(jù)容量,以免在擴容過程中 不斷地Hash計算來消耗內(nèi)存*
上段文字其實也算一個引子挠阁，推薦 使用 parseArray 和 ArrayMap 來代替HashMap
簡單介紹：ArrayMap是一個<key,value>映射的數(shù)據(jù)結構增拥，它設計上更多的是考慮內(nèi)存的優(yōu)化逗概，內(nèi)部是使用兩個數(shù)組進行數(shù)據(jù)存儲，一個數(shù)組記錄key的hash值，另外一個數(shù)組記錄Value值家厌，它和SparseArray一樣果覆，也會對key使用二分法進行從小到大排序重绷，在添加、刪除镜硕、查找數(shù)據(jù)的時候都是先使用二分查找法得到相應的index癌淮，然后通過index來進行添加裹刮、查找买鸽、刪除等操作，所以逗物，應用場景和SparseArray的一樣摆寄，如果在數(shù)據(jù)量比較大的情況下微饥，那么它的性能將退化至少50%黍檩。
更加詳細的 源碼級介紹：
ArrayMap詳解
2 HashMap其他 可能面試的問題
大體知識點總覽
2.1 哈希表解決Hash 沖突
2.2 鍵-值（key-value）都允許為空、線程不安全赠法、不保證有序甲脏、存儲位置隨時間變化
HashMap 線程不安全的其中一個重要原因：多線程下容易出現(xiàn)resize（）死循環(huán)
本質(zhì) : 并發(fā) 執(zhí)行 put（）操作導致觸發(fā) 擴容resize（）盔憨，轉移數(shù)據(jù)操作 = 按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入讯沈，即在轉移數(shù)據(jù)郁岩、擴容后，容易出現(xiàn)鏈表逆序的情況,從而導致 環(huán)形鏈表缺狠，使得在獲取數(shù)據(jù)遍歷鏈表時形成死循環(huán).
由于 JDK 1.8 轉移數(shù)據(jù)操作 : 按舊鏈表的正序遍歷鏈表问慎、在新鏈表的尾部依次插入，所以不會出現(xiàn)鏈表 逆序儒老、倒置的情況蝴乔，故不容易出現(xiàn)環(huán)形鏈表的情況记餐。(但是還是不建議 多線程高并發(fā)中使用Hashmap驮樊，官方推薦使用 ConcurrentHashMap)
2.3 為什么 key 多推薦使用 String、Integer
2.4 HashMap 中的 key若 Object類型， 則需實現(xiàn)哪些方法囚衔？
String Integer 中都默認實現(xiàn)了 hashcode() 和 equals() 方法
至于其
-
HashMap 和 ArrayMap 的區(qū)別（數(shù)組擴容方式 ）
ArrayMap ：通過 Hash/ （key/value）的存儲方式優(yōu)化數(shù)組空間挖腰，一種獨特的方式，能夠重復的利用因為數(shù)據(jù)擴容而遺留下來的數(shù)組空間HashMap ： 初始值16個長度练湿，每次擴容的時候猴仑，直接申請雙倍的數(shù)組空間，尾插法肥哎，添加到數(shù)組/鏈表/紅黑樹子節(jié)點.
ArrayMap ： 每次擴容的時候，如果size長度大于8時申請size*1.5個長度，大于4小于8時申請8個汛骂，小于4時申請4個席镀。 HashMap 和 LinkedHashMap的區(qū)別
LinkedHashMap - 參考文章深入LinkedHashMap 了解 LRU 緩存 （個人吃過很多虧）
LinkedHashMap 及 LRU 緩存 - 參考文章
HashMap 和 LinkedHashMap 簡單區(qū)別：LinkedHashMap 是HashMap的子類，雙向鏈表保存了記錄的插入順序杈女，在遍歷LinkedHashMap時朱浴，先得到的記錄是先插入的.也可以在構造時用帶參數(shù)，按照應用次數(shù)排序达椰。在遍歷的時候會比HashMap慢翰蠢，不過有種情況例外，當HashMap容量很大啰劲，實際數(shù)據(jù)較少時梁沧，遍歷起來可能會比 LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關蝇裤，和容量無關趁尼，而HashMap的遍歷速度和他的容量有關。
- ConcurrentHashMap 了解嗎猖辫？（多并發(fā)）
ConcurrentHashMap 參考文章
個人對ConcurrentHashMap 多線程并發(fā)中做的工作：在添加元素時候酥泞，采用synchronized來保證線程安全，然后計算size的時候采用CAS操作進行計算啃憎。在擴容期間通過給不同的線程設置不同的下表索引進行擴容操作芝囤，就是不同的線程，操作的數(shù)組分段不一樣辛萍，同時利用synchronized同步鎖鎖住操作的節(jié)點悯姊，保證了線程安全。
ArrayList贩毕、LinkedList悯许、Vector 的區(qū)別
ArrayList、LinkedList辉阶、Vector 數(shù)據(jù)結構區(qū)別
ArrayList和Vector是按照順序?qū)⒃卮鎯Γ◤臑?開始）先壕，刪除元素時瘩扼，刪除操作完成后，需要使部分元素移位垃僚，默認的初始容量都是10.
ArrayList和Vector是基于數(shù)組實現(xiàn)的集绰，LinkedList是基于雙向鏈表實現(xiàn)的（含有頭結點）。所以 ArrayList和Vector 更加適合于隨機訪問數(shù)據(jù)谆棺，LinkedList 由于基于鏈表實現(xiàn)栽燕，在插入和刪除的時候只需要修改指針指向地址就可以了，所以更適合插入和刪除操作改淑。（不過由于LinkedList雙向鏈表碍岔，支持雙向查找。查找前會根據(jù)指定位置index判斷是在鏈表的前半段還是后半段朵夏，從而決定是從前往后找或是從后往前找付秕，提升查找效率。）
ArrayList侍郭、LinkedList询吴、Vector 多線程
ArrayList、LinkedList不具有線程安全性（并且LinkedList在單線程的中亮元，也是線程不安全的）猛计，如果在并發(fā)環(huán)境下使用它們，可以用Collections類中的靜態(tài)方法synchronizedList(）對ArrayList和LinkedList進行調(diào)用即可爆捞。
List list = Collections.synchronizedList(new LinkedList(...));
Vector實現(xiàn)線程安全的奉瘤，即它大部分的方法都包含關鍵字synchronized,但是Vector的效率沒有ArraykList和LinkedList高。
ArrayList煮甥、LinkedList盗温、Vector 擴容
ArrayList和Vector都是使用Object的數(shù)組形式來存儲的，當向這兩種類型中增加元素的時候成肘，若容量不夠卖局，需要進行擴容。ArrayList擴容后的容量是之前的1.5倍双霍，然后把之前的數(shù)據(jù)拷貝到新建的數(shù)組中去砚偶。而Vector默認情況下擴容后的容量是之前的2倍（擴容都通過新建數(shù)組，將老數(shù)組數(shù)據(jù)copy到新數(shù)組中）洒闸。
由于LinkedList 為雙向鏈表染坯，不存在容量，所以不需要擴容丘逸。
Vector可以設置容量增量单鹿，而ArrayList不可以。在Vector中深纲，有capacityIncrement：當大小大于其容量時仲锄，容量自動增加的量劲妙。如果在創(chuàng)建Vector時，指定了capacityIncrement的大小昼窗，則Vector中動態(tài)數(shù)組容量需要增加時，如果容量的增量大于0涛舍，則增加的是大小是capacityIncrement澄惊，如果增量小于0，則增大為之前的2倍富雅。
