散列表
定義：
通過散列函數(shù)把元素的鍵值映射為下標(biāo)，然后將數(shù)據(jù)存儲(chǔ)在數(shù)組中對(duì)應(yīng)下標(biāo)的位置。當(dāng)我們按照鍵值查詢?cè)貢r(shí)，我們用同樣的散列函數(shù)，將鍵值轉(zhuǎn)化數(shù)組下標(biāo)，從對(duì)應(yīng)的數(shù)組下標(biāo)的位置取數(shù)據(jù)。
裝載因子：
散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度。
裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能會(huì)下降。
散列沖突解決方案
開放尋址法
線性探測(cè)
插入過程：
如果某個(gè)數(shù)據(jù)經(jīng)過散列函數(shù)散列之后，存儲(chǔ)位置已經(jīng)被占用了，我們就從當(dāng)前位置開始，依次往后查找，看是否有空閑位置，直到找到為止。
查找過程：
我們通過散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素。如果相等，則說明就是我們要找的元素；否則就順序往后依次查找。如果遍歷到數(shù)組中的空閑位置，還沒有找到，就說明要查找的元素并沒有在散列表中。
刪除過程：
將刪除的元素，特殊標(biāo)記為deleted。當(dāng)線性探測(cè)查找的時(shí)候，遇到標(biāo)記為deleted的空間，并不是停下來，而是繼續(xù)往下探測(cè)。
適用條件：
當(dāng)數(shù)據(jù)量比較小、裝載因子小的時(shí)候，適合采用開放尋址法。
ThreadLocalMap使用開放尋址法解決散列沖突。鏈表法
在散列表中，每個(gè)桶會(huì)對(duì)應(yīng)一條鏈表，所有散列值相同的元素都會(huì)放到相同槽位對(duì)應(yīng)的鏈表中。
內(nèi)存的利用率比開放尋址法要高，對(duì)大裝載因子的容忍度更高。
比較適合存儲(chǔ)大對(duì)象、大數(shù)據(jù)量的散列表，而且，比起開放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如用紅黑樹代替鏈表。
如何設(shè)計(jì)散列表
散列函數(shù)
散列函數(shù)的設(shè)計(jì)不能太復(fù)雜。會(huì)消耗很多計(jì)算時(shí)間，也就間接地影響到散列表的性能。
散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布，這樣才能避免或者最小化散列沖突，而且即便出現(xiàn)沖突，散列到每個(gè)槽里的數(shù)據(jù)也會(huì)比較平均，不會(huì)出現(xiàn)某個(gè)槽內(nèi)數(shù)據(jù)特別多的情況。解決負(fù)載因子過大問題
擴(kuò)容，數(shù)組長(zhǎng)度擴(kuò)大為之前2倍，負(fù)載因子原先是0.8也會(huì)減到0.4。
散列表的大小變了，數(shù)據(jù)的存儲(chǔ)位置也變了，所以需要通過散列函數(shù)重新計(jì)算每個(gè)數(shù)據(jù)的存儲(chǔ)位置。如何解決低效擴(kuò)容
為了解決一次性擴(kuò)容耗時(shí)過多的情況，我們可以將擴(kuò)容操作穿插在插入操作的過程中，分批完成。當(dāng)裝載因子觸達(dá)閾值之后，我們只申請(qǐng)新空間，但并不將老的數(shù)據(jù)搬移到新散列表中。
當(dāng)有新數(shù)據(jù)要插入時(shí)，我們將新數(shù)據(jù)插入新散列表中，并且從老的散列表中拿出一個(gè)數(shù)據(jù)放入到新散列表。這樣沒有了集中的一次性數(shù)據(jù)搬移，插入操作就都變得很快了。
查詢先從新散列表中查找，再從舊散列表中查找。
HashMap
HashMap是一個(gè)利用哈希表原理來存儲(chǔ)元素的集合。遇到?jīng)_突時(shí)，HashMap是采用的鏈表法來解決。
在JDK1.7中，HashMap是由數(shù)組+鏈表構(gòu)成的。在JDK1.8中，HashMap是由數(shù)組+鏈表+紅黑樹構(gòu)成。
HashMap初始化容量16，負(fù)載因子0.75。
鏈表長(zhǎng)度大于8會(huì)轉(zhuǎn)成紅黑樹，小于6，紅黑樹又會(huì)轉(zhuǎn)成鏈表。
當(dāng)極端情況，所有數(shù)據(jù)都裝進(jìn)一個(gè)桶內(nèi)，使用查詢時(shí)間是O（n），使用紅黑樹查詢時(shí)間是O（logn），在數(shù)據(jù)量較大且哈希碰撞較多時(shí)，能夠極大的增加檢索的效率。在數(shù)據(jù)量較小的情況下，紅黑樹要維護(hù)平衡，比起鏈表來，性能上的優(yōu)勢(shì)并不明顯，空間成本比較高。
允許key和value都為null。key重復(fù)會(huì)被覆蓋，value允許重復(fù)。
無序。
字段屬性
private static final long serialVersionUID = 362498820763181265L;
// 集合初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 集合的最大容量
static final int MAXIMUM_CAPACITY = 1073741824;
// 默認(rèn)的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75F;
// 當(dāng)桶上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 當(dāng)桶上的節(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)會(huì)轉(zhuǎn)成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 當(dāng)集合中的容量大于這個(gè)值時(shí)，表中的桶才能進(jìn)行樹形化，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容，而不是樹形化
// 為了避免進(jìn)行擴(kuò)容、樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
transient HashMap.Node<K, V>[] table;
transient Set<Entry<K, V>> entrySet;
// 記錄集合被修改的次數(shù)
transient int modCount;
// 當(dāng)前已占用數(shù)組長(zhǎng)度
int threshold;
// 散列表的加載因子
final float loadFactor;
Hash算法
這種做法可以使數(shù)組元素分布均勻，減少散列沖突。
static final int hash(Object key) {
int h;
// 算出來的hash值比較分散,減少了碰撞的可能性
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key在數(shù)組中的位置公式：i = (table.length - 1) & hash;
hash值算出來，要計(jì)算當(dāng)前key在數(shù)組中的索引下標(biāo)位置時(shí)，可以采用取模的方式，就是索引下標(biāo)位置 = hash 值 % 數(shù)組大小，這樣做的好處，就是可以保證計(jì)算出來的索引下標(biāo)值可以均勻的分布在數(shù)組的各個(gè)索引位置上。但取模操作對(duì)于處理器的計(jì)算是比較慢的，數(shù)學(xué)上有個(gè)公式，當(dāng)b是2的冪次方時(shí)，a % b = a &（b-1），所以此處索引位置的計(jì)算公式我們可以更換為： (n-1) & hash。
如何解決hash沖突
hash沖突指的是key值的hashcode計(jì)算相同，但key值不同的情況。
- 好的hash算法
- 到達(dá)閾值自動(dòng)擴(kuò)容
- hash沖突發(fā)生時(shí)，采用鏈表來解決
- hash沖突嚴(yán)重時(shí)，鏈表自動(dòng)轉(zhuǎn)化成紅黑樹，提高遍歷速度
添加元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//數(shù)組為空，擴(kuò)容數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果當(dāng)前索引位置是空的，直接生成新的節(jié)點(diǎn)在當(dāng)前索引位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果key的hash和值都相等，直接把當(dāng)前下標(biāo)位置的Node值賦值給臨時(shí)變量
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 是個(gè)鏈表，把新節(jié)點(diǎn)放到鏈表的尾端
else {
for (int binCount = 0; ; ++binCount) {
// 到了尾節(jié)點(diǎn)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 當(dāng)鏈表的長(zhǎng)度大于等于 8 時(shí)，鏈表轉(zhuǎn)紅黑樹
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;
}
}
// 說明新節(jié)點(diǎn)的新增位置已經(jīng)找到了
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 記錄HashMap的數(shù)據(jù)結(jié)構(gòu)發(fā)生了變化
++modCount;
//如果HashMap的實(shí)際大小大于擴(kuò)容的門檻，開始擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 判斷鍵值對(duì)數(shù)組長(zhǎng)度是否是0，為0進(jìn)行擴(kuò)容。
- 根據(jù)鍵值key計(jì)算hash得到插入數(shù)據(jù)索引i，如果當(dāng)前索引位置是空的，直接生成新的節(jié)點(diǎn)在當(dāng)前索引位置上，轉(zhuǎn)向6。如果不為空，轉(zhuǎn)向3。
- hash沖突，兩種解決方案：鏈表 or 紅黑樹。
- 如果是鏈表，調(diào)用鏈表的新增方法。
- 如果是紅黑樹，調(diào)用紅黑樹的新增方法。
- 通過onlyIfAbsent變量判斷是否覆蓋對(duì)應(yīng)key的值。
- 判斷是否需要擴(kuò)容。
鏈表新增節(jié)點(diǎn)
循環(huán)鏈表，將新元素追加隊(duì)尾。
當(dāng)鏈表長(zhǎng)度大于等于8，并且整個(gè)數(shù)組大小大于等于64時(shí)，才會(huì)轉(zhuǎn)成紅黑樹。注意當(dāng)數(shù)組大小小于64時(shí)，只會(huì)觸發(fā)擴(kuò)容，不會(huì)轉(zhuǎn)化成紅黑樹。
紅黑樹新增節(jié)點(diǎn)
- 通過equals判斷新增的節(jié)點(diǎn)在紅黑樹上是不是已經(jīng)存在；
- 新增的節(jié)點(diǎn)如果已經(jīng)在紅黑樹上，直接返回；不在的話，判斷新增節(jié)點(diǎn)是在當(dāng)前節(jié)點(diǎn)的左邊還是右邊，左邊值小，右邊值大；
- 自旋當(dāng)前節(jié)點(diǎn)，直到當(dāng)前節(jié)點(diǎn)的左邊或者右邊的節(jié)點(diǎn)為空時(shí)，停止自旋，當(dāng)前節(jié)點(diǎn)即為我們新增節(jié)點(diǎn)的父節(jié)點(diǎn)；
- 把新增節(jié)點(diǎn)放到當(dāng)前節(jié)點(diǎn)的左邊或右邊為空的地方，并于當(dāng)前節(jié)點(diǎn)建立父子節(jié)點(diǎn)關(guān)系；
- 進(jìn)行著色，旋轉(zhuǎn)。
擴(kuò)容
擴(kuò)容時(shí)機(jī)：
- 添加元素時(shí)發(fā)現(xiàn)數(shù)組為空，進(jìn)行初始化擴(kuò)容，默認(rèn)擴(kuò)容大小為 16;
- 添加元素成功，發(fā)現(xiàn)現(xiàn)有數(shù)組大小大于擴(kuò)容的門閥值時(shí)，進(jìn)行擴(kuò)容，擴(kuò)容為老數(shù)組大小的2倍;
每次擴(kuò)容時(shí)門閥值都會(huì)被重新計(jì)算，門閥值等于數(shù)組的大小 * 影響因子（0.75）。
1.7源碼：
新建一個(gè)擴(kuò)容數(shù)組，將數(shù)組元素轉(zhuǎn)移到新數(shù)組里面，修改閾值。
轉(zhuǎn)移數(shù)組元素：
遍歷同桶數(shù)組中的每一個(gè)桶，遍歷桶的外接鏈表。找到新表的桶位置。
舊桶數(shù)組中的某個(gè)桶的外掛單鏈表是通過頭插法插入新桶數(shù)組中的，并且原鏈表中的Entry結(jié)點(diǎn)并不一定仍然在新桶數(shù)組的同一鏈表。
1.8源碼：
為了性能在同一索引處發(fā)生哈希沖突到一定程度時(shí)鏈表結(jié)構(gòu)會(huì)轉(zhuǎn)換為紅黑數(shù)結(jié)構(gòu)存儲(chǔ)沖突元素，故在擴(kuò)容時(shí)如果當(dāng)前索引中元素結(jié)構(gòu)是紅黑樹且元素個(gè)數(shù)小于鏈表還原閾值時(shí)就會(huì)把樹形結(jié)構(gòu)縮小或直接還原為鏈表結(jié)構(gòu)。
查找元素
通過key計(jì)算索引，找到桶位置，先檢查第一個(gè)節(jié)點(diǎn)，如果是則返回，如果不是，則遍歷其后面的鏈表或者紅黑樹，找到返回，沒有找到返回null。
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 如果當(dāng)前節(jié)點(diǎn)hash等于key的hash，并且equals相等，當(dāng)前節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
刪除元素
刪除元素首先是要找到桶的位置，然后如果是鏈表，則進(jìn)行鏈表遍歷，找到需要?jiǎng)h除的元素后，進(jìn)行刪除；如果是紅黑樹，也是進(jìn)行樹的遍歷，找到元素刪除后，進(jìn)行平衡調(diào)節(jié)，當(dāng)紅黑樹的節(jié)點(diǎn)數(shù)小于6時(shí)，會(huì)轉(zhuǎn)化成鏈表。
參考
JDK1.8源碼(七)——java.util.HashMap 類
《極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法之美專欄》
