簡單談談HashMap
- 2020 年 3 月 9 日
- 筆記
概述
面試Java基礎，HashMap可以說是一個繞不過去的基礎容器，哪怕其他容器都不問，HashMap也是不能不問的。
除了HashMap，還有HashTable跟ConcurrentHashMap，兩個都是線程安全的哈希容器，但是HashTable是JDK1.0就有的容器，線程安全是通過synchronized關鍵字來實現的，而且鎖住的是整個table對象，雖然線程安全，但是並發性能並不高。因此在JDK1.5裏面並發大師Doug Lea操刀寫了個ConcurrentHashMap，通過粒度更細的鎖來實現更高的性能。
HashMap的歷史
在不同版本的JDK中，HashMap是在不停優化的。
- 比如JDK1.6裏面new HashMap時，開闢了內存空間，如果不使用，則浪費內存；JDK1.7裏面改成了懶加載，new HashMap並沒有開闢內存空間，節約了內存空間
- 1.8優化了hashCode算法：高16位異或（XOR）低16位 主要是為了增加擾動，減少碰撞幾率
- 1.8裏面優化了hash碰撞較多情況下的性能問題（鏈表長度限制為8，過長時請將鏈錶轉換為TreeNode(紅黑樹)）
配置常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final int MAXIMUM_CAPACITY = 1 << 30; 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容器初始化的容量為16，默認負載因子為0.75，樹化閾值為8，反樹化閾值為6。
put流程
- 對key的hashCode()做hash運算，計算index；
- 如果沒碰撞直接放到bucket里；
- 如果碰撞了，以鏈表的形式存在buckets後；
- 如果碰撞導致鏈表過長(大於等於TREEIFY_THRESHOLD)，就把鏈錶轉換成紅黑樹(JDK1.8中的改動)；
- 如果節點已經存在就替換old value(保證key的唯一性)
- 如果bucket滿了(超過load factor*current capacity)，就要resize。
get流程
- 對key的hashCode()做hash運算，計算index;
- 如果在bucket里的第一個節點裏直接命中，則直接返回；
- 如果有衝突，則通過key.equals(k)去查找對應的Entry；
- 若為樹，則在樹中通過key.equals(k)查找，O(logn)；
- 若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。
Hash算法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }HashMap中可以存放key為null的值，放在首位。
將高16位與低16位異或運算，通過這樣一個擾動函數，減小了hash衝突的概率。然後再通過這個hash值與數組的長度進行取模運算，決定這個鍵值對該放入哪個bin中。
(n – 1) & hash
這個算法是當bin為bull的時候，直接將Node放入table中；當擴容的時候，存在兩種情況，要麼放在原來的位置，要麼往後移動原來的容量大小的位置，這時候使用的是下面這個算法：
e.hash & oldCap
如果得到的結果為零，則在原位置；反之，則將其向高位移動oldCap大小的位置。
拓展
String的Hash算法如下：
public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }String類中的hashCode計算方法還是比較簡單的，就是以31為權，每一位為字符的ASCII值進行運算，用自然溢出來等效取模。
哈希計算公式可以計為s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
那為什麼以31為質數呢?
主要是因為31是一個奇質數，所以31*i=32*i-i=(i<<5)-i，這種位移與減法結合的計算相比一般的運算快很多。
