面試題1：說一下 HashMap 的實(shí)現(xiàn)原理？

正經(jīng)回答：

眾所周知，HashMap是一個(gè)用于存儲(chǔ)Key-Value鍵值對(duì)的集合，每一個(gè)鍵值對(duì)也叫做Entry（包括Key-Value），其中Key 和 Value 允許為null。這些個(gè)鍵值對(duì)（Entry）分散存儲(chǔ)在一個(gè)數(shù)組當(dāng)中，這個(gè)數(shù)組就是HashMap的主干。另外，HashMap數(shù)組每一個(gè)元素的初始值都是Null。

值得注意的是：HashMap不能保證映射的順序，插入后的數(shù)據(jù)順序也不能保證一直不變（如擴(kuò)容后rehash）。

要說HashMap的原理，首先要先了解他的數(shù)據(jù)結(jié)構(gòu)，

如上圖為JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)，其實(shí)HashMap在JDK1.7及以前是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組 + 鏈表的結(jié)合體。JDK8優(yōu)化為：數(shù)組+鏈表+紅黑樹。

我們常把數(shù)組中的每一個(gè)節(jié)點(diǎn)稱為一個(gè)桶。當(dāng)向桶中添加一個(gè)鍵值對(duì)時(shí)，首先計(jì)算鍵值對(duì)中key的hash值（hash(key)），以此確定插入數(shù)組中的位置（即哪個(gè)桶），但是可能存在同一hash值的元素已經(jīng)被放在數(shù)組同一位置了，這種現(xiàn)象稱為碰撞，這時(shí)按照尾插法(jdk1.7及以前為頭插法)的方式添加key-value到同一hash值的元素的最后面，鏈表就這樣形成了。

當(dāng)鏈表長(zhǎng)度超過8(TREEIFY_THRESHOLD - 閾值)時(shí)，鏈表就自行轉(zhuǎn)為紅黑樹。

注意：同一hash值的元素指的是key內(nèi)容一樣么？不是。根據(jù)hash算法的計(jì)算方式，是將key值轉(zhuǎn)為一個(gè)32位的int值（近似取值），key值不同但key值相近的很可能hash值相同，如key=“a”和key=“aa”等。

通過上述回答的內(nèi)容，我們明顯給了面試官往深入問的多個(gè)誘餌，根據(jù)我們的回答，下一步他多可能會(huì)追問這些問題：

1、如何實(shí)現(xiàn)HashMap的有序？ 4、put方法原理是怎么實(shí)現(xiàn)的？ 6、擴(kuò)容機(jī)制原理 → 初始容量、加載因子 → 擴(kuò)容后的rehash（元素遷移） 2、插入后的數(shù)據(jù)順序會(huì)變的原因是什么？ 3、HashMap在JDK1.7-JDK1.8都做了哪些優(yōu)化？ 5、鏈表紅黑樹如何互相轉(zhuǎn)換？閾值多少？ 7、頭插法改成尾插法為了解決什么問題？

而我們，當(dāng)然是提前準(zhǔn)備好如何回答好這些問題！當(dāng)你的回答超過面試同學(xué)的認(rèn)知范圍時(shí)，主動(dòng)權(quán)就到我們手里了。

深入追問： 追問1：如何實(shí)現(xiàn)HashMap的有序？

使用LinkedHashMap 或 TreeMap。

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> linkedMap = new LinkedHashMap<String, String>();
  linkedMap.put("1", "占便宜");
  linkedMap.put("2", "沒夠兒");
  linkedMap.put("3", "吃虧");
  linkedMap.put("4", "難受");
  for(linkedMap.Entry<String,String> item: linkedMap.entrySet()){
    System.out.println(item.getKey() + ":" + item.getValue());
  }
}

輸出結(jié)果:

1:占便宜 2:沒夠兒 3:吃虧 4:難受

追問2：那TreeMap怎么實(shí)現(xiàn)有序的？

TreeMap是按照Key的自然順序或者Comprator的順序進(jìn)行排序，內(nèi)部是通過紅黑樹來實(shí)現(xiàn)。

TreeMap實(shí)現(xiàn)了SortedMap接口，它是一個(gè)key有序的Map類。要么key所屬的類實(shí)現(xiàn)Comparable接口，或者自定義一個(gè)實(shí)現(xiàn)了Comparator接口的比較器，傳給TreeMap用于key的比較。

TreeMap<String, String> map = new TreeMap<String, String>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
            return o2.compareTo(o1);
    }
});

