Q: HashMap什么時(shí)候會(huì)進(jìn)行擴(kuò)容？
HashMap在初始化時(shí)可以給定初始容量和負(fù)載因子，默認(rèn)的初始容量和負(fù)載因子16和0.75，也就是當(dāng)put完成后如果數(shù)據(jù)量大于12就會(huì)進(jìn)行第一次擴(kuò)容。
Q: java8對(duì)HashMap有什么優(yōu)化？
主要有兩個(gè)優(yōu)化，首先是在存儲(chǔ)hash沖突的元素時(shí)，如果桶位上沖突元素個(gè)數(shù)大于等于8個(gè)則轉(zhuǎn)換為紅黑樹(shù)存儲(chǔ)，加速尋找目標(biāo)元素。第二個(gè)是在擴(kuò)容時(shí)，由于每次擴(kuò)容都是乘2翻倍即左移一位，意味著數(shù)據(jù)擴(kuò)容后新的桶位有沒(méi)有變化，只與其hash值在擴(kuò)容位上的字位是否為1有關(guān)，如果是1的話，那新的桶位就是舊的hash值加舊容量，如果是0那桶位不變。位運(yùn)算的優(yōu)化加快了重hash的速度。
Q: LinkedHashMap和HashMap有什么區(qū)別？
LinkedHashMap會(huì)記錄數(shù)據(jù)插入或者訪問(wèn)的順序，內(nèi)部會(huì)持有head\tail兩個(gè)結(jié)點(diǎn)的引用，結(jié)點(diǎn)繼承了HashMap的結(jié)點(diǎn)實(shí)現(xiàn)并且多了兩個(gè)屬性分別保存結(jié)點(diǎn)的前驅(qū)和后繼。如果是記錄插入順序，那么在插入的時(shí)候會(huì)更新tail結(jié)點(diǎn)；如果是記錄訪問(wèn)順序，那么在get之后會(huì)更新tail結(jié)點(diǎn)。
Q: HashMap沖突鏈表轉(zhuǎn)紅黑樹(shù)的閾值為什么是8
紅黑樹(shù)結(jié)點(diǎn)占用的空間是鏈表結(jié)點(diǎn)的2倍，所以只會(huì)當(dāng)必要的情況下才使用紅黑樹(shù)。另外，在hash值能保證隨機(jī)分布的情況下，0.75的負(fù)載因子的hash沖突概率符合參數(shù)為0.5的泊松分布，當(dāng)k值為8的時(shí)候，概率已經(jīng)非常小了（10^-8數(shù)量級(jí)）。也就是正常情況下考慮到時(shí)空效率的平衡，會(huì)用鏈表來(lái)處理hash沖突，只有當(dāng)hash算法有問(wèn)題才會(huì)為了保存查詢(xún)效率使用紅黑樹(shù)處理沖突。
Q: 解決hash沖突的方式還有哪些？
除了hashmap所用的鏈地址法，一般還有以下方法：
- 再hash法。就是同時(shí)構(gòu)造多個(gè)hash方法，當(dāng)其中一個(gè)發(fā)生沖突時(shí)，就用下一個(gè)hash方法計(jì)算hash值，該方法缺點(diǎn)是增加了計(jì)算hash值的時(shí)間，在查詢(xún)的時(shí)候也要進(jìn)行多次hash計(jì)算。
- 建立公共溢出區(qū)。當(dāng)一個(gè)hash值產(chǎn)生沖突時(shí)，會(huì)把沖突的數(shù)據(jù)放到溢出區(qū)中，相應(yīng)的在查詢(xún)的時(shí)候也需要遍歷溢出區(qū)。
- 開(kāi)放定址法。就是當(dāng)發(fā)送hash沖突時(shí)，會(huì)加一個(gè)數(shù)字然后再進(jìn)行hash，直到找到空位。該數(shù)字可以是線性的1，2，3...也可以是二次方或者一個(gè)隨機(jī)數(shù)。在查找的時(shí)候需要做匹配操作，如果hash值相同但是不匹配，說(shuō)明存在hash沖突，需要根據(jù)規(guī)則找到下一個(gè)桶位，如果找到的桶位是空值則說(shuō)明不存在。由于查找方法的需要，刪除數(shù)據(jù)時(shí)不能真的刪除而是記錄刪除標(biāo)志，然后在下次插入數(shù)據(jù)時(shí)進(jìn)行覆蓋。
Q: HashMap在高并發(fā)的情況下有什么問(wèn)題？
首先是在java1.8之前hashmap在擴(kuò)容時(shí)，多線程環(huán)境下處理沖突鏈可能會(huì)造成死循環(huán)，1.8之后對(duì)擴(kuò)容的邏輯進(jìn)行了優(yōu)化，不會(huì)再出現(xiàn)死循環(huán)的，但是還是會(huì)有其他很多問(wèn)題，例如put數(shù)據(jù)的時(shí)候size++就不是一個(gè)原子操作，多線程環(huán)境下會(huì)出現(xiàn)計(jì)數(shù)錯(cuò)誤的問(wèn)題；并且多線程put hash值相同的元素時(shí)，也可能會(huì)造成數(shù)據(jù)被覆蓋丟失的問(wèn)題；紅黑樹(shù)插入、刪除涉及的旋轉(zhuǎn)邏輯也是線程不安全的。
Q: ConcurrentHashMap是怎么處理并發(fā)問(wèn)題的？
ConcurrentHashMap在put的時(shí)候以CAS的方式訪問(wèn)、設(shè)置存儲(chǔ)數(shù)據(jù)的數(shù)組，并在發(fā)生hash沖突的時(shí)候以synchronized的同步方式處理沖突，也就是相當(dāng)于每個(gè)桶位都在put的時(shí)候有一個(gè)獨(dú)立的鎖，只有當(dāng)處理同一個(gè)hash值的時(shí)候才會(huì)發(fā)生資源競(jìng)爭(zhēng)。而在get數(shù)據(jù)的時(shí)候，如果hash值相符且equals為true則直接返回結(jié)果，如果hash值為負(fù)，則看該結(jié)點(diǎn)的類(lèi)型，如果是正在遷移的結(jié)點(diǎn)則到新表中查詢(xún)，如果是樹(shù)節(jié)點(diǎn)則調(diào)用紅黑樹(shù)的搜索方法進(jìn)行查詢(xún)，由于紅黑樹(shù)的讀寫(xiě)是互斥的所以會(huì)有讀鎖。如果是鏈表結(jié)點(diǎn)則遍歷鏈表。
Q: java8對(duì)ConcurrentHashMap有什么優(yōu)化？
java7是以分段鎖的形式上鎖，而java8是每一個(gè)桶位都有一把鎖，允許不同桶位之間的操作可以并發(fā)進(jìn)行。
