一個(gè)HashMap跟面試官扯了半個(gè)小時(shí)

前言

HashMap應(yīng)該算是Java后端工程師面試的必問題，因?yàn)槠渲械闹R(shí)點(diǎn)太多，很適合用來考察面試者的Java基礎(chǔ)。

開場(chǎng)

面試官: 你先自我介紹一下吧！

安琪拉: 我是安琪拉，草叢三婊之一，最強(qiáng)中單（鐘馗不服）！哦，不對(duì)，串場(chǎng)了，我是**，目前在--公司做--系統(tǒng)開發(fā)。

面試官: 看你簡(jiǎn)歷上寫熟悉Java集合，HashMap用過的吧？

安琪拉: 用過的。(還是熟悉的味道)

面試官: 那你跟我講講HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)？

安琪拉: 目前我用的是JDK1.8版本的，內(nèi)部使用數(shù)組 + 鏈表 / 紅黑樹；

安琪拉: 方便我給您畫個(gè)數(shù)據(jù)結(jié)構(gòu)圖吧：

面試官: 那你清楚HashMap的數(shù)據(jù)插入原理嗎？

安琪拉: 呃[做沉思狀]。我覺得還是應(yīng)該畫個(gè)圖比較清楚，如下：

1. 判斷數(shù)組是否為空，為空進(jìn)行初始化;
2. 不為空，計(jì)算 k 的 hash 值，通過 (n - 1) & hash計(jì)算應(yīng)當(dāng)存放在數(shù)組中的下標(biāo) index ;
3. 查看 table[index] 是否存在數(shù)據(jù)，沒有數(shù)據(jù)就構(gòu)造一個(gè)Node節(jié)點(diǎn)存放在 table[index] 中；
4. 存在數(shù)據(jù)，說明發(fā)生了hash沖突, 繼續(xù)判斷key是否相等，相等，用新的value替換原數(shù)據(jù)(onlyIfAbsent為false)；
5. 如果不相等，判斷當(dāng)前節(jié)點(diǎn)類型是不是樹型節(jié)點(diǎn)，如果是樹型節(jié)點(diǎn)，創(chuàng)建樹型節(jié)點(diǎn)插入紅黑樹中；
6. 如果不是樹型節(jié)點(diǎn)，創(chuàng)建普通Node加入鏈表中；判斷鏈表長(zhǎng)度是否大于 8， 大于的話鏈表轉(zhuǎn)換為紅黑樹；
7. 插入完成之后判斷當(dāng)前節(jié)點(diǎn)數(shù)是否大于閾值，如果大于開始擴(kuò)容為原數(shù)組的二倍。

面試官: 剛才你提到HashMap的初始化，那HashMap怎么設(shè)定初始容量大小的嗎？

安琪拉: [這也算問題？?] 一般如果new HashMap() 不傳值，默認(rèn)大小是16，負(fù)載因子是0.75， 如果自己傳入初始大小k，初始化大小為 大于k的 2的整數(shù)次方，例如如果傳10，大小為16。（補(bǔ)充說明:實(shí)現(xiàn)代碼如下）

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;}

補(bǔ)充說明：下圖是詳細(xì)過程，算法就是讓初始二進(jìn)制分別右移1，2，4，8，16位，與自己異或，把高位第一個(gè)為1的數(shù)通過不斷右移，把高位為1的后面全變?yōu)?，111111 + 1 = 1000000  =  （符合大于50并且是2的整數(shù)次冪 ）

面試官:  你提到hash函數(shù)，你知道HashMap的哈希函數(shù)怎么設(shè)計(jì)的嗎？

安琪拉:  [問的還挺細(xì)] hash函數(shù)是先拿到通過key 的hashcode，是32位的int值，然后讓hashcode的高16位和低16位進(jìn)行異或操作。

面試官:  那你知道為什么這么設(shè)計(jì)嗎？

安琪拉:  [這也要問]，這個(gè)也叫擾動(dòng)函數(shù)，這么設(shè)計(jì)有二點(diǎn)原因：

