HashMap 源碼？原理？
HashMap采用Entry數(shù)組來存儲key-value對，每一個鍵值對組成了一個Entry實體，Entry類實際上是一個單向鏈表結(jié)構(gòu)，她具有next指針，可以連接下一個Entry實體。在JDK1.8中鏈表長度大于8 的時候，鏈表會變成紅黑樹。
為什么用數(shù)組+鏈表？
數(shù)組是用來確定桶的位置，利用key的hash值對數(shù)組長度取模得到。
鏈表是用來解決hash沖突問題的，當(dāng)出現(xiàn)hash值一樣的時候，就會在數(shù)組上對應(yīng)的位置形成一條鏈表。ps:這里的hash值并不是hashcode,而是將hashCode高低十六位異或過的。
解決hash沖突的辦法
開放地址法
鏈地址法
再哈希法
建立公共溢出區(qū)
LinkedList可以代替數(shù)組結(jié)構(gòu)嗎？那為什么HashMap不用LinkedList兒選用數(shù)組？
可以！
因為數(shù)組效率高！在HashMap中，定位桶的位置是利用元素的key的哈希值對數(shù)組長度取模得到。此時，我們已經(jīng)知道桶的位置，先讓數(shù)組的查找效率比LInkedList（鏈表，增刪快）大。
ArrayList底層也是數(shù)組，為什么不用？
基本數(shù)組結(jié)構(gòu)，可以自定義擴(kuò)容機(jī)制，HashMap中的數(shù)組擴(kuò)容機(jī)制剛好是2的次冪，在做取模運算的效率高。
ArrayList 是i1.5倍擴(kuò)容。
HashMap 在什么條件下擴(kuò)容？
如果bucket滿了（超過loadFactor * currentCapacity），就會擴(kuò)容resize。
loadFactor 為0.75，為了最大程度避免hash沖突。
currentCapacity 為當(dāng)前數(shù)組大小。
為什么擴(kuò)容是2的次冪？
HashMap為了存取高效，要盡量較少碰撞，就要盡量吧數(shù)據(jù)分配均勻，每個鏈表長度大致相同，這個實現(xiàn)就在把數(shù)組存到哪個鏈表的算法：取模，hash%length。
但是這種運算不如位運算，所以優(yōu)化為hash&（length - 1）
也就是說hash%length == hash&（length - 1）。
因為2的n次方實際就是1后面n個0,2的n次方-1，實際就是n個1.
例如：
長度為8的時候，3&（8-1）=3；2&（8-1）=2，不同位置上，不碰撞；
長度為5的時候，3&（5-1）=0；2&（5-1）=0，出現(xiàn)了碰撞；
所以，保證容積是2的n次方，是為了保證在做（length-1）的時候，每一位都能&1，也就是和11111......111111進(jìn)行與運算。
為什么要先高16位異或菂16位再取模運算？
這么做是為了降低hash沖突的幾率。
用上 高16位異或低16位的“擾動函數(shù)”后，就減少了碰撞的幾率。
HashMap中put元素的過程？
對key的hashCode() 做hash運算，計算index；
如果沒有碰撞直接放到bucket里；
-
如果碰撞了，以鏈表的形式存在bucket后，
如果碰撞導(dǎo)致鏈表長度過長（大于等于treeify_threshold），就要把鏈表轉(zhuǎn)換成紅黑樹；
如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)
如果bucket滿了（超過了loadFator*currentCapacity），就要resize。
HashMap中g(shù)et元素的過程？
對key的hashCode（）做hash運算，得到index；
如果bucket中的第一個節(jié)點直接命中，則直接返回；
如果有沖突，就通過key.equals(k)查找對應(yīng)Entry。
hash算法
Hash函數(shù)就是值把一個大范圍映射到一個小范圍。目的是為了節(jié)省空間，使得數(shù)據(jù)容易保存。
JDK1.8中的HashMap改了什么？
由數(shù)組+鏈表改為數(shù)組+鏈表+紅黑樹
優(yōu)化了高位運算的hash算法h^(h>>>16)
擴(kuò)容后，元素要么在原位置，要么在原位置再移動2次冪的位置，且鏈表順序不變。
為什么解決hash沖突的時候，不直接用紅黑樹？而先用鏈表，再轉(zhuǎn)紅黑樹？
因為紅黑樹需要左旋，右旋，變色等操作來保持平衡，而單鏈表不需要。
當(dāng)元素小于8個是，做查詢操作，鏈表結(jié)構(gòu)能夠保證查詢效率；當(dāng)元素大于8個是，此時需要紅黑樹來加快查詢速度，但是新增節(jié)點的效率變慢了。
因此，如果一開始就用紅黑樹結(jié)構(gòu)，元素太少，新增效率有比較慢，無疑是浪費性能的。
當(dāng)鏈表轉(zhuǎn)為紅黑樹后，什么時候退化成鏈表？
為6的時候退轉(zhuǎn)為鏈表，中間有個差值7可以防止鏈表和樹之間頻繁的轉(zhuǎn)換。如果設(shè)計成超過8個，鏈表就轉(zhuǎn)換成紅黑樹，少于8個再轉(zhuǎn)換成鏈表，如果一個HashMap不停的插入、刪除元素，鏈表元素在8個左右徘徊，就會頻繁的發(fā)生數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換，效率很低。
HashMap在并發(fā)編程下有什么問題？怎么解決？
多線程擴(kuò)容，引起的死循環(huán)問題
多線程put的時候可能導(dǎo)致元素丟失
put飛null的元素，get出來的是null
解決：
比如 使用ConcurrentHashMap、HashTable等線程安全集合類。
實現(xiàn)一個自定義的class作為HashMap的key該如何實現(xiàn)？
重寫hashCode和equals方法
-
如何設(shè)計一個不變類
類添加final修飾符，保證類不被繼承
保證所有成員變量必須私有，并加上final修飾
不提供改變成員變量的方法，包括setter
通過構(gòu)造器初始化所有成員，進(jìn)行深拷貝
如果構(gòu)造器傳?的對象直接賦值給成員變量，還是可以通過對傳?對象的修改進(jìn)?導(dǎo)致改變內(nèi)部變量的值。例如
這種?式不能保證不可變性，myArray和array指向同?塊內(nèi)存地址，??可以在ImmutableDemo之外通過修改array 對象的值來改變myArray內(nèi)部的值。
為了保證內(nèi)部的值不被修改，可以采?深度copy來創(chuàng)建?個新內(nèi)存保存?zhèn)?的值。正確做法：
- 在getter方法中，不要直接返回對象本身，而是克隆對象，并返回對象的拷貝。
這種做法也是防?對象外泄，防?通過getter獲得內(nèi)部可變成員對象后對成員變量直接操作，導(dǎo)致成員變量發(fā)?改變
