在JDK1.6，JDK1.7中，HashMap采用數(shù)組+鏈表實(shí)現(xiàn)，而JDK1.8中，HashMap采用數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)。以JDK1.7的為例，HashMap里面的每個(gè)元素都是通過鍵值對(duì)key,value形式存儲(chǔ)的。首先它會(huì)通過key來計(jì)算對(duì)應(yīng)的哈希值，并把key,value,hash值，下一個(gè)元素的地址封裝成一個(gè)Entry對(duì)象；然后再通過讓哈希值求模的形式來確定Entry對(duì)象在數(shù)組中的位置。假設(shè)在數(shù)組的下標(biāo)為2的位置，那么首先會(huì)看下標(biāo)為2的位置上是不是空，如果為空就直接將Entry對(duì)象放到2位置；如果下標(biāo)為2的位置不為空，則會(huì)發(fā)生哈希碰撞，這時(shí)候需要遍歷該位置元素下的鏈表，看看哈希值和key值是不是都相同，如果相等則覆蓋原來的元素，如果不相等則在頭節(jié)點(diǎn)追加元素形成鏈表形式。
DEFAULT_INITIAL_CAPACITY：默認(rèn)的初始化容量，1<<4位運(yùn)算的結(jié)果是16，也就是默認(rèn)的初始化容量為16，容量大小需要是2的整數(shù)倍。
MAXIMUM_CAPACITY：容量的最大值，1 << 30位，2的30次冪。
DEFAULT_LOAD_FACTOR：默認(rèn)的加載因子。
TREEIFY_THRESHOLD：因?yàn)閖dk8以后，HashMap底層的存儲(chǔ)結(jié)構(gòu)改為了數(shù)組+鏈表+紅黑樹的存儲(chǔ)結(jié)構(gòu)（之前是數(shù)組+鏈表），剛開始存儲(chǔ)元素產(chǎn)生碰撞時(shí)會(huì)在碰撞的數(shù)組后面掛上一個(gè)鏈表，當(dāng)鏈表長(zhǎng)度大于這個(gè)參數(shù)時(shí)，鏈表就可能會(huì)轉(zhuǎn)化為紅黑樹(為什么是可能后面還有一個(gè)參數(shù)，需要他們兩個(gè)都滿足的時(shí)候才會(huì)轉(zhuǎn)化)。
UNTREEIFY_THRESHOLD：介紹上面的參數(shù)時(shí)，我們知道當(dāng)長(zhǎng)度過大時(shí)可能會(huì)產(chǎn)生從鏈表到紅黑樹的轉(zhuǎn)化，但是，元素不僅僅只能添加還可以刪除，或者另一種情況，擴(kuò)容后該數(shù)組槽位置上的元素?cái)?shù)據(jù)不是很多了，還使用紅黑樹的結(jié)構(gòu)就會(huì)很浪費(fèi)，所以這時(shí)就可以把紅黑樹結(jié)構(gòu)變回鏈表結(jié)構(gòu)，什么時(shí)候變，就是元素?cái)?shù)量等于這個(gè)值也就是6的時(shí)候變回來（元素?cái)?shù)量指的是一個(gè)數(shù)組槽內(nèi)的數(shù)量，不是HashMap中所有元素的數(shù)量）。
MIN_TREEIFY_CAPACITY：鏈表樹化的一個(gè)標(biāo)準(zhǔn)，前面說過當(dāng)數(shù)組槽內(nèi)的元素?cái)?shù)量大于8時(shí)可能會(huì)轉(zhuǎn)化為紅黑樹，之所以說是可能就是因?yàn)檫@個(gè)值，當(dāng)數(shù)組的長(zhǎng)度小于這個(gè)值的時(shí)候，會(huì)先去進(jìn)行擴(kuò)容，擴(kuò)容之后就有很大的可能讓數(shù)組槽內(nèi)的數(shù)據(jù)可以更分散一些了，也就不用轉(zhuǎn)化數(shù)組槽后的存儲(chǔ)結(jié)構(gòu)了。當(dāng)然，長(zhǎng)度大于這個(gè)值并且槽內(nèi)數(shù)據(jù)大于8時(shí)，那就轉(zhuǎn)化為紅黑樹吧。
引入紅黑樹是為了避免hash性能急劇下降，引起HashMap的讀寫性能急劇下降的場(chǎng)景，正常情況下，一般是不會(huì)用到紅黑樹的，在一些極端場(chǎng)景下，假如客戶端實(shí)現(xiàn)了一個(gè)性能拙劣的hashCode方法，可以保證HashMap的讀寫復(fù)雜度不會(huì)低于O(lgN)。
加載因子是用于表示數(shù)組中元素填滿的程度。加載因子默認(rèn)值是0.75。如果不指明初始大小，數(shù)組默認(rèn)大小即初始容量為16，加載因子loadFactor=0.75，默認(rèn)初始容量是16*0.75=12。如果填充比為0.5則空間利用率比較低。如果填充比1，說明利用的空間很多，那么形成沖突的機(jī)會(huì)就會(huì)越大，鏈表也會(huì)邊長(zhǎng)，這樣查找的成本就變高。
關(guān)于這個(gè)默認(rèn)容量的選擇，JDK并沒有給出官方解釋，那么這應(yīng)該就是個(gè)經(jīng)驗(yàn)值，既然一定要設(shè)置一個(gè)默認(rèn)的2^n 作為初始值，那么就需要在效率和內(nèi)存使用上做一個(gè)權(quán)衡。這個(gè)值既不能太小，也不能太大。太小了就有可能頻繁發(fā)生擴(kuò)容，影響效率。太大了又浪費(fèi)空間，不劃算。所以，16就作為一個(gè)經(jīng)驗(yàn)值被采用了。
不可以。從key映射到HashMap的數(shù)組的對(duì)應(yīng)位置時(shí)，會(huì)用到一個(gè)hash函數(shù):index = HashCode（Key）&（Length - 1）;
如果Length的長(zhǎng)度為奇數(shù)，假設(shè)長(zhǎng)度為15， Length-1轉(zhuǎn)換為二進(jìn)制后為 1110 ,假設(shè)此時(shí)的hashCode為 101110001110101110 1011, 做&運(yùn)算得出的index結(jié)果為: 101110001110101110 1010, 如果此時(shí)的hashCode為101110001110101110 1010,同樣的做&運(yùn)算，發(fā)現(xiàn)得出啦相同的index。看似好像沒有很大的問題，因?yàn)槲覀冊(cè)谟胔ashmap的時(shí)候出現(xiàn)哈希值相等的情況還是有的。再看一種情況，如果長(zhǎng)度為9，那么Length-1 轉(zhuǎn)換為二進(jìn)制的結(jié)果為1000, 那么只要hashCode的最后三位不相同，計(jì)算出來的結(jié)果仍然是一樣的，那么此時(shí)的index會(huì)更容易出現(xiàn)，并且此時(shí)的index的最后三位永遠(yuǎn)不會(huì)出現(xiàn)111的情況，這樣的話，不符合Hash算法的均勻分布原則。
假如長(zhǎng)度為16,那么length-1對(duì)應(yīng)的二進(jìn)制位1111,那么計(jì)算哈希code的時(shí)不會(huì)影響index出現(xiàn)的概率，符合均勻分布的設(shè)計(jì)原則。 因此HashMap的長(zhǎng)度一般為2^n, 默認(rèn)的長(zhǎng)度為16。
如果一直不進(jìn)行擴(kuò)容的話，鏈表就會(huì)越來越長(zhǎng)，這樣查找的效率很低，因?yàn)殒湵淼拈L(zhǎng)度很大（當(dāng)然最新版本使用了紅黑樹后會(huì)改進(jìn)很多），擴(kuò)容之后，將原來鏈表數(shù)組的每一個(gè)鏈表分成奇偶兩個(gè)子鏈表分別掛在新鏈表數(shù)組的散列位置，這樣就減少了每個(gè)鏈表的長(zhǎng)度，增加查找效率。
JDK7的HashMap是數(shù)組+鏈表實(shí)現(xiàn)的，JDK8的HashMap是數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)的；
當(dāng)某個(gè)key-value對(duì)需要存儲(chǔ)到數(shù)組中時(shí)，需要先生成一個(gè)數(shù)組下標(biāo)index，并且這個(gè)index不能越界。在HashMap中，先得到key的hashcode，hashcode是一個(gè)數(shù)字，然后通過hashcode & (table.length - 1) 運(yùn)算得到一個(gè)數(shù)組下標(biāo)index，是通過與運(yùn)算計(jì)算出來一個(gè)數(shù)組下標(biāo)的，而不是通過取余，與運(yùn)算相比于取余運(yùn)算速度更快，但是也有一個(gè)前提條件，就是數(shù)組的長(zhǎng)度得是一個(gè)2的冪次方數(shù)。
HashMap在多線程并發(fā)時(shí)線程不安全，主要表現(xiàn)在下面兩個(gè)方面：
(1) 當(dāng)向HashMap中put(添加)元素時(shí)導(dǎo)致的多線程數(shù)據(jù)不一致
比如有兩個(gè)線程 A 和 B ，首先 A 希望插入一個(gè) key-value鍵值對(duì)到HashMap 中，它首先計(jì)算記錄所要落到的 hash 桶的索引坐標(biāo)，然后獲取到該桶里面的鏈表頭結(jié)點(diǎn)，此時(shí)線程 A 的時(shí)間片用完了，而此時(shí)線程 B 被調(diào)度得以執(zhí)行，和線程 A 一樣執(zhí)行，只不過線程 B 成功將記錄插到了桶里面。假設(shè)線程 A 插入的記錄計(jì)算出來的 hash 桶索引和線程 B 要插入的記錄計(jì)算出來的 hash 桶索引是一樣的，那么當(dāng)線程 B 成功插入之后，線程 A 再次被調(diào)度運(yùn)行時(shí)，它依然持有過期的鏈表頭但是它對(duì)此一無所知，以至于它認(rèn)為它應(yīng)該這樣做，如此一來就覆蓋了線程 B 插入的記錄，這樣線程 B 插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為。
簡(jiǎn)單來說就是在多線程環(huán)境下，向HashMap集合中添加元素會(huì)存在覆蓋的現(xiàn)象，導(dǎo)致了線程不安全。
(2) 當(dāng)HashMap進(jìn)行擴(kuò)容調(diào)用resize()函數(shù)時(shí)引起死循環(huán)
HashMap在put的時(shí)候，插入的元素超過了容量（由負(fù)載因子決定）的范圍就會(huì)觸發(fā)擴(kuò)容操作，就是rehash，這個(gè)會(huì)重新將原數(shù)組的內(nèi)容重新hash到新的擴(kuò)容數(shù)組中，在多線程的環(huán)境下，存在同時(shí)其他的元素也在進(jìn)行put操作，如果hash值相同，可能出現(xiàn)同時(shí)在同一數(shù)組下用鏈表表示，造成閉環(huán)，導(dǎo)致在get時(shí)會(huì)出現(xiàn)死循環(huán)，所以HashMap是線程不安全的。
HashMap的線程不安全主要體現(xiàn)在下面兩個(gè)方面：
1.在JDK1.7中，當(dāng)并發(fā)執(zhí)行擴(kuò)容操作時(shí)會(huì)造成環(huán)形鏈和數(shù)據(jù)丟失的情況。
2.在JDK1.8中，在并發(fā)執(zhí)行put操作時(shí)會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。
get(key)方法 ：
● 首先獲取key的hash值，計(jì)算hash&(n-1)得到在數(shù)組中的位置first=tab[hash&(n-1)]
● 先判斷first的key是否與參數(shù)key相等，不等就遍歷后面的鏈表找到相同的key值返回對(duì)應(yīng)的Value值即可
put(key,value)方法：
● 1)判斷鍵值對(duì)數(shù)組tab[]是否為空或?yàn)閚ull，否則以默認(rèn)大小resize()；
● 2)根據(jù)鍵值key計(jì)算hash值，hash值再計(jì)算得到插入的數(shù)組索引i，如果tab[i]==null，直接新建節(jié)點(diǎn)添加，否則轉(zhuǎn)入3
● 3)判斷當(dāng)前數(shù)組中處理hash沖突的方式為鏈表還是紅黑樹(check第一個(gè)節(jié)點(diǎn)類型即可),分別處理。
1. hashMap默認(rèn)的負(fù)載因子是0.75，即如果hashmap中的元素個(gè)數(shù)超過了總?cè)萘?5%，則會(huì)觸發(fā)擴(kuò)容
2. 如果某個(gè)桶中的鏈表長(zhǎng)度大于等于8了，則會(huì)判斷當(dāng)前的hashmap的容量是否大于64，如果小于64，則會(huì)進(jìn)行擴(kuò)容；如果大于64，則將鏈表轉(zhuǎn)為紅黑樹。
1. 擾動(dòng)函數(shù)：促使元素位置分布均勻，減少碰撞幾率
2. 使用final對(duì)象，并采用合適的equals()和hashCode()方法
京公網(wǎng)安備 11030102010736號(hào)