1. 一定要盡可能降低hash碰撞，越分散越好；
2. 算法一定要盡可能高效，因?yàn)檫@是高頻操作, 因此采用位運(yùn)算；

面試官:  為什么采用hashcode的高16位和低16位異或能降低hash碰撞？hash函數(shù)能不能直接用key的hashcode？

[這問題有點(diǎn)刁鉆], 安琪拉差點(diǎn)原地??了，恨不得出biubiubiu 二一三連招。

安琪拉:  因?yàn)?key.hashCode() 函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)，返回int型散列值。int值范圍為**-2147483648~2147483647**，前后加起來大概40億的映射空間。只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的。但問題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。你想，如果HashMap數(shù)組的初始大小才16，用之前需要對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才能用來訪問數(shù)組下標(biāo)。

源碼中模運(yùn)算就是把散列值和數(shù)組長(zhǎng)度-1做一個(gè)"與"操作，位運(yùn)算比%運(yùn)算要快。

bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {     return h & (length-1);}

順便說一下，這也正好解釋了為什么HashMap的數(shù)組長(zhǎng)度要取2的整數(shù)冪。因?yàn)檫@樣（數(shù)組長(zhǎng)度-1）正好相當(dāng)于一個(gè)“低位掩碼”。“與”操作的結(jié)果就是散列值的高位全部歸零，只保留低位值，用來做數(shù)組下標(biāo)訪問。以初始長(zhǎng)度16為例，16-1=15。2進(jìn)制表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值。

  10100101 11000100 00100101& 00000000 00000000 00001111----------------------------------  00000000 00000000 00000101    //高位全部歸零，只保留末四位

但這時(shí)候問題就來了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會(huì)很嚴(yán)重。更要命的是如果散列本身做得不好，分布上成等差數(shù)列的漏洞，如果正好讓最后幾個(gè)低位呈現(xiàn)規(guī)律性重復(fù)，就無比蛋疼。

這時(shí)候 hash 函數(shù)（“擾動(dòng)函數(shù)”）的價(jià)值就體現(xiàn)出來了，說到這里大家應(yīng)該猜出來了?？聪旅孢@個(gè)圖，

右位移16位，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。

最后我們來看一下Peter Lawley的一篇專欄文章《An introduction to optimising a hashing strategy》里的的一個(gè)實(shí)驗(yàn)：他隨機(jī)選取了352個(gè)字符串，在他們散列值完全沒有沖突的前提下，對(duì)它們做低位掩碼，取數(shù)組下標(biāo)。

結(jié)果顯示，當(dāng)HashMap數(shù)組長(zhǎng)度為512的時(shí)候（），也就是用掩碼取低9位的時(shí)候，在沒有擾動(dòng)函數(shù)的情況下，發(fā)生了103次碰撞，接近30%。而在使用了擾動(dòng)函數(shù)之后只有92次碰撞。碰撞減少了將近10%?？磥頂_動(dòng)函數(shù)確實(shí)還是有功效的。

另外Java1.8相比1.7做了調(diào)整，1.7做了四次移位和四次異或，但明顯Java 8覺得擾動(dòng)做一次就夠了，做4次的話，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了。

下面是1.7的hash代碼：

static int hash(int h) {    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}

面試官:  看來做過功課，有點(diǎn)料啊！是不是偷偷看了安琪拉的博客公眾號(hào), 你剛剛說到1.8對(duì)hash函數(shù)做了優(yōu)化，1.8還有別的優(yōu)化嗎？

安琪拉: 1.8還有三點(diǎn)主要的優(yōu)化：

