HashMap幾乎是面試必問的知識(shí)，對(duì)于HashMap面試是你真的能從容面對(duì)嗎？相信如果你去面試知名互聯(lián)網(wǎng)公司的時(shí)候，決對(duì)不會(huì)只是問問你HashMap的數(shù)據(jù)結(jié)構(gòu)這么簡(jiǎn)單的問題。我收集了最近老大在面試過程中關(guān)于HashMap常問的幾個(gè)問題：
創(chuàng)新互聯(lián)建站專注于企業(yè)全網(wǎng)營銷推廣、網(wǎng)站重做改版、鶴山網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、HTML5、商城建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為鶴山等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
重慶分公司
重慶分公司
new HashMap(14);HashMap是由數(shù)組+鏈表（1.8還有紅黑樹）來實(shí)現(xiàn)的，那么上面這行代碼它執(zhí)行后，創(chuàng)建的數(shù)組大小是多少呢？
追蹤源碼可以看到它會(huì)執(zhí)行這樣一個(gè)函數(shù)來返回?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;
}
圖解：
通過這個(gè)函數(shù)的運(yùn)算，可以將我們傳入的14運(yùn)算得到16，也就是大于14的最小的2的n次冪。
上面說明了數(shù)組大小最后會(huì)保證是2的n次冪，那么接下來說說為什么要保證是2的n次冪
static int indexFor(int h, int length) {
return h & (length-1);
}在jdk1.7的時(shí)候，在put元素時(shí)，會(huì)執(zhí)行這樣一段代碼片段，它的用意就是數(shù)據(jù)長度與hashCode值取余運(yùn)算。那既然是取余，為什么不直接用%號(hào)呢？是因?yàn)槲贿\(yùn)算要比%運(yùn)算高效很多。
那既然是&運(yùn)算，又為什么非要保證length是2^n呢？
加載因子是非常重要的一塊，如果加載因子太大，假如為1，那么從空間利用率倒是上去了，但是時(shí)間效率就降低了。
如果加載因子太小，倒導(dǎo)致hashmap頻繁的擴(kuò)容操作，每次擴(kuò)容都非常耗性能；
好吧！說了就像沒說一樣，關(guān)于這個(gè)問題我也只能拋磚引玉；
其實(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è)折中，也并不是說，非必須是0.75，其它的編程語言也有配置成0.72的。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
while(null != e) {
Entry 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;
}
}
} 說起這個(gè)話題，當(dāng)時(shí)在網(wǎng)上找博客看是真沒有能看懂的，所以我盡量用圖的方式來表述
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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)生死鎖了！
首先，TreeNode節(jié)點(diǎn)的占用空間的大小是鏈表節(jié)點(diǎn)的兩倍，只有當(dāng)容器達(dá)到8的時(shí)候才轉(zhuǎn)為紅黑樹，為什么是8呢，在第二個(gè)問題中已經(jīng)說明了，根據(jù)泊松分布可以看出，鏈表節(jié)點(diǎn)是很難達(dá)到長度為8的時(shí)候的，如果真有特殊情況達(dá)到8了，那么才將鏈表轉(zhuǎn)為紅黑樹；
轉(zhuǎn)為紅黑樹時(shí)還有個(gè)要求，就是hashMap中的元素個(gè)數(shù)達(dá)到64。
JDK1.8HashMap雖然能夠盡大的避免擴(kuò)容時(shí)死循環(huán)問題，但是，HashMap仍然是線程不安全的，例如：線程A在put元素時(shí)，線程B進(jìn)行擴(kuò)容；
之所以不安全的原因是多線程會(huì)操作同一實(shí)例變化，導(dǎo)致變量狀態(tài)不一致；
