實(shí)面試題之：Hashmap的結(jié)構(gòu)，1.7和1.8有哪些區(qū)別
不同點(diǎn)：
（1）JDK1.7用的是頭插法，而JDK1.8及之后使用的都是尾插法，那么他們?yōu)槭裁匆@樣做呢？因?yàn)镴DK1.7是用單鏈表進(jìn)行的縱向延伸，當(dāng)采用頭插法時(shí)會(huì)容易出現(xiàn)逆序且環(huán)形鏈表死循環(huán)問題。但是在JDK1.8之后是因?yàn)榧尤肓思t黑樹使用尾插法，能夠避免出現(xiàn)逆序且鏈表死循環(huán)的問題。
（2）擴(kuò)容后數(shù)據(jù)存儲(chǔ)位置的計(jì)算方式也不一樣：
- 在JDK1.7的時(shí)候是直接用hash值和需要擴(kuò)容的二進(jìn)制數(shù)進(jìn)行&（這里就是為什么擴(kuò)容的時(shí)候?yàn)樯兑欢ū仨毷?的多少次冪的原因所在，因?yàn)槿绻挥?的n次冪的情況時(shí)最后一位二進(jìn)制數(shù)才一定是1，這樣能最大程度減少hash碰撞）（hash值 & length-1）
- 而在JDK1.8的時(shí)候直接用了JDK1.7的時(shí)候計(jì)算的規(guī)律，也就是擴(kuò)容前的原始位置+擴(kuò)容的大小值=JDK1.8的計(jì)算方式，而不再是JDK1.7的那種異或的方法。但是這種方式就相當(dāng)于只需要判斷Hash值的新增參與運(yùn)算的位是0還是1就直接迅速計(jì)算出了擴(kuò)容后的儲(chǔ)存方式。
在計(jì)算hash值的時(shí)候，JDK1.7用了9次擾動(dòng)處理=4次位運(yùn)算+5次異或，而JDK1.8只用了2次擾動(dòng)處理=1次位運(yùn)算+1次異或。
擴(kuò)容流程對(duì)比圖：
這里再進(jìn)行補(bǔ)充兩個(gè)問題：
（1）為什么在JDK1.7的時(shí)候是先進(jìn)行擴(kuò)容后進(jìn)行插入，而在JDK1.8的時(shí)候則是先插入后進(jìn)行擴(kuò)容的呢？
//其實(shí)就是當(dāng)這個(gè)Map中實(shí)際插入的鍵值對(duì)的值的大小如果大于這個(gè)默認(rèn)的閾值的時(shí)候（初始是16*0.75=12）的時(shí)候才會(huì)觸發(fā)擴(kuò)容， //這個(gè)是在JDK1.8中的先插入后擴(kuò)容
if (++size > threshold)
resize();
其實(shí)這個(gè)問題也是JDK8對(duì)HashMap中，主要是因?yàn)閷?duì)鏈表轉(zhuǎn)為紅黑樹進(jìn)行的優(yōu)化，因?yàn)槟悴迦脒@個(gè)節(jié)點(diǎn)的時(shí)候有可能是普通鏈表節(jié)點(diǎn)，也有可能是紅黑樹節(jié)點(diǎn)，但是為什么1.8之后HashMap變?yōu)橄炔迦牒髷U(kuò)容的原因，我也有點(diǎn)不是很理解？歡迎來討論這個(gè)問題？
但是在JDK1.7中的話，是先進(jìn)行擴(kuò)容后進(jìn)行插入的，就是當(dāng)你發(fā)現(xiàn)你插入的桶是不是為空，如果不為空說明存在值就發(fā)生了hash沖突，那么就必須得擴(kuò)容，但是如果不發(fā)生Hash沖突的話，說明當(dāng)前桶是空的（后面并沒有掛有鏈表），那就等到下一次發(fā)生Hash沖突的時(shí)候在進(jìn)行擴(kuò)容，但是當(dāng)如果以后都沒有發(fā)生hash沖突產(chǎn)生，那么就不會(huì)進(jìn)行擴(kuò)容了，減少了一次無用擴(kuò)容，也減少了內(nèi)存的使用
void addEntry(int hash, K key, V value, int bucketIndex) { //這里當(dāng)錢數(shù)組如果大于等于12（假如）閾值的話，并且當(dāng)前的數(shù)組的Entry數(shù)組還不能為空的時(shí)候就擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) { //擴(kuò)容數(shù)組，比較耗時(shí)
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
} void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//把新加的放在原先在的前面，原先的是e，現(xiàn)在的是new，next指向e
table[bucketIndex] = new Entry<>(hash, key, value, e);//假設(shè)現(xiàn)在是new
size++;
}
2）為什么在JDK1.8中進(jìn)行對(duì)HashMap優(yōu)化的時(shí)候，把鏈表轉(zhuǎn)化為紅黑樹的閾值是8,而不是7或者不是20呢（面試蘑菇街問過）？
如果選擇6和8（如果鏈表小于等于6樹還原轉(zhuǎn)為鏈表，大于等于8轉(zhuǎn)為樹），中間有個(gè)差值7可以有效防止鏈表和樹頻繁轉(zhuǎn)換。假設(shè)一下，如果設(shè)計(jì)成鏈表個(gè)數(shù)超過8則鏈表轉(zhuǎn)換成樹結(jié)構(gòu)，鏈表個(gè)數(shù)小于8則樹結(jié)構(gòu)轉(zhuǎn)換成鏈表，如果一個(gè)HashMap不停的插入、刪除元素，鏈表個(gè)數(shù)在8左右徘徊，就會(huì)頻繁的發(fā)生樹轉(zhuǎn)鏈表、鏈表轉(zhuǎn)樹，效率會(huì)很低。
還有一點(diǎn)重要的就是由于treenodes的大小大約是常規(guī)節(jié)點(diǎn)的兩倍，因此我們僅在容器包含足夠的節(jié)點(diǎn)以保證使用時(shí)才使用它們，當(dāng)它們變得太?。ㄓ捎谝瞥蛘{(diào)整大小）時(shí)，它們會(huì)被轉(zhuǎn)換回普通的node節(jié)點(diǎn)，容器中節(jié)點(diǎn)分布在hash桶中的頻率遵循泊松分布，桶的長度超過8的概率非常非常小。所以作者應(yīng)該是根據(jù)概率統(tǒng)計(jì)而選擇了8作為閥值
//Java中解釋的原因
* 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
二、哈希表如何解決Hash沖突
三、為什么HashMap具備下述特點(diǎn)：鍵-值（key-value）都允許為空、線程不安全、不保證有序、存儲(chǔ)位置隨時(shí)間變化
四、為什么 HashMap 中 String、Integer 這樣的包裝類適合作為 key 鍵
五、HashMap 中的 key若 Object類型， 則需實(shí)現(xiàn)哪些方法？