1. 數(shù)組+鏈表改成了數(shù)組+鏈表或紅黑樹；
2. 鏈表的插入方式從頭插法改成了尾插法，簡(jiǎn)單說就是插入時(shí)，如果數(shù)組位置上已經(jīng)有元素，1.7將新元素放到數(shù)組中，原始節(jié)點(diǎn)作為新節(jié)點(diǎn)的后繼節(jié)點(diǎn)，1.8遍歷鏈表，將元素放置到鏈表的最后；
3. 擴(kuò)容的時(shí)候1.7需要對(duì)原數(shù)組中的元素進(jìn)行重新hash定位在新數(shù)組的位置，1.8采用更簡(jiǎn)單的判斷邏輯，位置不變或索引+舊容量大??；
4. 在插入時(shí)，1.7先判斷是否需要擴(kuò)容，再插入，1.8先進(jìn)行插入，插入完成再判斷是否需要擴(kuò)容；

面試官:  你分別跟我講講為什么要做這幾點(diǎn)優(yōu)化；

安琪拉:  【咳咳，果然是連環(huán)炮】

1. 防止發(fā)生hash沖突，鏈表長(zhǎng)度過長(zhǎng)，將時(shí)間復(fù)雜度由O(n)降為O(logn);

2. 因?yàn)?.7頭插法擴(kuò)容時(shí)，頭插法會(huì)使鏈表發(fā)生反轉(zhuǎn)，多線程環(huán)境下會(huì)產(chǎn)生環(huán)；

   A線程在插入節(jié)點(diǎn)B，B線程也在插入，遇到容量不夠開始擴(kuò)容，重新hash，放置元素，采用頭插法，后遍歷到的B節(jié)點(diǎn)放入了頭部，這樣形成了環(huán)，如下圖所示：

1.7的擴(kuò)容調(diào)用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線程開始進(jìn)行擴(kuò)容      newTable[i] = e;      e = next;    }  }}

3. 擴(kuò)容的時(shí)候?yàn)槭裁?.8 不用重新hash就可以直接定位原節(jié)點(diǎn)在新數(shù)據(jù)的位置呢?

   這是由于擴(kuò)容是擴(kuò)大為原數(shù)組大小的2倍，用于計(jì)算數(shù)組位置的掩碼僅僅只是高位多了一個(gè)1，舉個(gè)例子：

   擴(kuò)容前長(zhǎng)度為16，用于計(jì)算 (n-1) & hash 的二進(jìn)制n - 1為0000 1111，  

     擴(kuò)容后為32后的二進(jìn)制就高位多了1，============>為0001 1111。

3. 因?yàn)槭?amp; 運(yùn)算，1和任何數(shù) & 都是它本身，那就分二種情況，如下圖：原數(shù)據(jù)hashcode高位第4位為0和高位為1的情況；

   第四位高位為0，重新hash數(shù)值不變，第四位為1，重新hash數(shù)值比原來大16（舊數(shù)組的容量）

   

面試官:  那HashMap是線程安全的嗎？

安琪拉:  不是，在多線程環(huán)境下，1.7 會(huì)產(chǎn)生死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋的問題，1.8 中會(huì)有數(shù)據(jù)覆蓋的問題。

以1.8為例，當(dāng)A線程執(zhí)行到下面代碼第6行判斷index位置為空后正好掛起，B線程開始執(zhí)行第7 行，往index位置的寫入節(jié)點(diǎn)數(shù)據(jù)，這時(shí)A線程恢復(fù)現(xiàn)場(chǎng)，執(zhí)行賦值操作，就把A線程的數(shù)據(jù)給覆蓋了；

還有第38行++size這個(gè)地方也會(huì)造成多線程同時(shí)擴(kuò)容等問題。

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) // 多個(gè)線程走到這，可能重復(fù)resize()    resize();  afterNodeInsertion(evict);  return null;}

面試官:  那你平常怎么解決這個(gè)線程不安全的問題？

安琪拉:  Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以實(shí)現(xiàn)線程安全的Map。

1. HashTable是直接在操作方法上加synchronized關(guān)鍵字，鎖住整個(gè)數(shù)組，粒度比較大；

2. Collections.synchronizedMap是使用Collections集合工具的內(nèi)部類，通過傳入Map封裝出一個(gè)SynchronizedMap對(duì)象，內(nèi)部定義了一個(gè)對(duì)象鎖，方法內(nèi)通過對(duì)象鎖實(shí)現(xiàn)；

