JDK1.8之前的HashMap
在JDK1.8之前，HashMap通過(guò)散列表(哈希表)實(shí)現(xiàn)，并且散列表沖突解決方案是鏈地址法(拉鏈法)，也可理解為數(shù)組+鏈表實(shí)現(xiàn)。
在java編程語(yǔ)言中普气，最基本的結(jié)構(gòu)就是兩種，一個(gè)是數(shù)組佃延，另外一個(gè)是模擬指針（引用）现诀，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來(lái)構(gòu)造的夷磕，HashMap也不例外。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)仔沿，即數(shù)組和鏈表的結(jié)合體坐桩。
什么是散列表？
一塊連續(xù)的存儲(chǔ)空間中于未，用以存儲(chǔ)按散列函數(shù)計(jì)算得到相應(yīng)散列地址的數(shù)據(jù)記錄撕攒。通常散列表的存儲(chǔ)空間是一個(gè)一維數(shù)組，散列地址是數(shù)組的下標(biāo)烘浦。
重溫?cái)?shù)據(jù)結(jié)構(gòu)_散列表/哈希表的查找
向HashMap存儲(chǔ)元素：
向HashMap中存儲(chǔ)某元素時(shí)候抖坪，首先hash算法根據(jù)元素的key值得到一個(gè)hash值，這個(gè)hash值就可以確定元素在數(shù)組中的位置闷叉。如果此位置沒有元素擦俐，直接存；如果已經(jīng)存在元素握侧，就要與它們的key進(jìn)行比較蚯瞧，有以下兩種情況：1.key相同的，覆蓋舊值品擎；2.key都不同埋合，形成一個(gè)以新元素為頭部的鏈表。
從HashMap獲取元素：
先根據(jù)key的hash算法得到hash值萄传，找到該元素在數(shù)組中的位置甚颂；再通過(guò)key的equals方法，在鏈表中找到對(duì)應(yīng)的元素秀菱，也就找到了key對(duì)應(yīng)的value振诬。
JDK1.8的HashMap
HashMap通過(guò)數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)，當(dāng)鏈表長(zhǎng)度超過(guò)閾值（8）時(shí)衍菱，將鏈表轉(zhuǎn)換為紅黑樹赶么，并且再次之后都用紅黑樹來(lái)存儲(chǔ)沖突的元素。
為什么JDK1.8HashMap要做如此改變脊串？
我們都知道在鏈表中查找節(jié)點(diǎn)時(shí)辫呻，會(huì)花費(fèi)O（n）的查找時(shí)間项钮。為了防止拉鏈過(guò)長(zhǎng)，導(dǎo)致嚴(yán)重影響HashMap的性能刽宪，當(dāng)鏈表長(zhǎng)度超過(guò)閾值（8）時(shí)悬嗓，不再采用單鏈表形式存儲(chǔ)，而是采用紅黑樹存儲(chǔ)读串，利用紅黑樹快速增刪改查的特點(diǎn)提高HashMap的性能。
JDK1.8 HashMap源碼分析
重要的字段
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K, V>[] table;
/**
* The number of key-value mappings contained in this map.
* 包含在map中鍵-值對(duì)的數(shù)量
*/
transient int size;
/**
* hashmap被結(jié)構(gòu)化改變的次數(shù)
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
* 擴(kuò)容的閾值，當(dāng)size大于這個(gè)值時(shí)念赶，table數(shù)組進(jìn)行擴(kuò)容
*/
int threshold;
/**
* The load factor for the hash table.
*
*/
float loadFactor;
對(duì)這些重要字段的解釋：
- table：Node[] table的初始化長(zhǎng)度length默認(rèn)值是16础钠；
- loadFactor ：負(fù)載因子默認(rèn)值是0.75；
- threshold ：是HashMap所能容納的最大數(shù)量的Node(鍵值對(duì))個(gè)數(shù)叉谜。
負(fù)載因子的定義公式：threshold = length * loadFactor旗吁。也就是說(shuō)，在數(shù)組定義好長(zhǎng)度之后停局，負(fù)載因子越大很钓，所能容納的鍵值對(duì)個(gè)數(shù)越多。
當(dāng)size超過(guò)這個(gè)數(shù)目就重新resize(擴(kuò)容)董栽，擴(kuò)容后的HashMap容量是之前容量的兩倍码倦。默認(rèn)的負(fù)載因子0.75是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇，建議大家不要修改锭碳，除非在時(shí)間和空間比較特殊的情況下袁稽，如果內(nèi)存空間很多而又對(duì)時(shí)間效率要求很高，可以降低負(fù)載因子Load factor的值擒抛；相反推汽，如果內(nèi)存空間緊張而對(duì)時(shí)間效率要求不高，可以增加負(fù)載因子loadFactor的值歧沪，這個(gè)值可以大于1歹撒。
- size：包含在map中鍵-值對(duì)的實(shí)際數(shù)量。注意和table的長(zhǎng)度length诊胞、容納最大鍵值對(duì)數(shù)量threshold的區(qū)別暖夭。
- modCount：主要用來(lái)記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)。需要注意的是內(nèi)部結(jié)構(gòu)發(fā)生變化真正意義是元素的key從來(lái)沒有被put過(guò)厢钧。
如何確定key對(duì)應(yīng)哈希桶數(shù)組索引位置鳞尔？
通過(guò)這個(gè)Java方法運(yùn)算來(lái)獲取hash碼值：
static final int hash(Object key) {
int h;
//取key的hashCode值、高位運(yùn)算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
通過(guò)hash方法得到的hash碼值早直，還不是數(shù)組的下標(biāo)編號(hào)寥假，還差一步，這一步就是hash碼值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算霞扬，具體代碼如下圖紅框糕韧。
下圖是得到key在數(shù)組具體位置索引號(hào)的過(guò)程：
### 重要方法分析
#### 靜態(tài)內(nèi)部類Node
Node是HashMap的一個(gè)靜態(tài)內(nèi)部類，實(shí)現(xiàn)了Map.Entry接口喻圃，表示一個(gè)映射條目或者說(shuō)是鍵值對(duì)萤彩。
static class Node<K,V> implements Map.Entry<K,V> {
//根據(jù)hash方法計(jì)算出來(lái)的值，作為定位數(shù)組位置的索引
final int hash;
final K key;
V value;
Node<K,V> next;//該Node指向的下一個(gè)Node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
HashMap的put方法實(shí)現(xiàn)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
