Java基礎之HashMap的原理

講到HashMap不得不講到HashCode，百度HashCode，它的釋義如下
哈希碼并不是完全唯一的，它是一種算法，讓同一個類的對象按照自己不同的特征盡量的有不同的哈希碼，但不表示不同的對象哈希碼完全不同。也有相同的情況，看程序員如何寫哈希碼的算法。
HashCode是用來在散列存儲結構中確定對象的存儲地址，HashMap正是利用HashCode來快速定位存儲對象的。
上面說過HashCode并不是唯一的，他取決于設計的哈希算法，所以在HashMap會出現Hash沖突的情況，那HashMap是怎么處理這種問題的呢？答案是在產生沖突的地方使用鏈表和紅黑樹。
在JDK1.8之前解決hash沖突使用的是鏈表，實際上初始化后的HashMap就是由長度為1的單向鏈表組成的數組，在發生hash沖突時，該節點的單向鏈表保存具有相同hashcode的對象。在JDK1.8之后，當節點的單向鏈表長度大于8時，改為使用紅黑樹，提高查找效率。
HashMap是日常開發中非常常用的容器，HashMap實現了Map接口，底層的實現原理是哈希表，HashMap不是一個線程安全的容器，jdk8對HashMap做了一些改進，作為開發人員需要對HashMap的原理有所了解，現在就通過源碼來了解HashMap的實現原理。
首先看HashMap中的屬性
//Node數組
transient Node<K,V>[] table;
//當前哈希表中k-v對個數，實際就是node的個數
transient int size;
//修改次數
transient int modCount;
//元素閾值
int threshold;
//負載因子
final float loadFactor;
這里的threshold = loadFactor * table.length，hash表如果想要保持比較好的性能，數組的長度通常要大于元素個數，默認的負載因子是0.75，用戶可以自行修改，不過最好使用默認的負載因子。
Node是用來存儲KV的節點，每次put(k,v)的時候就會包裝成一個新的Node, Node定義
static class Node<K,V> implements Map.Entry<K,V> {
//hash值
final int hash;
final K key;
V value;
//hash & (capacity - 1) 相同的Node會形成一個鏈表
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;
}
}
put操作
寫入操作是map中最常用的方法，這里看看hashmap的put方法代碼
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里先計算key的hash值，然后調用putVal()方法，其中hash方法是內部自帶的一個算法，會對key的hashcode再做一次hash操作

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
pubVal方法
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; //如果數組為空，先初始化一下
if ((p = tab[i = (n - 1) & hash]) == null) //如果對應的數組為空的話，那么就直接new一個node然后塞進去
tab[i] = newNode(hash, key, value, null);
else { //如果有值，說明發生了沖突，那么就先用拉鏈法來處理沖突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果頭結點的key和要插入的key相同，那么就說明找到了之前插入的節點
else if (p instanceof TreeNode) //如果鏈表轉成了紅黑樹
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //如果之前沒有put過這個節點，那么就new一個新的節點
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//另外要檢查一下當前鏈表的長度，如果超過8那么就將鏈表轉化成紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果找到了之前的節點，那么就跳出
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //在當前類中NOOP
return oldValue;
}
}
++modCount;
//如果當前元素數量大于門限值，就要resize整個hash表，實際上就是把數組擴大一倍，然后將所有元素重新塞到新的hash表中
if (++size > threshold)
resize();
afterNodeInsertion(evict); //在該類中NOOP
return null;
}
在hashtable中默認的出現沖突的時候就會將沖突的元素形成一個鏈表，當鏈表長度大于8的時候就會將鏈表變成一個二叉樹，這是java8中做出的改進，因為在使用hash表的時候在key特殊的情況下最壞的時候hash表會退化成一個鏈表，那么原有的O(1)的時間復雜度就變成了O(n)，性能就會大打折扣，但是引用了紅黑樹之后那么在最好的情況下時間復雜度就變成了O(log(n))。
resize方法
final Node<K, V> [] resize() {
......
//去掉了一些代碼，只關注最核心的node遷移
//resize會新建一個數組，數組的長度是原來數組長度的兩倍
for (int j = 0; j < oldCap; ++j) {//遍歷原來的數組
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; //如果沒有形成鏈表的話，就直接塞到新的hash表中
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //紅黑樹操作？？
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //如果hash值小于oldCap的時候，那么就還在原來那個數組的位置，就把這個節點放到low鏈表中
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //否則的話就是因為擴展數組長度，就把原來的節點放到high鏈表中
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; //low鏈表還放在原來的位置
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; //high鏈表放到j+oldCap位置上
}
}
}
}
}
resize操作就是創建一個先的數組，然后把老的數組中的元素塞到新的數組中，注意java8中的hashMap中數組長度都是2的n次冪,2、4、、8、16….. 這樣的好處就是可以通過與操作來替代求余操作。當數組擴大之后，那么每個元素所在的位置是可以預期的，就是要不就待在原來的位置，要不就是到j+oldCap位置上，舉個栗子，如果原來數組長度為4，那么hash為3和7 的元素都會放在index為3的位置上，當數組長度變成8的時候，hash為3的元素還待在index為3的位置，hash為7的元素此時就要放到index為7的位置上。
resize操作是一個很重要的操作，resize會很消耗性能，因此在創建hashMap的時候最好先預估容量，防止重復創建拷貝。
另外hashmap也是非線程安全的，在多線程操作的時候可能會產生cpu100%的情況，主要的原因也是因為在多個線程resize的時候導致鏈表產生了環，這樣下次get操作的時候就會容易進入死循環。
get方法（）
get的實現比較簡單
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) //如果節點不為空而且頭結點與查找的key相同就返回
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);//從紅黑樹中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null); //遍歷鏈表查找key相同的node
}
}
return null;
}
HashMap的常量和構造函數
//默認初始容量，這個值必須是2的次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
//最大容量，也必須設置成2的次冪
static final int MAXIMUM_CAPACITY = 1 << 30; // 1 073 741 824
//負載因子默認大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//節點保存數據數量超過這個值，由鏈表轉為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//當節點保存數據數量小于該值，紅黑樹轉為鏈表存儲
static final int UNTREEIFY_THRESHOLD = 6;
//紅黑樹最小長度
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap中實際就是用這樣一個元素類型為Node<K,V>的數組來存儲數據，該數組長度必須為2的次冪
//每個Node本質上就是一個單向鏈表
transient Node<K,V>[] table;
//HashMap大小,它代表HashMap保存的鍵值對的多少
transient int size;
//HashMap被改變的次數
transient int modCount;
//HashMap擴容的閾值，保存鍵值對個數大于它就要擴容
int threshold;
//存儲負載因子的常量
final float loadFactor;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
//根據loadFactor以及MAXIMUM_CAPACITY再次計算出新的threshold
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//數量超過閾值擴容
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
HashMap中的元素單向鏈表Node是Map.Entry<K,V>的實現，可以看到每一個Node只有next屬性，沒有pre屬性，是一個單向鏈表
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;
}
}
HashMap中的紅黑樹也是自己實現的，這里就不詳細列出其實現
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//省略...
}
HashMap主要常用API get和put方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//使用key參與hash運算后得出的hash，找出該位置的鏈表節點的第一個元素first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//總是先檢查鏈表第一個元素first是否匹配，匹配上就返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//匹配不上，就使用first的next屬性找到下一個節點e
if ((e = first.next) != null) {
//先判斷第一個節點是否是紅黑樹節點,是則在紅黑樹中查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果不是紅黑樹節點，再循環遍歷該位置單向鏈表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//以上都無法匹配就返回null
return null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
//如果使用該hash計算出XM返傭www.fx61.com/brokerlist/xm.html的位置沒有元素，就把元素保存在這個位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果該位置有數據，且該節點Node的hash和key都與傳入值相同或調用傳入鍵對象的equals方法與節點Node的key比較相同，則覆蓋該數據
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果上面的if判斷不滿足，且該位置節點Node是紅黑樹類型，使用紅黑樹保存
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果if滿足也不是紅黑樹類型節點，則找出該位置單向鏈表最后一個位置的元素，把它的next指向新傳入數據保存位置
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//添加完后，若該節點鏈表長度超過8，則轉換為紅黑樹
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;
}
為什么HashMap的容量必須設置為2的次冪呢？
其實主要是為了在哈希算法中減少碰撞，使數據均勻分布。這里就不深究了。