資訊專欄INFORMATION COLUMN
摘要：哈希碰撞的概率取決于計算方式和空間容量的大小。超過后執行擴容操作。當一個哈希桶存儲的鏈表長度大于會將鏈表轉換成紅黑樹，小于時則從紅黑樹轉換成鏈表。換句話來說，就是為了減少哈希碰撞。紅黑樹相關的操作雖然代碼不同，但是實際上要干的事情是一樣的。
前言
學習情況記錄
學習情況記錄
時間：week 3
SMART子目標 ：Java 容器
記錄在學習Java容器 知識點中，關于HashMap的需要重點記錄的知識點。
知識點概覽：
一、hashCode()
二、HashMap 底層實現
簡介
存儲結構
重要屬性
增加元素操作
Q: HashMap 的長度為什么默認初始長度是16，并且每次resize()的時候，長度必須是2的冪次方？
HashMap 擴容
Q: HashMap 死鏈問題
Java 8 與 Java 7對比
為什么要使用紅黑樹？
三、結語
一、hashCode()在Object 類中，hashCode()方法是一個被native修飾的類，JavaDoc中描述的是返回該對象的哈希值。
那么哈希值這個返回值是有什么作用呢？
主要是保證基于散列的集合，如HashSet、HashMap以及HashTable等，在插入元素時保證元素不可重復，同時為了提高元素的插入刪除便利效率而設計；主要是為了查找的便捷性而存在。
拿Set進行舉例，
眾所周知，Set集合是不能重復，如果每次添加數據都拿新元素去和集合內部元素進行逐一地equal()比較，那么插入十萬條數據的效率可以說是非常低的。
所以在添加數據的時候就出現了哈希表的應用，哈希算法也稱之為散列算法，當添加一個值的時候，先去計算出它的哈希值，根據算出的哈希值將數據插入指定位置。這樣的話就避免了一直去使用equal()比較的效率問題。
具體表現在：
如果指定位置為空，則直接添加
如果指定位置不為空，調用equal() 判斷兩個元素是否相同，如果相同則不存儲
上述第二種情況中，如果兩個元素不相同，但是hashCode()相同，那就是發生了我們所謂的哈希碰撞。
哈希碰撞的概率取決于hashCode()計算方式和空間容量的大小。
這種情況下，會在相同的位置，創建一個鏈表，把key值相同的元素存放到鏈表中。
在HashMap中就是使用拉鏈法來解決hashCode沖突。
總結hashCode是一個對象的標識，Java中對象的hashCode是一個int類型值。通過hashCode來指定數組的索引可以快速定位到要找的對象在數組中的位置，之后再遍歷鏈表找到對應值，理想情況下時間復雜度為O(1)，并且不同對象可以擁有相同的hashCode。
二、HashMap 底層實現 0. 簡介HashMap 基于哈希表的Map接口實現的，是以Key-Value存儲形式存在；
非線程安全；
key value都可以為null；
HashMap中的映射不是有序的；
在 JDK1.8 中，HashMap 是由 數組+鏈表+紅黑樹構成，新增了紅黑樹作為底層數據結構；
當一個哈希桶存儲的鏈表長度大于8 會將鏈表轉換成紅黑樹，小于6時則從紅黑樹轉換成鏈表；
1.8之前和1.8及以后的源碼，差別較大
1. 存儲結構在 JDK1.8 中，HashMap 是由 數組+鏈表+紅黑樹構成，新增了紅黑樹作為底層數據結構。
通過哈希來確認到數組的位置，如果發生哈希碰撞就以鏈表的形式存儲 ，但是這樣如果鏈表過長來的話，HashMap會把這個鏈表轉換成紅黑樹來存儲，閾值為8。
下面是HashMap的結構圖：
2. 重要屬性 2.1 table /**
* 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[] table;
在JDK1.8中我們了解到HashMap是由數組加鏈表加紅黑樹來組成的結構其中table就是HashMap中的數組。
2.2 size /**
* The number of key-value mappings contained in this map.
*/
transient int size;
HashMap中 鍵值對存儲數量。
2.3 loadFactor /**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
負載因子。負載因子是權衡資源利用率與分配空間的系數。當元素總量 > 數組長度 * 負載因子 時會進行擴容操作。
2.4 threshold /**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
擴容閾值。threshold = 數組長度 * 負載因子。超過后執行擴容操作。
2.5 TREEIFY_THRESHOLD/UNTREEIFY_THRESHOLD /**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
樹形化閾值。當一個哈希桶存儲的鏈表長度大于8 會將鏈表轉換成紅黑樹，小于6時則從紅黑樹轉換成鏈表。
3. 增加元素 public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
3.1 hash()
可以看到實際執行添加元素的是putVal()操作，在執行putVal()之前，先是對key執行了hash()方法，讓我們看下里面做了什么
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位異或
// >>>:無符號右移，忽略符號位，空位都以0補齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key==null說明，HashMap中是支持key為null的情況的。
同樣的方法在Hashstable中是直接用key來獲取hashCode，沒有key==null的判斷，所以Hashstable是不支持key為null的。
再回來說這個hash()方法。這個方法用專業術語來稱呼就叫做擾動函數。
使用hash()也就是擾動函數，是為了防止一些實現比較差的hashCode()方法。換句話來說，就是為了減少哈希碰撞。
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化，但是原理不變。我們再看下JDK1.7中是怎么做的。
// code in JDK1.7
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次。
3.2 putVal()再來看真正執行增加元素操作的putVal()方法，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 當數組為空或長度為0，初始化數組容量（resize() 方法是初始化或者擴容用的）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算數組下標 i = (n-1) & hash
// 如果這個位置沒有元素，則直接創建Node并存值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 這個位置已有元素
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// hash值、key值相等，用e變量獲取到當前位置這個元素的引用，后面用于替換已有的值
e = p;
else if (p instanceof TreeNode)
// 當前是以紅黑樹方式存儲，執行其特有的putVal方法 -- putTreeVal
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 當前是以鏈表方式存儲，開始遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 這里是插入到鏈表尾部！
p.next = newNode(hash, key, value, null);
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)
// onlyIfAbsent 如果為true - 不覆蓋已存在的值
// 把新值賦值進去
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 記錄修改次數
++modCount;
// 判斷元素數量是否超過閾值 超過則擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.3 HashMap 的長度為什么默認初始長度是16，并且每次resize()的時候，長度必須是2的冪次方？
這是一個常見的面試題。這個問題描述的設計，實際上為了服務于從Key映射到數組下標index的Hash算法。
前面提到了，我們為了讓HashMap存儲高效，應該盡量減少哈希碰撞，也就是說，應該讓元素分配得盡可能均勻。
Hash 值的范圍值-2147483648到2147483647，前后加起來大概40億的映射空間，只要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。但問題是一個40億長度的數組，內存是放不下的。所以這個散列值是不能直接拿來用的。
所以才需要一個映射的算法。這個計算方式就是3.2中有出現的(n - 1) & hash。
我們來進一步演示一下這個算法：
假設有一個key="book"
計算book的hashCode值，結果為十進制的3029737，二進制的101110001110101110 1001。
假定HashMap長度是默認的16，計算Length-1的結果為十進制的15，二進制的1111。
把以上兩個結果做與運算，101110001110101110 1001 & 1111 = 1001，十進制是9，所以 index=9。
通過這種與運算的方式，能夠和取模運算一樣的效果hashCode % length，在上述例子中就是3029737 % 16=9。
并且通過位運算的方式大大提高了性能。
可能到這里，你還是不知道為什么長度必須是2的冪次方，也是因為這種位運算的方法。
長度16或者其他2的冪，Length-1的值是所有二進制位全為1，這種情況下，index的結果等同于HashCode后幾位的值。只要輸入的HashCode本身分布均勻，Hash算法的結果就是均勻的。如果HashMap的長度不是2的冪次方，會出現某些index永遠不會出現的情況，這個顯然不符合均勻分布的原則和期望。所以在源碼里面一直都在強調power-of-two expansion和size must be power of two。
另外，HashMap 構造函數允許用戶傳入的容量不是 2 的 n 次方，因為它可以自動地將傳入的容量轉換為 2 的 n 次方。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
4. HashMap 擴容
接下來我們來講講HashMap擴容相關的知識。
4.1 擴容HashMap的初始長度是16，假設HashMap中的鍵值對一直在增加，但是table數組容量一直不變，那么就會發生哈希碰撞，查找的效率肯定會越來越低。所以當鍵值對數量超過某個閾值的時候，HashMap就會執行擴容操作。
那么擴容的閾值是怎么計算的呢？
閾值 = 數組長度 * 負載因子threshold = capacity * loadFactor
每次擴容后，threshold 加倍
上述計算就出現在resize()方法中。下面會詳細解析這個方法。我們先繼續往下講。
loadFactor這個參數，我們之前提到過，負載因子是權衡資源利用率與分配空間的系數。至于為什么是0.75呢？這個實際上就是一個作者認為比較好的權衡，當然你也可以通過構造方法手動設置負載因子 。public HashMap(int initialCapacity, float loadFactor) {...)。
接下去再來到這里的主角resize()方法
