HashMap你了解多少

HashMap幾乎是面試必問的知識，對于HashMap面試是你真的能從容面對嗎？相信如果你去面試知名互聯網公司的時候，決對不會只是問問你HashMap的數據結構這么簡單的問題。我收集了最近老大在面試過程中關于HashMap常問的幾個問題：

1. 為什么HashMap是2的冪次方？

new HashMap(14);

HashMap是由數組+鏈表（1.8還有紅黑樹）來實現的，那么上面這行代碼它執行后，創建的數組大小是多少呢？
追蹤源碼可以看到它會執行這樣一個函數來返回數組大小的：

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后面再多出來一個1
• 第二次右移并且或運算，可以保證從左到右再多出兩個1
• 以此類推，因為java中int值是4個字節，32位的，所以最后移16位的時候，足以保證2^32這種情況的出現；

• 通過這個函數的運算，可以將我們傳入的14運算得到16，也就是大于14的最小的2的n次冪。

上面說明了數組大小最后會保證是2的n次冪，那么接下來說說為什么要保證是2的n次冪

 static int indexFor(int h, int length) {
     return h & (length-1);
 }

在jdk1.7的時候，在put元素時，會執行這樣一段代碼片段，它的用意就是數據長度與hashCode值取余運算。那既然是取余，為什么不直接用%號呢？是因為位運算要比%運算高效很多。

那既然是&運算，又為什么非要保證length是2^n呢？

• 長度是2^n-1的話，可以保證&的結果是在hash表的大小范圍內；
• &運算與%取模的結果可以保證一致；

2. 為什么HashMap的擴容因子是0.75？

加載因子是非常重要的一塊，如果加載因子太大，假如為1，那么從空間利用率倒是上去了，但是時間效率就降低了。
如果加載因子太小，倒導致hashmap頻繁的擴容操作，每次擴容都非常耗性能；
好吧！說了就像沒說一樣，關于這個問題我也只能拋磚引玉；
其實是這樣的：

Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million

選擇0.75是空間和時間的一個折中，也并不是說，非必須是0.75，其它的編程語言也有配置成0.72的。

3. jdk1.7擴容時是怎么產生死循環的？

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];
                newTable[i] = e;
                e = next;
           }
       }
   }

說起這個話題，當時在網上找博客看是真沒有能看懂的，所以我盡量用圖的方式來表述

4. jdk1.8擴容時會產生死循環嗎？

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;
        }
        else {
                if (hiTail == null)
                        hiHead = e;
                else
                        hiTail.next = e;
                hiTail = e;
        }
} while ((e = next) != null);
if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;
}
if (hiTail != null) {
        hiTail.next = null;
        newTab[j + oldCap] = hiHead;
}

看下方圖文分析：

所以，jdk1.8中的HashMap在擴容時就不會產生死鎖了！

5. 為什么是鏈表長度達到8時轉為紅黑樹？

首先，TreeNode節點的占用空間的大小是鏈表節點的兩倍，只有當容器達到8的時候才轉為紅黑樹，為什么是8呢，在第二個問題中已經說明了，根據泊松分布可以看出，鏈表節點是很難達到長度為8的時候的，如果真有特殊情況達到8了，那么才將鏈表轉為紅黑樹；
轉為紅黑樹時還有個要求，就是hashMap中的元素個數達到64。

6. jdk1.8 HashMap是線程安全的嗎？

JDK1.8HashMap雖然能夠盡大的避免擴容時死循環問題，但是，HashMap仍然是線程不安全的，例如：線程A在put元素時，線程B進行擴容；
之所以不安全的原因是多線程會操作同一實例變化，導致變量狀態不一致；