Java-基礎-HashMap
1. 簡介
Java8 HashMap結構（數組 + 列表 + 紅黑樹）如圖：
基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。 此實現假定哈希函數將元素適當地分布在各桶之間，可為基本操作（get 和 put）提供穩定的性能。迭代 collection 視圖所需的時間與 HashMap 實例的「容量」（桶的數量）及其大小（鍵-值映射關係數）成比例。所以，如果迭代性能很重要，則不要將初始容量設置得太高（或將載入因子設置得太低）。
2. 定義
2.1 主要屬性
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//序列號，序列化的時候使用。
private static final long serialVersionUID = 362498820763181265L;
/**默認容量，1向左移位4個，00000001變成00010000，也就是2的4次方為16，使用移位是因為移位是電腦基礎運算，效率比加減乘除快。**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，2的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//負載因子，用於擴容使用。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當某個桶節點數量大於8時，會轉換為紅黑樹。
static final int TREEIFY_THRESHOLD = 8;
//當某個桶節點數量小於6時，會轉換為鏈表，前提是它當前是紅黑樹結構。
static final int UNTREEIFY_THRESHOLD = 6;
//當整個hashMap中元素數量大於64時，也會進行轉為紅黑樹結構。
static final int MIN_TREEIFY_CAPACITY = 64;
//存儲元素的數組，transient關鍵字表示該屬性不能被序列化
transient Node<K,V>[] table;
//將數據轉換成set的另一種存儲形式，這個變數主要用於迭代功能。
transient Set<Map.Entry<K,V>> entrySet;
//元素數量
transient int size;
//統計該map修改的次數
transient int modCount;
//臨界值，也就是元素數量達到臨界值時，會進行擴容。
int threshold;
//也是負載因子，只不過這個是變數。
final float loadFactor;
}
2.2 構造方法
HashMap共有三個構造函數：
初始化一個默認容量=16，負載因子=0.75 的hashmap對象。
public HashMap() {
// DEFAULT_LOAD_FACTOR = 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
初始化一個指定初始容量和負載因子-0.75 的hashmap對象。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
初始化一個指定初始容量和負載因子 的HashMap對象。
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);
}
2.3 node
Node是HashMap的靜態內部類，HashMap主幹是一個Node數組，Node是HashMap的最基本組成單位。
/**
* HashMap 的Node 節點元素
* @param <K> 元素的key
* @param <V> 元素的Value
*/
static class Node<K,V> implements Map.Entry<K,V> {
// 這個節點所在位置的hash值
final int hash;
//這個節點的Key
final K key;
//這個節點的value
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; }
/**
* 獲取HashCode
* key和value 的hash做異或運算 防止hash衝突
* @return
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 設置value
* @param newValue
* @return
*/
public final V setValue(V newValue) {
V oldValue = value;
//替換當前node的value
value = newValue;
//返回舊的value
return oldValue;
}
/**
* equals 比較
* 如果 key和value都一致 判斷equals相等
* @param o
* @return
*/
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;
}
}
3. 初始容量 負載因子
上文中反覆提到了兩個參數：初始容量，負載因子。這兩個參數是影響HashMap性能的重要參數。
容量：transient Node<K,V>[] table; 即 table的長度，初始容量是創建哈希表時的容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 即初始容量為 16。
負載因子： final float loadFactor; 容器進行初始化的時候會將值設置為0.75 ( 也就是初始可用的容量為：16 * 0.75 = 12，當容量達到12的時候就會進行擴容操作)，負載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散列表的空間使用程度，負載因子越大表示散列表的裝填程度越高，反之越小。
為什麼說 容量 和 負載因子 會影響 HashMap的性能？
我們在考慮HashMap的時候，首先要想到HashMap只是一個數據結構，既然是數據結構最主要的就是節省時間和空間。負載因子的作用肯定是節省時間和空間。為什麼節省呢？
-
假設 負載因子 = 1.0
HashMap是將key進行hash運算得到桶的位置（table的索引）的。既然是hash運算，那麼Hash衝突是避免不了的。當負載因子是1.0的時候，意味著會出現大量的Hash衝突（因為要將整個table填滿，並且為了將數均勻填充，jdk還使用了擾動函數，增加隨機性），底層的紅黑樹會變的異常複雜。對查詢效率極其不利。這種情況就是犧牲了時間來保證空間的利用率。
-
假設 負載因子 = 0.5
負載因子是0.5的時候，也就意味著，當數組中的元素達到了一半就開始擴容，既然填充的元素好了，Hash衝突也會減少，那麼底層的鏈表或者紅黑樹的高度就會降低。查詢效率就會增加。但是，這時候空間利用率就會大大降低，顯然也不太好。
總結：
默認容量 = 16，負載因子 = 0.75，這兩個常量的值都是經過大量的計算和統計得出來的最優解。
當然 如果知道自己的hashmap容量大小，盡量在初始化的時候就指定一下，可以避免擴容帶來的性能損耗。但負載因子就別隨意改了，畢竟是最優解。
4. 添加元素
put方法是一個重點方法，這裡有hashmap的初始化，數據的在hashmap中是如何存儲的，什麼情況下會轉換成紅黑樹等。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* putVal 方法 真正進行插入操作的方法，
*
* @param hash 傳入key的哈希值
* @param key
* @param value
* @param onlyIfAbsent 如果該值是true,如果存在值就不會進行修改操作
* @param evict LinekdHashMap尾操作使用，這裡暫無用途
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
/**********初始化********/
// 如果table長度是0或table是null會調整一次大小
// 這時tab會指向調整大下後的Node<K,V>[](主幹數組)
// n被賦值為新數組長度
// 如果沒有調整大小，tab指向table
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
/********開始查找鍵的位置，並存儲value*******/
// i = (n - 1) & hash這個是獲取key應該在哪個桶里,下面詳說
// 這裡將p指向當前key所需要的那個桶
if ((p = tab[i = (n - 1) & hash]) == null) {
// 如果空桶，也就是無哈希衝突的情況，直接丟個Node進去。
// 此時的tab就是table
tab[i] = newNode(hash, key, value, null);
//存在衝突，開始尋找我們要找的節點
} else {
Node<K, V> e;
K k;
// 判斷第一個節點是不是我們找的
// 此時k儲存了 p.key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
// hash值相等，key值相等，定位完成,是修改操作
// e來儲存p這個節點，一會修改
e = p;
// 判斷是否是紅黑樹節點
} else if (p instanceof TreeNode) {
// 是紅黑樹節點，存在就返回那個節點，不存在就返回null
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 最終，是鏈表了，開始對鏈表遍歷查找
} else {
for (int binCount = 0; ; ++binCount) {
// 上面知道第一個接點不是我們要的，直接獲取下一個，並儲存給e
// 下一個是空，直接丟個Node在這裡，然後p.next指向這裡
// 這裡下一個節點地址給了e
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// ！大於樹化閥值，開始樹化
// 注意-1是因為binCount是索引而不是長度
// 其實此時鏈表長度已經是7+1（索引） + 1（新進來的Node）
// 已經大於樹化閥值8，也就是說鏈表長度為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;
}
}
// 上面說了，這有修改操作e才能不是null
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 給e新值
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
// 這個是LinkedHashMap用的，HashMap里是個空實現
afterNodeAccess(e);
// 修改就會把舊值返回去
return oldValue;
}
}
/*********修改完成的後續操作**********/
// 修改次數加1
++modCount;
// 如果size大於閥值，會執行resize()方法調整大小
if (++size > threshold) {
resize();
}
// 這個是給LinkedHashMap用的，HashMap里也是個空實現
afterNodeInsertion(evict);
// 添加成功返回null
return null;
}
hash方法 擾動函數
/**
* hash 運算
* @param key
* @return
*/
static final int hash(Object key) {
int h;
/**
* key是null就返回0，key不是null就先取hashCode（）
* 然後與這個hashCode（）無符號右移進行亦或運算
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到了熟悉的hashCode，這就解釋了為什麼重寫equals方法的時候，一定要重寫hashCode方法，因為key是基於hashCode來處理的。
為什麼 獲取了key的hashcode() 返回的int型的散列值還要異或（^）h >>> 16 呢？ 有什麼用？
實質上是把一個數的低16位與它的高16位做異或運算，混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來。
**那為什麼要增加低16位的隨機性呢？ **
根本目的是為了增加 散列表的裝填程度，為了使數據分布的更均勻。
因為在找key的位置tab[i = (n - 1) & hash])，是通過(n - 1) & hash 計算索引位置的，而當n的長度不夠大時，只和hashCode()的低16位有關。
這樣做有幾個好處：
- &運算速度快，至少比%取模運算快
- 能保證 索引值 肯定在 capacity 中，不會超出數組長度
- ( n -1) & hash，當n為2次冪時，會滿足一個公式：
(n -1) & hash = hash % n
5. 擴容方法
擴容的三種情況：
- 使用默認構造方法初始化HashMap。從前文可以知道HashMap在一開始初始化的時候會返回一個空的table，並且thershold為0。因此第一次擴容的容量為默認值DEFAULT_INITIAL_CAPACITY也就是16。同時threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
- 指定初始容量的構造方法初始化HashMap。那麼從下面源碼可以看到初始容量會等於threshold，接著threshold = 當前的容量（threshold） * DEFAULT_LOAD_FACTOR。
- HashMap不是第一次擴容。如果HashMap已經擴容過的話，那麼每次table的容量以及threshold量為原有的兩倍
這邊也可以引申到一個問題就是HashMap是先插入數據再進行擴容的，但是如果是剛剛初始化容器的時候是先擴容再插入數據。
5.1 擴容部分
/**
* 擴容方法
*
* @return
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
// 原容量，table為null返回0，否則返回table長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原始閾值
int oldThr = threshold;
//新容量，新閾值
int newCap, newThr = 0;
// table已經初始化，舊容量>0
if (oldCap > 0) {
// 容量已經超過最大容量，直接返回去
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
// 2倍擴容後小於最大容量，並且原容量大於默認初始化容量(我還沒想清楚為什麼要大於默認初始容量)
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
// 閥值加倍
newThr = oldThr << 1; // double threshold
}
// 原數組容量為0，未初始化，但閥值不為0
// 也就是構造方法里threshold = tableSizeFor(initialCapacity）這個步驟
} else if (oldThr > 0) { // initial capacity was placed in threshold
newCap = oldThr;
// 啥都沒有，默認構造
}else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新數組閥值未被賦值
if (newThr == 0) {
// 使用新的容量*負載因子計算閥值
float ft = (float) newCap * loadFactor;
// 取計算後閥值和最大容量里較小的那個
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
threshold = newThr;
5.2 複製數據部分
// 創建新的數組
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
//開始複製數據
if (oldTab != null) {
//開始遍歷
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;
//如果是紅黑樹，分裂放入新數組
} 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里
next = e.next;
// 該節點不需要移動
if ((e.hash & oldCap) == 0) {
// 尾元素為空，說明鏈表為空，確定為首元素
if (loTail == null) {
loHead = e;
} else {
// 尾元素有就將元素放進尾元素的後繼節點
loTail.next = e;
}
// 確定尾元素
loTail = e;
// 該節點需要移動
} else {
// 尾元素為空，說明鏈表為空，確定為首元素
if (hiTail == null) {
hiHead = e;
} else {
// 尾元素有就將元素放進尾元素的後繼節點
hiTail.next = e;
}
// 確定尾元素
hiTail = e;
}
//直到遍歷完鏈表跳出
} while ((e = next) != null);
// 把兩個首元素放在兩個桶里就可以了
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新的數組
return newTab;
