JDK HashMap詳解

HashMap的繼承關(guān)系如圖:

HashMap的繼承關(guān)系圖

初始空間大小 1<<4（16）
最大空間大小1 << 30 (1073741824)
哈希桶元素超過1杉允，鏈接方式默認(rèn)為鏈表形式民轴，數(shù)量超過TREEIFY_THRESHOLD的閾值(默認(rèn)8)將被轉(zhuǎn)換成紅黑樹
哈希桶的元素如果降低到UNTREEIFY_THRESHOLD的閾值(默認(rèn)6)會被重新轉(zhuǎn)換成鏈表形式
最小的哈希表容量為64(4倍TREEIFY_THRESHOLD值)
哈希表節(jié)點(diǎn)的類型為Node<K,V>(實(shí)現(xiàn)Map.Entry<K,V> 接口)

結(jié)構(gòu)為：
hash:哈希值
key:key
value:值
next:持有下一個節(jié)點(diǎn)的索引

put過程(以下是偽代碼，貼有部分jdk8的代碼實(shí)現(xiàn))：

計算key的哈希值
采用哈希算法
```
 int h;
 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
```
這里也是哈希能兼容key為null的原因

哈希算法為什么這樣寫?
右位移16位闹啦，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或勺拣，就是為了混合原始哈希碼的高位和低位竞思，以此來加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征娘荡，這樣高位的信息也被變相保留下來。
將hash驶沼，key炮沐，value移交給putVal方法處理
處理節(jié)點(diǎn)數(shù)據(jù)
1. 哈希表是空的：
  初始化哈希表，在初始化哈希表的過程中會進(jìn)行擴(kuò)容操作(resize()方法)會創(chuàng)建一個數(shù)組
  
  注意:實(shí)質(zhì)上初始化數(shù)組和數(shù)組容量達(dá)到當(dāng)前數(shù)組上限都會調(diào)用resize()方法并返回一個新的數(shù)組回怜，達(dá)到容量上限的時候大年，會將原有數(shù)組的值copy(遍歷到新的數(shù)組中)并返回新數(shù)組的引用,在擴(kuò)容的時候會將原有哈希表中的元素分散到新的哈希表中，因?yàn)闊o論如何計算哈西元素的時候當(dāng)前元素要么在當(dāng)前位置(j)要么在(j+oldCap)位置玉雾，形成新的哈希桶翔试，這樣可以快速確定元素位置，而不用去重新確定元素對于所有桶的位置复旬，這點(diǎn)很重要
2. 根據(jù)當(dāng)前key的哈希和當(dāng)前的數(shù)組長度計算數(shù)值將被賦予的哈希桶位置垦缅，并賦值給如果當(dāng)前哈希桶首元素為null，則創(chuàng)建一個新的node并賦予當(dāng)前哈希表位置
3. 如果不是null驹碍，則分為三種情況
  - map中已經(jīng)有當(dāng)前元素的key了.
    判定條件為：
    p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k)))
  - 當(dāng)前節(jié)點(diǎn)是一個TreeNode節(jié)點(diǎn)(超過了樹化閾值)
  - 沒有當(dāng)前元素并且不達(dá)到樹化條件,則添加元素到鏈表中并將引用存入node節(jié)點(diǎn)的next中,如果添加元素之后達(dá)到樹化條件壁涎，則將鏈表實(shí)現(xiàn)更新為紅黑樹的實(shí)現(xiàn)
  以下摘自網(wǎng)絡(luò)
  但是超過這個閾值后HashMap開始將列表升級成一個紅黑樹，使用哈希值作為樹的分支變量志秃，如果兩個哈希值不等怔球，但指向同一個桶的話，較大的那個會插入到右子樹里浮还。如果哈希值相等竟坛，HashMap希望key值最好是實(shí)現(xiàn)了Comparable接口的，這樣它可以按照順序來進(jìn)行插入碑定。這對HashMap的key來說并不是必須的流码，不過如果實(shí)現(xiàn)了當(dāng)然最好。如果沒有實(shí)現(xiàn)這個接口延刘，在出現(xiàn)嚴(yán)重的哈希碰撞的時候漫试，你就并別指望能獲得性能提升了。
4. 如果map中存在次元素則替換元素的值并提供拓展點(diǎn)afterNodeAccess(Node<K,V> p)來處理這類數(shù)據(jù)
5. 判定當(dāng)前容量已經(jīng)達(dá)到最大設(shè)置容量碘赖，如果達(dá)到給數(shù)組擴(kuò)容
6. 提供拓展點(diǎn)給子類提供添加之后的一些處理afterNodeInsertion(boolean evict)

get過程(以下是偽代碼驾荣，貼有部分jdk8的代碼實(shí)現(xiàn))：

鏈表查找：計算key的哈希值，并獲取當(dāng)前哈希桶普泡，判定當(dāng)前哈希桶中的首元素是不是需要的數(shù)據(jù)（進(jìn)行equals）比較播掷，如果不是，則依次遍歷節(jié)點(diǎn)后驅(qū)直至找到key對應(yīng)的node
遍歷紅黑樹：判定首節(jié)點(diǎn)的類型是否是TreeNode撼班，如果是從紅黑樹中獲取元素并返回

如果沒有查找到元素則返回null

 需要注意的是:
 containsKey()和containsValue()方法歧匈，其實(shí)質(zhì)還是遍歷一遍哈希桶，所以砰嘁，如果只是判定在map中含有這個數(shù)據(jù)件炉，用這個方法當(dāng)然更好勘究，但是如果需要這個數(shù)據(jù)做下一步運(yùn)算就用get判空效率更高，因?yàn)閏ontainsKey()之后再次get相當(dāng)于調(diào)用了兩次遍歷斟冕，效率相對下降許多

keySet()和values()方法:

keySet()和values()是因?yàn)閔ashMap繼承自AbstractMap口糕，它提供了超類實(shí)現(xiàn)將node中的key和value拆分到兩個set中(keySet和values())，在第一次調(diào)用的時候(new KeySet的時候和values()的時候會創(chuàng)建一個對象磕蛇，這個對象引用了key序列和value序列景描，這里并不需要去維護(hù)這個數(shù)組，只需要實(shí)現(xiàn)了set的迭代器name這個對象就會被索引到set里面(很神奇秀撇，我也驚訝了好久但是實(shí)驗(yàn)過后的確是這樣的))超棺，之后就能取得set里面的數(shù)據(jù)，但是這個set的數(shù)值發(fā)生改變捌袜，map本身的數(shù)據(jù)也會發(fā)生改變说搅，里面存放的只是對象的key/value引用炸枣。

ps:沒有人比我寫的更詳細(xì)了吧虏等，就問還有誰還有誰！Ｊ食Α霍衫！