HashMap幾乎是面試必問的知識,對于HashMap面試是你真的能從容面對嗎?相信如果你去面試知名互聯(lián)網(wǎng)公司的時候,決對不會只是問問你HashMap的數(shù)據(jù)結(jié)構(gòu)這么簡單的問題。我收集了最近老大在面試過程中關(guān)于HashMap常問的幾個問題:
創(chuàng)新互聯(lián)建站專注于企業(yè)全網(wǎng)營銷推廣、網(wǎng)站重做改版、鶴山網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、HTML5、商城建設(shè)、集團公司官網(wǎng)建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù),價格優(yōu)惠性價比高,為鶴山等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。
new HashMap(14);
HashMap是由數(shù)組+鏈表(1.8還有紅黑樹)來實現(xiàn)的,那么上面這行代碼它執(zhí)行后,創(chuàng)建的數(shù)組大小是多少呢?
追蹤源碼可以看到它會執(zhí)行這樣一個函數(shù)來返回數(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;
}
圖解:
通過這個函數(shù)的運算,可以將我們傳入的14運算得到16,也就是大于14的最小的2的n次冪。
上面說明了數(shù)組大小最后會保證是2的n次冪,那么接下來說說為什么要保證是2的n次冪
static int indexFor(int h, int length) {
return h & (length-1);
}
在jdk1.7的時候,在put元素時,會執(zhí)行這樣一段代碼片段,它的用意就是數(shù)據(jù)長度與hashCode值取余運算。那既然是取余,為什么不直接用%號呢?是因為位運算要比%運算高效很多。
那既然是&運算,又為什么非要保證length是2^n呢?
加載因子是非常重要的一塊,如果加載因子太大,假如為1,那么從空間利用率倒是上去了,但是時間效率就降低了。
如果加載因子太小,倒導(dǎo)致hashmap頻繁的擴容操作,每次擴容都非常耗性能;
好吧!說了就像沒說一樣,關(guān)于這個問題我也只能拋磚引玉;
其實是這樣的:
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的。
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;
}
}
}
說起這個話題,當(dāng)時在網(wǎng)上找博客看是真沒有能看懂的,所以我盡量用圖的方式來表述
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在擴容時就不會產(chǎn)生死鎖了!
首先,TreeNode節(jié)點的占用空間的大小是鏈表節(jié)點的兩倍,只有當(dāng)容器達(dá)到8的時候才轉(zhuǎn)為紅黑樹,為什么是8呢,在第二個問題中已經(jīng)說明了,根據(jù)泊松分布可以看出,鏈表節(jié)點是很難達(dá)到長度為8的時候的,如果真有特殊情況達(dá)到8了,那么才將鏈表轉(zhuǎn)為紅黑樹;
轉(zhuǎn)為紅黑樹時還有個要求,就是hashMap中的元素個數(shù)達(dá)到64。
JDK1.8HashMap雖然能夠盡大的避免擴容時死循環(huán)問題,但是,HashMap仍然是線程不安全的,例如:線程A在put元素時,線程B進(jìn)行擴容;
之所以不安全的原因是多線程會操作同一實例變化,導(dǎo)致變量狀態(tài)不一致;
分享標(biāo)題:HashMap你了解多少
URL鏈接:http://muchs.cn/article8/pichop.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供微信小程序、全網(wǎng)營銷推廣、面包屑導(dǎo)航、企業(yè)建站、搜索引擎優(yōu)化、關(guān)鍵詞優(yōu)化
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)