追問3：put方法原理是怎么實(shí)現(xiàn)的？

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] 中；存在數(shù)據(jù)，說明發(fā)生了hash沖突(存在二個(gè)節(jié)點(diǎn)key的hash值一樣), 繼續(xù)判斷key是否相等，相等，用新的value替換原數(shù)據(jù)(onlyIfAbsent為false)；
4. 如果不相等，判斷當(dāng)前節(jié)點(diǎn)類型是不是樹型節(jié)點(diǎn)，如果是樹型節(jié)點(diǎn)，創(chuàng)造樹型節(jié)點(diǎn)插入紅黑樹中；
5. (如果當(dāng)前節(jié)點(diǎn)是樹型節(jié)點(diǎn)證明當(dāng)前已經(jīng)是紅黑樹了)如果不是樹型節(jié)點(diǎn)，創(chuàng)建普通Node加入鏈表中；
6. 判斷鏈表長(zhǎng)度是否大于 8并且數(shù)組長(zhǎng)度大于64， 大于的話鏈表轉(zhuǎn)換為紅黑樹；
7. 插入完成之后判斷當(dāng)前節(jié)點(diǎn)數(shù)是否大于閾值，如果大于開始擴(kuò)容為原數(shù)組的二倍。

下面我們看看源碼中的內(nèi)容：

/**
 * 將指定參數(shù)key和指定參數(shù)value插入map中，如果key已經(jīng)存在，那就替換key對(duì)應(yīng)的value
 * 
 * @param key 指定key
 * @param value 指定value
 * @return 如果value被替換，則返回舊的value，否則返回null。當(dāng)然，可能key對(duì)應(yīng)的value就是null。
 */
public V put(K key, V value) {
    //putVal方法的實(shí)現(xiàn)就在下面
    return putVal(hash(key), key, value, false, true);
}

從源碼中可以看到，put(K key, V value)可以分為三個(gè)步驟：

1. 通過hash(Object key)方法計(jì)算key的哈希值。
2. 通過putVal(hash(key), key, value, false, true)方法實(shí)現(xiàn)功能。
3. 返回putVal方法返回的結(jié)果。

那么看看putVal方法的源碼是如何實(shí)現(xiàn)的？

