首先，我們要了解一下HashMap的存儲方式
既然名字包含Hash，不難看出他是以hash值作為位址存儲的，更确切的講他是以哈希桶aka鍊位址的方式存儲元素的
如果不了解什麼是哈希桶，或者想先看一下HashMap的實作特點參見——HashMap實作特點——基于JDK文檔
哈希沖突采用的是哈希桶，桶中元素使用連結清單存儲，但是如果元素過多，那麼就會采用樹的方式存儲。樹是HashMap中最重要的資料結構。
首先我們要通過源碼分析HashMap的存儲以及操作。
- HashMap()構造方法
- putVal()方法
- resize()方法
HashMap是按照下面圖示方式存儲元素（如果沒有哈希沖突），一個數組，數組中元素叫做節點也就是桶，是以首先我們需要了解節點。如果有哈希沖突，那麼每個節點的桶就會存多個元素，文章下面有。
下面是内部類Node：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
可以看到，是一個很常見的節點的表達方式，下面這個圖就沒有寫hash，因為hash使用制定存放位址的，這裡的next一般是為了解決哈希沖突而設定的，本篇文章下面還有一幅圖更詳細
建立HashMap對象後，隻有使用它，它才會初始化，也就是put語句，使用put後
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//其餘省略，因為隻運作了條件為真的
}
@pass是指由于條件語句為假是以不運作改語句塊
是以由于table為空，是以初始化也就是運作resize方法，tab = resize();調用了resize()方法
繼續向下看：
final Node<K,V>[] resize() {
//初始化table數組，或者加倍，先讨論初始化
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldCap = 0;
//threshold: The next size value at which to resize (capacity * load factor).
int oldThr = threshold;
int newCap, newThr = 0;
@pass
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
@pass
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//運作這一步。因為oldThr初始為0
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
@pass
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//threshold初始化了
//開始建立一個Node數組，大小為newCap
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//table賦予值
table = newTab;
@pass
//下面代碼也被省略
return newTab;
}
目前就完成了初始化，得到一個預設容量的連結清單，然後繼續執行putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//############################################################################
//上面已經執行過了，是以不用管，繼續看下面
//在條件語句中 i = 0
if ((p = tab[i = (n - 1) & hash]) == null)
tab[0]也就是首元素 = newNode();是以我們繼續看newNode()方法
tab[i] = newNode(hash, key, value, null);
else {
//由于條件語句，跳過這些代碼
}
//...也省略
return null;
}
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
可以看到他是建立節點的函數，繼續調用Node的構造方法，上面已經介紹了Node和它的構造方法，是以傳回了一個新的節點，由于這是第一個節點，也就是頭節點。繼續添加節點和上面步驟一樣，不過需要注意的是，當遇到hash沖突時，也就是我們要存放一個元素，根據其hash值存放，不過檢測到原節點數組該位置已經有元素，并且他們兩個的key值不一樣，這就遇到了hash沖突，是以我們會執行哈希桶，也就是鍊位址法去解決沖突，如果不了解哈希桶，可以參見我另一篇文章；
下面我介紹一下哈希沖突元素的添加：（從第一個哈希沖突介紹）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//上面代碼忽略，因為條件語句跳過。
//運作下面這一句，p就擷取了目前hash位址的節點，并且不為空，是以執行else中語句
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//p已經被找到為舊節點
//如果p.hash = hash p存放key = k，說明找到節點，并且沒有出現hash沖突，e = p；
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//哈希沖突
//因為p目前是第一個hash沖突元素，是以不運作下面這段
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//因為是第一個hash沖突，是以p.next = null;
if ((e = p.next) == null) {
//先建立一個存放沖突節點的。此時沖突node之間是線性連接配接的
p.next = newNode(hash, key, value, null);
//哈希沖突數量過多就用類似TreeMap的形式存儲
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//執行
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
此圖就講解了Hash沖突的解決方案。如果哈希桶中元素過多會使用樹去代替連結清單，樹在HashMap中是很重要的一個結構，足足占了600行代碼。以後會專門講解。