HashMap幾乎是面試必問(wèn)的知識(shí)，對(duì)于HashMap面試是你真的能從容面對(duì)嗎？相信如果你去面試知名互聯(lián)網(wǎng)公司的時(shí)候，決對(duì)不會(huì)只是問(wèn)問(wèn)你HashMap的數(shù)據(jù)結(jié)構(gòu)這么簡(jiǎn)單的問(wèn)題。我收集了最近老大在面試過(guò)程中關(guān)于HashMap常問(wèn)的幾個(gè)問(wèn)題：

公司主營(yíng)業(yè)務(wù)：成都做網(wǎng)站、網(wǎng)站制作、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。成都創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。成都創(chuàng)新互聯(lián)推出新林免費(fèi)做網(wǎng)站回饋大家。

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

new HashMap(14);

HashMap是由數(shù)組+鏈表（1.8還有紅黑樹(shù)）來(lái)實(shí)現(xiàn)的，那么上面這行代碼它執(zhí)行后，創(chuàng)建的數(shù)組大小是多少呢？
追蹤源碼可以看到它會(huì)執(zhí)行這樣一個(gè)函數(shù)來(lái)返回?cái)?shù)組大小的：

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

圖解：

• 第一次右移并且或運(yùn)算，可以保證從左到右第一位1后面再多出來(lái)一個(gè)1
• 第二次右移并且或運(yùn)算，可以保證從左到右再多出兩個(gè)1
• 以此類(lèi)推，因?yàn)閖ava中int值是4個(gè)字節(jié)，32位的，所以最后移16位的時(shí)候，足以保證2^32這種情況的出現(xiàn)；

• 通過(guò)這個(gè)函數(shù)的運(yùn)算，可以將我們傳入的14運(yùn)算得到16，也就是大于14的最小的2的n次冪。

上面說(shuō)明了數(shù)組大小最后會(huì)保證是2的n次冪，那么接下來(lái)說(shuō)說(shuō)為什么要保證是2的n次冪

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

在jdk1.7的時(shí)候，在put元素時(shí)，會(huì)執(zhí)行這樣一段代碼片段，它的用意就是數(shù)據(jù)長(zhǎng)度與hashCode值取余運(yùn)算。那既然是取余，為什么不直接用%號(hào)呢？是因?yàn)槲贿\(yùn)算要比%運(yùn)算高效很多。

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

• 長(zhǎng)度是2^n-1的話，可以保證&的結(jié)果是在hash表的大小范圍內(nèi)；
• &運(yùn)算與%取模的結(jié)果可以保證一致；

2. 為什么HashMap的擴(kuò)容因子是0.75？

加載因子是非常重要的一塊，如果加載因子太大，假如為1，那么從空間利用率倒是上去了，但是時(shí)間效率就降低了。
如果加載因子太小，倒導(dǎo)致hashmap頻繁的擴(kuò)容操作，每次擴(kuò)容都非常耗性能；
好吧！說(shuō)了就像沒(méi)說(shuō)一樣，關(guān)于這個(gè)問(wèn)題我也只能拋磚引玉；
其實(shí)是這樣的：

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是空間和時(shí)間的一個(gè)折中，也并不是說(shuō)，非必須是0.75，其它的編程語(yǔ)言也有配置成0.72的。

3. jdk1.7擴(kuò)容時(shí)是怎么產(chǎn)生死循環(huán)的？

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

說(shuō)起這個(gè)話題，當(dāng)時(shí)在網(wǎng)上找博客看是真沒(méi)有能看懂的，所以我盡量用圖的方式來(lái)表述

4. jdk1.8擴(kuò)容時(shí)會(huì)產(chǎn)生死循環(huán)嗎？

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在擴(kuò)容時(shí)就不會(huì)產(chǎn)生死鎖了！

5. 為什么是鏈表長(zhǎng)度達(dá)到8時(shí)轉(zhuǎn)為紅黑樹(shù)？

首先，TreeNode節(jié)點(diǎn)的占用空間的大小是鏈表節(jié)點(diǎn)的兩倍，只有當(dāng)容器達(dá)到8的時(shí)候才轉(zhuǎn)為紅黑樹(shù)，為什么是8呢，在第二個(gè)問(wèn)題中已經(jīng)說(shuō)明了，根據(jù)泊松分布可以看出，鏈表節(jié)點(diǎn)是很難達(dá)到長(zhǎng)度為8的時(shí)候的，如果真有特殊情況達(dá)到8了，那么才將鏈表轉(zhuǎn)為紅黑樹(shù)；
轉(zhuǎn)為紅黑樹(shù)時(shí)還有個(gè)要求，就是hashMap中的元素個(gè)數(shù)達(dá)到64。

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

JDK1.8HashMap雖然能夠盡大的避免擴(kuò)容時(shí)死循環(huán)問(wèn)題，但是，HashMap仍然是線程不安全的，例如：線程A在put元素時(shí)，線程B進(jìn)行擴(kuò)容；
之所以不安全的原因是多線程會(huì)操作同一實(shí)例變化，導(dǎo)致變量狀態(tài)不一致；

創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。

標(biāo)題名稱：HashMap你了解多少-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://chinadenli.net/article30/digspo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、小程序開(kāi)發(fā)、網(wǎng)站導(dǎo)航、網(wǎng)站排名、企業(yè)建站、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)