一個HashMap跟面試官扯了半個小時
前言
HashMap應該算是Java后端工程師面試的必問題，因為其中的知識點太多，很適合用來考察面試者的Java基礎。
開場
面試官: 你先自我介紹一下吧！
安琪拉: 我是安琪拉，草叢三婊之一，最強中單（鐘馗不服）！哦，不對，串場了，我是**，目前在--公司做--系統開發(fā)。
面試官: 看你簡歷上寫熟悉Java集合，HashMap用過的吧？
安琪拉: 用過的。(還是熟悉的味道)
面試官: 那你跟我講講HashMap的內部數據結構？
安琪拉: 目前我用的是JDK1.8版本的，內部使用數組 + 鏈表 / 紅黑樹；
安琪拉: 方便我給您畫個數據結構圖吧：
面試官: 那你清楚HashMap的數據插入原理嗎？
安琪拉: 呃[做沉思狀]。我覺得還是應該畫個圖比較清楚，如下：
- 判斷數組是否為空，為空進行初始化;
- 不為空，計算 k 的 hash 值，通過 (n - 1) & hash計算應當存放在數組中的下標 index ;
- 查看 table[index] 是否存在數據，沒有數據就構造一個Node節(jié)點存放在 table[index] 中；
- 存在數據，說明發(fā)生了hash沖突, 繼續(xù)判斷key是否相等，相等，用新的value替換原數據(onlyIfAbsent為false)；
- 如果不相等，判斷當前節(jié)點類型是不是樹型節(jié)點，如果是樹型節(jié)點，創(chuàng)建樹型節(jié)點插入紅黑樹中；
- 如果不是樹型節(jié)點，創(chuàng)建普通Node加入鏈表中；判斷鏈表長度是否大于 8， 大于的話鏈表轉換為紅黑樹；
- 插入完成之后判斷當前節(jié)點數是否大于閾值，如果大于開始擴容為原數組的二倍。
面試官: 剛才你提到HashMap的初始化，那HashMap怎么設定初始容量大小的嗎？
安琪拉: [這也算問題？?] 一般如果new HashMap() 不傳值，默認大小是16，負載因子是0.75， 如果自己傳入初始大小k，初始化大小為 大于k的 2的整數次方，例如如果傳10，大小為16。（補充說明:實現代碼如下）
- static final int tableSizeFor(int cap) {
- int n = cap - 1;
- n |= n >>> 1;
- n |= n >>> 2;
- n |= n >>> 4;
- n |= n >>> 8;
- n |= n >>> 16;
- return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
補充說明：下圖是詳細過程，算法就是讓初始二進制分別右移1，2，4，8，16位，與自己異或，把高位第一個為1的數通過不斷右移，把高位為1的后面全變?yōu)?，111111 + 1 = 1000000 = （符合大于50并且是2的整數次冪 ）
面試官: 你提到hash函數，你知道HashMap的哈希函數怎么設計的嗎？
安琪拉: [問的還挺細] hash函數是先拿到通過key 的hashcode，是32位的int值，然后讓hashcode的高16位和低16位進行異或操作。
面試官: 那你知道為什么這么設計嗎？
安琪拉: [這也要問]，這個也叫擾動函數，這么設計有二點原因：
- 一定要盡可能降低hash碰撞，越分散越好；
- 算法一定要盡可能高效，因為這是高頻操作, 因此采用位運算；
面試官: 為什么采用hashcode的高16位和低16位異或能降低hash碰撞？hash函數能不能直接用key的hashcode？
[這問題有點刁鉆], 安琪拉差點原地💥了，恨不得出biubiubiu 二一三連招。
安琪拉: 因為 key.hashCode() 函數調用的是key鍵值類型自帶的哈希函數，返回int型散列值。int值范圍為**-2147483648~2147483647**，前后加起來大概40億的映射空間。只要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。但問題是一個40億長度的數組，內存是放不下的。你想，如果HashMap數組的初始大小才16，用之前需要對數組的長度取模運算，得到的余數才能用來訪問數組下標。
源碼中模運算就是把散列值和數組長度-1做一個"與"操作，位運算比%運算要快。
- bucketIndex = indexFor(hash, table.length);
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
順便說一下，這也正好解釋了為什么HashMap的數組長度要取2的整數冪。因為這樣（數組長度-1）正好相當于一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度16為例，16-1=15。2進制表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。
- 10100101 11000100 00100101
- & 00000000 00000000 00001111
- ----------------------------------
- 00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時候問題就來了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分布上成等差數列的漏洞，如果正好讓最后幾個低位呈現規(guī)律性重復，就無比蛋疼。
這時候 hash 函數（“擾動函數”）的價值就體現出來了，說到這里大家應該猜出來了?？聪旅孢@個圖，
右位移16位，正好是32bit的一半，自己的高半區(qū)和低半區(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
最后我們來看一下Peter Lawley的一篇專欄文章《An introduction to optimising a hashing strategy》里的的一個實驗：他隨機選取了352個字符串，在他們散列值完全沒有沖突的前提下，對它們做低位掩碼，取數組下標。
結果顯示，當HashMap數組長度為512的時候（），也就是用掩碼取低9位的時候，在沒有擾動函數的情況下，發(fā)生了103次碰撞，接近30%。而在使用了擾動函數之后只有92次碰撞。碰撞減少了將近10%。看來擾動函數確實還是有功效的。
另外Java1.8相比1.7做了調整，1.7做了四次移位和四次異或，但明顯Java 8覺得擾動做一次就夠了，做4次的話，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了。
下面是1.7的hash代碼：
- static int hash(int h) {
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
- }
面試官: 看來做過功課，有點料啊！是不是偷偷看了安琪拉的博客公眾號, 你剛剛說到1.8對hash函數做了優(yōu)化，1.8還有別的優(yōu)化嗎？
安琪拉: 1.8還有三點主要的優(yōu)化：
- 數組+鏈表改成了數組+鏈表或紅黑樹；
- 鏈表的插入方式從頭插法改成了尾插法，簡單說就是插入時，如果數組位置上已經有元素，1.7將新元素放到數組中，原始節(jié)點作為新節(jié)點的后繼節(jié)點，1.8遍歷鏈表，將元素放置到鏈表的最后；
- 擴容的時候1.7需要對原數組中的元素進行重新hash定位在新數組的位置，1.8采用更簡單的判斷邏輯，位置不變或索引+舊容量大??；
- 在插入時，1.7先判斷是否需要擴容，再插入，1.8先進行插入，插入完成再判斷是否需要擴容；
面試官: 你分別跟我講講為什么要做這幾點優(yōu)化；
安琪拉: 【咳咳，果然是連環(huán)炮】
- 防止發(fā)生hash沖突，鏈表長度過長，將時間復雜度由O(n)降為O(logn);
- 因為1.7頭插法擴容時，頭插法會使鏈表發(fā)生反轉，多線程環(huán)境下會產生環(huán)；
A線程在插入節(jié)點B，B線程也在插入，遇到容量不夠開始擴容，重新hash，放置元素，采用頭插法，后遍歷到的B節(jié)點放入了頭部，這樣形成了環(huán)，如下圖所示：
1.7的擴容調用transfer代碼，如下所示：
- void transfer(Entry[] newTable, boolean rehash) {
- int newCapacity = newTable.length;
- for (Entry<K,V> e : table) {
- while(null != e) {
- Entry<K,V> next = e.next;
- if (rehash) {
- e.hash = null == e.key ? 0 : hash(e.key);
- }
- int i = indexFor(e.hash, newCapacity);
- e.next = newTable[i]; //A線程如果執(zhí)行到這一行掛起，B線程開始進行擴容
- newTable[i] = e;
- e = next;
- }
- }
- }
3. 擴容的時候為什么1.8 不用重新hash就可以直接定位原節(jié)點在新數據的位置呢?
這是由于擴容是擴大為原數組大小的2倍，用于計算數組位置的掩碼僅僅只是高位多了一個1，舉個例子：擴容前長度為16，用于計算 (n-1) & hash 的二進制n - 1為0000 1111，
擴容后為32后的二進制就高位多了1，============>為0001 1111。
4. 因為是& 運算，1和任何數 & 都是它本身，那就分二種情況，如下圖：原數據hashcode高位第4位為0和高位為1的情況；
第四位高位為0，重新hash數值不變，第四位為1，重新hash數值比原來大16（舊數組的容量）
面試官: 那HashMap是線程安全的嗎？
安琪拉: 不是，在多線程環(huán)境下，1.7 會產生死循環(huán)、數據丟失、數據覆蓋的問題，1.8 中會有數據覆蓋的問題。
以1.8為例，當A線程執(zhí)行到下面代碼第6行判斷index位置為空后正好掛起，B線程開始執(zhí)行第7 行，往index位置的寫入節(jié)點數據，這時A線程恢復現場，執(zhí)行賦值操作，就把A線程的數據給覆蓋了；
還有第38行++size這個地方也會造成多線程同時擴容等問題。
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- if ((p = tab[i = (n - 1) & hash]) == null) //多線程執(zhí)行到這里
- tab[i] = newNode(hash, key, value, null);
- else {
- 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)
- 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);
- if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- if (++size > threshold) // 多個線程走到這，可能重復resize()
- resize();
- afterNodeInsertion(evict);
- return null;
- }
面試官: 那你平常怎么解決這個線程不安全的問題？
安琪拉: Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以實現線程安全的Map。
- HashTable是直接在操作方法上加synchronized關鍵字，鎖住整個數組，粒度比較大；
- Collections.synchronizedMap是使用Collections集合工具的內部類，通過傳入Map封裝出一個SynchronizedMap對象，內部定義了一個對象鎖，方法內通過對象鎖實現；
- ConcurrentHashMap使用分段鎖，降低了鎖粒度，讓并發(fā)度大大提高。
面試官: 那你知道ConcurrentHashMap的分段鎖的實現原理嗎？
安琪拉: 【天啦擼! 俄羅斯套娃，一個套一個】ConcurrentHashMap成員變量使用volatile 修飾，免除了指令重排序，同時保證內存可見性，另外使用CAS操作和synchronized結合實現賦值操作，多線程操作只會鎖住當前操作索引的節(jié)點。
如下圖，線程A鎖住A節(jié)點所在鏈表，線程B鎖住B節(jié)點所在鏈表，操作互不干涉。
面試官: 你前面提到鏈表轉紅黑樹是鏈表長度達到閾值，這個閾值是多少？
安琪拉: 閾值是8，紅黑樹轉鏈表閾值為6
面試官: 為什么是8，不是16，32甚至是7 ？又為什么紅黑樹轉鏈表的閾值是6，不是8了呢？
安琪拉: 【你去問作者??！天啦擼，biubiubiu 真想213連招】
因為作者就這么設計的，哦，不對，因為經過計算，在hash函數設計合理的情況下，發(fā)生hash碰撞8次的幾率為百萬分之6，概率說話。。因為8夠用了，至于為什么轉回來是6，因為如果hash碰撞次數在8附近徘徊，會一直發(fā)生鏈表和紅黑樹的轉化，為了預防這種情況的發(fā)生。
面試官: HashMap內部節(jié)點是有序的嗎？
安琪拉: 是無序的，根據hash值隨機插入
面試官: 那有沒有有序的Map？
安琪拉: LinkedHashMap 和 TreeMap
面試官: 跟我講講LinkedHashMap怎么實現有序的？
安琪拉: LinkedHashMap內部維護了一個單鏈表，有頭尾節(jié)點，同時LinkedHashMap節(jié)點Entry內部除了繼承HashMap的Node屬性，還有before 和 after用于標識前置節(jié)點和后置節(jié)點?？梢詫崿F按插入的順序或訪問順序排序。
- /**
- * The head (eldest) of the doubly linked list.
- */
- transient LinkedHashMap.Entry<K,V> head;
- /**
- * The tail (youngest) of the doubly linked list.
- */
- transient LinkedHashMap.Entry<K,V> tail;
- //鏈接新加入的p節(jié)點到鏈表后端
- private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
- LinkedHashMap.Entry<K,V> last = tail;
- tail = p;
- if (last == null)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- }
- //LinkedHashMap的節(jié)點類
- static class Entry<K,V> extends HashMap.Node<K,V> {
- Entry<K,V> before, after;
- Entry(int hash, K key, V value, Node<K,V> next) {
- super(hash, key, value, next);
- }
- }
示例代碼：
- public static void main(String[] args) { Map<String, String> map = new LinkedHashMap<String, String>(); map.put("1", "安琪拉"); map.put("2", "的"); map.put("3", "博客"); for(Map.Entry<String,String> item: map.entrySet()){ System.out.println(item.getKey() + ":" + item.getValue()); }}//console輸出1:安琪拉2:的3:博客
面試官: 跟我講講TreeMap怎么實現有序的？
安琪拉：TreeMap是按照Key的自然順序或者Comprator的順序進行排序，內部是通過紅黑樹來實現。所以要么key所屬的類實現Comparable接口，或者自定義一個實現了Comparator接口的比較器，傳給TreeMap用戶key的比較。
面試官: 前面提到通過CAS 和 synchronized結合實現鎖粒度的降低，你能給我講講CAS 的實現以及synchronized的實現原理嗎？
安琪拉: 下一期咋們再約時間，OK？
面試官: 好吧，回去等通知吧！