3. ConcurrentHashMap使用分段鎖，降低了鎖粒度，讓并發(fā)度大大提高。

面試官:  那你知道ConcurrentHashMap的分段鎖的實(shí)現(xiàn)原理嗎？

安琪拉:  【天啦擼! 俄羅斯套娃，一個(gè)套一個(gè)】ConcurrentHashMap成員變量使用volatile 修飾，免除了指令重排序，同時(shí)保證內(nèi)存可見性，另外使用CAS操作和synchronized結(jié)合實(shí)現(xiàn)賦值操作，多線程操作只會(huì)鎖住當(dāng)前操作索引的節(jié)點(diǎn)。

如下圖，線程A鎖住A節(jié)點(diǎn)所在鏈表，線程B鎖住B節(jié)點(diǎn)所在鏈表，操作互不干涉。

面試官:  你前面提到鏈表轉(zhuǎn)紅黑樹是鏈表長(zhǎng)度達(dá)到閾值，這個(gè)閾值是多少？

安琪拉:  閾值是8，紅黑樹轉(zhuǎn)鏈表閾值為6

面試官:  為什么是8，不是16，32甚至是7 ？又為什么紅黑樹轉(zhuǎn)鏈表的閾值是6，不是8了呢？

安琪拉: 【你去問作者?。√炖矓]，biubiubiu 真想213連招】

因?yàn)樽髡呔瓦@么設(shè)計(jì)的，哦，不對(duì)，因?yàn)榻?jīng)過計(jì)算，在hash函數(shù)設(shè)計(jì)合理的情況下，發(fā)生hash碰撞8次的幾率為百萬分之6，概率說話。。因?yàn)?夠用了，至于為什么轉(zhuǎn)回來是6，因?yàn)槿绻鹔ash碰撞次數(shù)在8附近徘徊，會(huì)一直發(fā)生鏈表和紅黑樹的轉(zhuǎn)化，為了預(yù)防這種情況的發(fā)生。

面試官:  HashMap內(nèi)部節(jié)點(diǎn)是有序的嗎？

安琪拉:  是無序的，根據(jù)hash值隨機(jī)插入

面試官:  那有沒有有序的Map？

安琪拉:  LinkedHashMap 和 TreeMap

面試官:  跟我講講LinkedHashMap怎么實(shí)現(xiàn)有序的？

安琪拉:  LinkedHashMap內(nèi)部維護(hù)了一個(gè)單鏈表，有頭尾節(jié)點(diǎn)，同時(shí)LinkedHashMap節(jié)點(diǎn)Entry內(nèi)部除了繼承HashMap的Node屬性，還有before 和 after用于標(biāo)識(shí)前置節(jié)點(diǎn)和后置節(jié)點(diǎn)?？梢詫?shí)現(xiàn)按插入的順序或訪問順序排序。

/** * 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é)點(diǎn)到鏈表后端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é)點(diǎn)類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怎么實(shí)現(xiàn)有序的？

安琪拉：TreeMap是按照Key的自然順序或者Comprator的順序進(jìn)行排序，內(nèi)部是通過紅黑樹來實(shí)現(xiàn)。所以要么key所屬的類實(shí)現(xiàn)Comparable接口，或者自定義一個(gè)實(shí)現(xiàn)了Comparator接口的比較器，傳給TreeMap用戶key的比較。

面試官:  前面提到通過CAS 和 synchronized結(jié)合實(shí)現(xiàn)鎖粒度的降低，你能給我講講CAS 的實(shí)現(xiàn)以及synchronized的實(shí)現(xiàn)原理嗎？

安琪拉:  下一期咋們?cè)偌s時(shí)間，OK？

面試官:  好吧，回去等通知吧！

--end--

掃描下方二維碼
添加好友，備注【交流】
可私聊交流，也可進(jìn)資源豐富學(xué)習(xí)群

更文不易，點(diǎn)個(gè)“在看”支持一下??