/**
 * Map.put和其他相關(guān)方法的實(shí)現(xiàn)需要的方法
 * 
 * @param hash 指定參數(shù)key的哈希值
 * @param key 指定參數(shù)key
 * @param value 指定參數(shù)value
 * @param onlyIfAbsent 如果為true，即使指定參數(shù)key在map中已經(jīng)存在，也不會(huì)替換value
 * @param evict 如果為false，數(shù)組table在創(chuàng)建模式中
 * @return 如果value被替換，則返回舊的value，否則返回null。當(dāng)然，可能key對(duì)應(yīng)的value就是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;
    //如果哈希表為空，調(diào)用resize()創(chuàng)建一個(gè)哈希表，并用變量n記錄哈希表長(zhǎng)度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果指定參數(shù)hash在表中沒有對(duì)應(yīng)的桶，即為沒有碰撞
    if ((p = tab[i = (n - 1) & hash]) == null)
        //直接將鍵值對(duì)插入到map中即可
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //如果碰撞了，且桶中的第一個(gè)節(jié)點(diǎn)就匹配了
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //將桶中的第一個(gè)節(jié)點(diǎn)記錄起來
            e = p;
        //如果桶中的第一個(gè)節(jié)點(diǎn)沒有匹配上，且桶內(nèi)為紅黑樹結(jié)構(gòu)，則調(diào)用紅黑樹對(duì)應(yīng)的方法插入鍵值對(duì)
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //不是紅黑樹結(jié)構(gòu)，那么就肯定是鏈?zhǔn)浇Y(jié)構(gòu)
        else {
            //遍歷鏈?zhǔn)浇Y(jié)構(gòu)
            for (int binCount = 0; ; ++binCount) {
                //如果到了鏈表尾部
                if ((e = p.next) == null) {
                    //在鏈表尾部插入鍵值對(duì)
                    p.next = newNode(hash, key, value, null);
                    //如果鏈的長(zhǎng)度大于TREEIFY_THRESHOLD這個(gè)臨界值，則把鏈變?yōu)榧t黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //跳出循環(huán)
                    break;
                }
                //如果找到了重復(fù)的key，判斷鏈表中結(jié)點(diǎn)的key值與插入的元素的key值是否相等，如果相等，跳出循環(huán)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
                p = e;
            }
        }
        //如果key映射的節(jié)點(diǎn)不為null
        if (e != null) { // existing mapping for key
            //記錄節(jié)點(diǎn)的vlaue
            V oldValue = e.value;
            //如果onlyIfAbsent為false，或者oldValue為null
            if (!onlyIfAbsent || oldValue == null)
                //替換value
                e.value = value;
            //訪問后回調(diào)
            afterNodeAccess(e);
            //返回節(jié)點(diǎn)的舊值
            return oldValue;
        }
    }
    //結(jié)構(gòu)型修改次數(shù)+1
    ++modCount;
    //判斷是否需要擴(kuò)容
    if (++size > threshold)
        resize();
    //插入后回調(diào)
    afterNodeInsertion(evict);
    return null;
}

追問4：HashMap擴(kuò)容機(jī)制原理

capacity 即容量，默認(rèn)16。

loadFactor 加載因子，默認(rèn)是0.75

threshold 閾值。閾值=容量*加載因子。默認(rèn)12。當(dāng)元素?cái)?shù)量超過閾值時(shí)便會(huì)觸發(fā)擴(kuò)容。

• 一般情況下，當(dāng)元素?cái)?shù)量超過閾值時(shí)便會(huì)觸發(fā)擴(kuò)容（調(diào)用resize()方法）。
• 每次擴(kuò)容的容量都是之前容量的2倍。
• 擴(kuò)展后Node對(duì)象的位置要么在原位置，要么移動(dòng)到原偏移量?jī)杀兜奈恢谩?/li>

這里我們以JDK1.8的擴(kuò)容為例：

HashMap的容量變化通常存在以下幾種情況：

1.空參數(shù)的構(gòu)造函數(shù)：實(shí)例化的HashMap默認(rèn)內(nèi)部數(shù)組是null，即沒有實(shí)例化。第一次調(diào)用put方法時(shí)，則會(huì)開始第一次初始化擴(kuò)容，長(zhǎng)度為16。

2.有參構(gòu)造函數(shù)：用于指定容量。會(huì)根據(jù)指定的正整數(shù)找到不小于指定容量的2的冪數(shù)，將這個(gè)數(shù)設(shè)置賦值給閾值（threshold）。第一次調(diào)用put方法時(shí)，會(huì)將閾值賦值給容量，然后讓 閾值 = 容量 x 加載因子 。（因此并不是我們手動(dòng)指定了容量就一定不會(huì)觸發(fā)擴(kuò)容，超過閾值后一樣會(huì)擴(kuò)容?。。?/p>

3.如果不是第一次擴(kuò)容，則容量變?yōu)樵瓉淼?倍，閾值也變?yōu)樵瓉淼?倍。（容量和閾值都變?yōu)樵瓉淼?倍時(shí)，加載因子0.75不變）

此外還有幾個(gè)點(diǎn)需要注意：

• 首次put時(shí)，先會(huì)觸發(fā)擴(kuò)容（算是初始化），然后存入數(shù)據(jù)，然后判斷是否需要擴(kuò)容；可見首次擴(kuò)容可能會(huì)調(diào)用兩次resize()方法。
• 不是首次put，則不再初始化，直接存入數(shù)據(jù)，然后判斷是否需要擴(kuò)容；

擴(kuò)容時(shí)，要擴(kuò)大空間，為了使hash散列均勻分布，原有部分元素的位置會(huì)發(fā)生移位。

JDK7的元素遷移

JDK7中，HashMap的內(nèi)部數(shù)據(jù)保存的都是鏈表。因此邏輯相對(duì)簡(jiǎn)單：在準(zhǔn)備好新的數(shù)組后，map會(huì)遍歷數(shù)組的每個(gè)“桶”，然后遍歷桶中的每個(gè)Entity，重新計(jì)算其hash值（也有可能不計(jì)算），找到新數(shù)組中的對(duì)應(yīng)位置，以頭插法插入新的鏈表。

• 這里有幾個(gè)注意點(diǎn)：

是否要重新計(jì)算hash值的條件這里不深入討論，讀者可自行查閱源碼。因?yàn)槭穷^插法，因此新舊鏈表的元素位置會(huì)發(fā)生轉(zhuǎn)置現(xiàn)象。

元素遷移的過程中在多線程情境下有可能會(huì)觸發(fā)死循環(huán)（無限進(jìn)行鏈表反轉(zhuǎn)）。

JDK1.8的元素遷移

JDK1.8則因?yàn)榍擅畹脑O(shè)計(jì)，性能有了大大的提升：由于數(shù)組的容量是以2的冪次方擴(kuò)容的，那么一個(gè)Entity在擴(kuò)容時(shí)，新的位置要么在原位置，要么在原長(zhǎng)度+原位置的位置。原因如下圖：

數(shù)組長(zhǎng)度變?yōu)樵瓉淼?倍，表現(xiàn)在二進(jìn)制上就是多了一個(gè)高位參與數(shù)組下標(biāo)確定。此時(shí)，一個(gè)元素通過hash轉(zhuǎn)換坐標(biāo)的方法計(jì)算后，恰好出現(xiàn)一個(gè)現(xiàn)象：最高位是0則坐標(biāo)不變，最高位是1則坐標(biāo)變?yōu)椤?0000+原坐標(biāo)”，即“原長(zhǎng)度+原坐標(biāo)”。如下圖：

因此，在擴(kuò)容時(shí)，不需要重新計(jì)算元素的hash了，只需要判斷最高位是1還是0就好了。

JDK8的HashMap還有以下細(xì)節(jié)需要注意：

• JDK8在遷移元素時(shí)是正序的，不會(huì)出現(xiàn)鏈表轉(zhuǎn)置的發(fā)生。
• 如果某個(gè)桶內(nèi)的元素超過8個(gè)，則會(huì)將鏈表轉(zhuǎn)化成紅黑樹，加快數(shù)據(jù)查詢效率。

追問5：HashMap在JDK1.8都做了哪些優(yōu)化？

1.數(shù)組+鏈表改成了數(shù)組+鏈表或紅黑樹；

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

2.鏈表的插入方式從頭插法改成了尾插法，簡(jiǎn)單說就是插入時(shí)，如果數(shù)組位置上已經(jīng)有元素，1.7將新元素放到數(shù)組中，新節(jié)點(diǎn)插入到鏈表頭部，原始節(jié)點(diǎn)后移；而JDK1.8會(huì)遍歷鏈表，將元素放置到鏈表的最后；

因?yàn)?.7頭插法擴(kuò)容時(shí)，頭插法可能會(huì)導(dǎo)致鏈表發(fā)生反轉(zhuǎn)，多線程環(huán)境下會(huì)產(chǎn)生環(huán)（死循環(huán)）；

這個(gè)過程為，先將A復(fù)制到新的hash表中，然后接著復(fù)制B到鏈頭（A的前邊：B.next=A），本來B.next=null，到此也就結(jié)束了（跟線程二一樣的過程），但是，由于線程二擴(kuò)容的原因，將B.next=A，所以，這里繼續(xù)復(fù)制A，讓A.next=B，由此，環(huán)形鏈表出現(xiàn)：B.next=A; A.next=B

使用頭插會(huì)改變鏈表的上的順序，但是如果使用尾插，在擴(kuò)容時(shí)會(huì)保持鏈表元素原本的順序，就不會(huì)出現(xiàn)鏈表成環(huán)的問題了。

就是說原本是A->B，在擴(kuò)容后那個(gè)鏈表還是A->B。

3.擴(kuò)容的時(shí)候1.7需要對(duì)原數(shù)組中的元素進(jìn)行重新hash定位在新數(shù)組的位置，1.8采用更簡(jiǎn)單的判斷邏輯，位置不變或索引+舊容量大?。?/p>

4.在插入時(shí)，1.7先判斷是否需要擴(kuò)容，再插入，1.8先進(jìn)行插入，插入完成再判斷是否需要擴(kuò)容；

追問6：鏈表紅黑樹如何互相轉(zhuǎn)換？閾值多少？

• **鏈表轉(zhuǎn)紅黑樹的閾值為：8
• ****紅黑樹轉(zhuǎn)鏈表的閾值為：6 **

經(jīng)過計(jì)算，在hash函數(shù)設(shè)計(jì)合理的情況下，發(fā)生hash碰撞8次的幾率為百萬分之6，從概率上講，閾值為8足夠用；至于為什么紅黑樹轉(zhuǎn)回來鏈表的條件閾值是6而不是7或9？因?yàn)槿绻鹔ash碰撞次數(shù)在8附近徘徊，可能會(huì)頻繁發(fā)生鏈表和紅黑樹的互相轉(zhuǎn)化操作，為了預(yù)防這種情況的發(fā)生。

面試題2：HashMap是線程安全的嗎？

正經(jīng)回答：

不是線程安全的，在多線程環(huán)境下，

• JDK1.7：會(huì)產(chǎn)生死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋的問題；
• JDK1.8：中會(huì)有數(shù)據(jù)覆蓋的問題。

以1.8為例，當(dāng)A線程判斷index位置為空后正好掛起，B線程開始往index位置寫入數(shù)據(jù)時(shí)，這時(shí)A線程恢復(fù)，執(zhí)行寫入操作，這樣A或B數(shù)據(jù)就被覆蓋了。

追問1：你是如何解決這個(gè)線程不安全問題的？

在Java中有HashTable、SynchronizedMap、ConcurrentHashMap這三種是實(shí)現(xiàn)線程安全的Map。

• HashTable：是直接在操作方法上加synchronized關(guān)鍵字，鎖住整個(gè)數(shù)組，粒度比較大；
• SynchronizedMap：是使用Collections集合工具的內(nèi)部類，通過傳入Map封裝出一個(gè)SynchronizedMap對(duì)象，內(nèi)部定義了一個(gè)對(duì)象鎖，方法內(nèi)通過對(duì)象鎖實(shí)現(xiàn)；
• ConcurrentHashMap：使用分段鎖（CAS + synchronized相結(jié)合），降低了鎖粒度，大大提高并發(fā)度。

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望你能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評(píng)論