????????面試core java，HashMap的結(jié)構(gòu)差不多是必問(wèn)題了。字面意思，真的真的是必問(wèn)題了。

? ? ? ? 我遇到的問(wèn)題有：

??????????1. HashMap, ConcurrentHashMap,HashTable 的結(jié)構(gòu)，在JDK 1.7 和1.8 中有什么不同（最基礎(chǔ)）

? ? ? ? ? ?2. put時(shí)，是加到鏈表頭還是鏈表尾

? ? ? ? ? ?3. get的時(shí)間復(fù)雜度（對(duì)鏈表，對(duì)紅黑樹(shù)）

????????然后，在一次糟心的面試中，面試官問(wèn)問(wèn)題1 ，我回答了，提到了loadfactor = 0.75， 對(duì)方來(lái)了句“這個(gè)都記，背得挺熟的嘛” ， 我：？？？(黑人問(wèn)號(hào)臉)。?

????????他問(wèn)，那你說(shuō)，為什么是0.75 ， 不是0.5或者1？

????????這個(gè)好回答。 如果是0.5 ， 那么每次達(dá)到容量的一半就進(jìn)行擴(kuò)容，默認(rèn)容量是16， 達(dá)到8就擴(kuò)容成32，達(dá)到16就擴(kuò)容成64， 最終使用空間和未使用空間的差值會(huì)逐漸增加，空間利用率低下。 ?如果是1，那意味著每次空間使用完畢才擴(kuò)容，在一定程度上會(huì)增加put時(shí)候的時(shí)間。

????????接著，他問(wèn)我為什么是0.75，不是0.6或者0.8？

? ? ? ? 我：……?

========================

? ? ? ? 面試只是檢測(cè)知識(shí)的一個(gè)經(jīng)歷。 回頭再想想：那為什么是0.75呢？ 0.75是 0.5 ～ 1的中間值？?（寫(xiě)到這里，突然想這樣解釋也可以哎，取中間值）

? ? ? ? 然后我去查看了API...

? ? ? ? JDK 1.7中：

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

翻譯過(guò)來(lái)就是：

作為一般規(guī)則，默認(rèn)負(fù)載因子（0.75）在時(shí)間和空間成本上提供了很好的折衷。較高的值會(huì)降低空間開(kāi)銷(xiāo)，但提高查找成本（體現(xiàn)在大多數(shù)的HashMap類(lèi)的操作，包括get和put）。設(shè)置初始大小時(shí)，應(yīng)該考慮預(yù)計(jì)的entry數(shù)在map及其負(fù)載系數(shù)，并且盡量減少rehash操作的次數(shù)。如果初始容量大于最大條目數(shù)除以負(fù)載因子，rehash操作將不會(huì)發(fā)生。

? ? JDK 1.8中也有上述內(nèi)容，并且還有一段如下（現(xiàn)在頭腦清醒了，覺(jué)得下面這段與“為什么是0.75”關(guān)系不大，不過(guò)是百度中能找到的關(guān)于這個(gè)問(wèn)題的別人的文章中有著一段）：

Ideally, under random hashCodes, the frequency of nodes in bins follows a 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

簡(jiǎn)單翻譯一下，就是 ：

理想狀態(tài)下，在隨機(jī)哈希值的情況，對(duì)于loadfactor = 0.75 ，雖然由于粒度調(diào)整會(huì)產(chǎn)生較大的方差，桶中的Node的分布頻率服從參數(shù)為0.5的泊松分布。?

（泊松分布算是我在這個(gè)沒(méi)什么意思的探討中學(xué)到的新的知識(shí)點(diǎn)吧，比較通俗易懂的解釋在這里 ）

在上面給出的結(jié)果中，t=1，λ=0.5，推算得各種結(jié)果。這個(gè)我自己寫(xiě)程序?qū)崿F(xiàn)了一下，沒(méi)錯(cuò)。但這個(gè)地方跟0.75沒(méi)關(guān)系，實(shí)際上是在JDK1.8中，如果鏈表的長(zhǎng)度大于8，那么鏈表轉(zhuǎn)為紅黑樹(shù) 這個(gè)操作得來(lái)的。

那么，回到問(wèn)題，0.75是怎么得來(lái)的呢？StackOverFlow上有這么一個(gè)回答我覺(jué)得可以給我結(jié)案了：

原鏈接如下：What is the significance of load factor in HashMap?

這個(gè)回答的釋義是： 一個(gè)bucket空和非空的概率為0.5，通過(guò)牛頓二項(xiàng)式等數(shù)學(xué)計(jì)算，得到這個(gè)loadfactor的值為log（2），約等于0.693. 同回答者所說(shuō)，可能小于0.75 大于等于log（2）的factor都能提供更好的性能，0.75這個(gè)數(shù)說(shuō)不定是 pulled out of a hat。

==========================

昨天和我學(xué)金融的著重號(hào)朋友討論這個(gè)問(wèn)題，最后她說(shuō)

其實(shí)我就是不喜歡面試官陰陽(yáng)怪氣地說(shuō)一句“這都背下來(lái)了”，你說(shuō)你考我問(wèn)題，又覺(jué)得我是背的，那你期待我怎么表現(xiàn)？？回答不上來(lái)？哎，過(guò)去就過(guò)去了。

總結(jié)一下：

為什么是0.75？ 這個(gè)我沒(méi)找到一個(gè)肯定完整的答案，這個(gè)問(wèn)題比較偏，問(wèn)到的幾率很小。但經(jīng)過(guò)探討，你可以回答

1. 取 0.5和1 的缺點(diǎn)是什么， 同時(shí)說(shuō)一下上面第一段引用的JDK API，就說(shuō)API中也沒(méi)有說(shuō)為什么取0.75.

2. 對(duì)方如果是個(gè)杠精，你可以深入理解一下stackoverflow中的這個(gè)計(jì)算，然后告訴他。 如果對(duì)方考你高數(shù)……我也沒(méi)辦法了，記得來(lái)我這里領(lǐng)一個(gè)愛(ài)的抱抱。

============================

學(xué)到了什么：?

1. 泊松分布和指數(shù)分布，順便回想一下正態(tài)分布

2. 氣場(chǎng)不和的面試官要用正確的心態(tài)去面對(duì)。