Map原始碼剖析
HashMap&LinkedHashMap&Hashtable
hashMap默認的閾值是0.75
HashMap put操作
put操作涉及3種結構，普通node節點，鏈表節點，紅黑樹節點，針對第三種，紅黑樹節點，我們后續單獨去學習，這里不多做擴散
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) {
// 初始化哈希陣列，或者對哈希陣列擴容，回傳新的哈希陣列
tab = resize();
n = tab.length;
}
// 相當于取余
i = (n - 1) & hash;
p = tab[i];
if (p == null) {
// 直接放普通元素
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)))) {
// 存在同位元素，也就是出現了hash碰撞
e = p;
} else if (p instanceof TreeNode) {
// 如果當前位置已經是紅黑樹節點，那么就put紅黑色
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
// 遍歷哈希槽后面鏈接的其他元素（binCount統計的是插入新元素之前遍歷過的元素數量）
// 這里就是鏈表型別
for (int binCount = 0; ; ++binCount) {
// 后繼節點為空
if ((e = p.next) == null) {
// 拼接到后繼節點上
p.next = newNode(hash, key, value, null);
/**
* 哈希槽（鏈）上的元素數量增加到TREEIFY_THRESHOLD后，這些元素進入波動期，即將從鏈表轉換為紅黑樹
* 注意這個TREEIFY_THRESHOLD 是8，為什么是8？？
* 每次遍歷一個鏈表，平均查找的時間復雜度是 O(n)，n 是鏈表的長度，由于紅黑樹有自平衡的特點，可以防止不平衡情況的發生，
* 所以可以始終將查找的時間復雜度控制在 O(log(n))，
* 最初鏈表還不是很長，所以可能 O(n) 和 O(log(n)) 的區別不大，但是如果鏈表越來越長，那么這種區別便會有所體現，所以為了提升查找性能，需要把鏈表轉化為紅黑樹的形式，
* 鏈表查詢的時候使用二分查詢，平均查找長度為n/2，長度為8的時候，為4，而6/2 = 3
* 而如果是紅黑樹，那么就是log(n) ，長度為8時候，log(8) = 3, log(6) =
* 這個時候我們發現超過8這個閾值之后，鏈表的查詢效率會越來越不如紅黑樹
*/
if (binCount >= TREEIFY_THRESHOLD - 1) {
// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
// 判斷鏈表中的后繼原始是否hash碰撞，如果發生了hash碰撞break
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果存在同位元素（在HashMap中占據相同位置的元素）
if (e != null) { // existing mapping for key
V oldValue = https://www.cnblogs.com/cutter-point/archive/2022/12/02/e.value;
// 判斷是否需要進行覆寫取值,因為key相同，那么直接取代，否則什么也不操作
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
總結關鍵資訊：
哈希槽（鏈）上的元素數量增加到TREEIFY_THRESHOLD后，這些元素進入波動期，即將從鏈表轉換為紅黑樹
注意這個TREEIFY_THRESHOLD 是8，為什么是8？？
每次遍歷一個鏈表，平均查找的時間復雜度是 O(n)，n 是鏈表的長度，由于紅黑樹有自平衡的特點，可以防止不平衡情況的發生，
所以可以始終將查找的時間復雜度控制在 O(log(n))，
最初鏈表還不是很長，所以可能 O(n) 和 O(log(n)) 的區別不大，但是如果鏈表越來越長，那么這種區別便會有所體現，所以為了提升查找性能，需要把鏈表轉化為紅黑樹的形式，
鏈表查詢的時候使用二分查詢，平均查找長度為n/2，長度為8的時候，為4，而6/2 = 3
而如果是紅黑樹，那么就是log(n) ，長度為8時候，log(8) = 3, log(6) =
這個時候我們發現超過8這個閾值之后，鏈表的查詢效率會越來越不如紅黑樹
HashMap get，remove操作
除了紅黑樹的查找比較特殊，其余的鏈表查找就是暴力搜索，只是平均下來找到一個元素的話是n/2
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab = table;
Node<K,V> p;
int n, index;
if (tab != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
// 找到節點，并且是首節點
node = p;
} else if ((e = p.next) != null) {
if (p instanceof TreeNode) {
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
} else {
// 鏈表查詢，暴力搜索
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 移除節點，可能只需要匹配hash和key就行，也可能還要匹配value，這取決于matchValue引數
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) {
// 移除紅黑樹節點
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
} else if (node == p) {
// 移除首節點為后繼節點
tab[index] = node.next;
} else {
// 鏈表斷開
p.next = node.next;
}
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
HashMap擴容
鏈表拆分，進入新的容器
這里有個知識點：如何使用位運算進行取模
a % b == a & (b - 1)
我們拆分鏈表的思路也是這樣：比如原來長度為8的鏈表，也就是 x % 8 = x & (8 - 1) = x & 0111 也就是取后三位，那么擴容之后重新排序的話，容量擴大一倍，也就是16，那么這個時候就是 x % 16 = x & (16 - 1) = x & 1111 這個時候我們發現和之前的區別就是最高位由原來的0變為1，如果還在后三位范圍內，那么新容量中的位置是不會變的
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 舊閾值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 判斷舊容量是否已經超過最大值
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果已經達到1 << 30;，那么直接設定為Integer.MAX_VALUE; 0x7fffffff
threshold = Integer.MAX_VALUE;
return oldTab;
} else {
// mod by xiaof 嘗試將哈希表陣列容量加倍，注意這里是左移，也就是說*2
newCap = oldCap << 1;
// 如果容量成功加倍（沒有達到上限），則將閾值也加倍
if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
newThr = oldThr << 1;
}
}
// else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
// oldCap >= DEFAULT_INITIAL_CAPACITY) {
// newThr = oldThr << 1; // double threshold
// }
} else if (oldThr > 0) {
// initial capacity was placed in threshold
newCap = oldThr;
} else { // zero initial threshold signifies using defaults
// 如果實體化HashMap時沒有指定初始容量，則使用默認的容量與閾值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/*
* 至此，如果newThr==0，則可能有以下兩種情形：
* 1.哈希陣列已經初始化，且哈希陣列的容量還未超出最大容量，
* 但是，在執行了加倍操作后，哈希陣列的容量達到了上限
* 2.哈希陣列還未初始化，但在實體化HashMap時指定了初始容量
*/
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// 如果新容量小于最大允許容量，并且新容量*裝載因子之后還是小于最大容量，那么說明不需要擴容，那么直接使用ft作為新的閾值容量
// 如果新容量已經超過最大容量了，那么就直接回傳最大允許的容量
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新閾值
threshold = newThr;
// 新的容器物件，創建容量為新的newCap
@SuppressWarnings({"rawtypes","unchecked"})
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 = oldTab[j];
if (e != null) {
// 把原來的陣列中的指標設定為空
oldTab[j] = null;
if (e.next == null) {
// 重新計算hash索引位置，計算hash位置的方式防止陣列越界的話，那么就設定hashcode & 長度 - 1
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
// 紅黑樹，這里是對紅黑樹進行拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
} else { // preserve order
// lo對應的鏈表是資料不會動的
Node<K,V> loHead = null, loTail = null;
// hi對應的鏈表標識是需要去新容器新的位置的
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 這個是鏈表的情況下進行拆分
// 因為num % 2^n == num & (2^n - 1)，容量大小一定是2的N次方
do {
next = e.next;
// 注意：e.hash & oldCap，注意這里是對老的容量oldCap進行計算這一步就是前面說的判斷多出的這一位是否為1
// 因為新的是老的2倍，新節點位置是否需要發生改變，取決于最高位是否為0
// 若與原容量做與運算，結果為0，表示將這個節點放入到新陣列中，下標不變
// 由于原來的是2的倍數，那么取余肯定是和一個0111111的物件進行&操作，而不減一那就是10000000進行&操作，正好是最高位
if ((e.hash & oldCap) == 0) {
// 最高位為0，那么位置不需要改變，本身就在原來容量范圍內的資料
// 直接加入lotail,并判斷是否需要初始化lotail
if (loTail == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
} else {
// 最高位是1，那么就需要進行切換位置
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;
}
LinkedHashMap
基本和hashmap差不多，唯一需要注意下的是
還有一個核心點就是linkedHashMap覆寫了newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 這里創建了linkedhashmap物件
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 創建完成之后，就添加到鏈表中連接起來
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
插入覆寫afterNodeAccess
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
// 獲取節點 b -> p -> a
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 斷開尾部連接
p.after = null;
// 如果前置節點是空的，那么就吧A作為head節點
if (b == null) {
head = a;
} else {
// 如果前置節點不為空，那么就吧前置節點連接到后置節點，吧中間節點斷開
b.after = a;
}
// 后置節點不為空，那么就吧后置節點連接到前置節點上
if (a != null) {
a.before = b;
} else {
// 如果后置節點為空，那么重新設定tail指向before節點
last = b;
}
// 重新連接當前這個節點到末尾
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
afterNodeInsertion在linkedhashmap中作用不大
/**
*
* +----+ +----+ +----+
* | b | ---> | p | ---> | a |
* +----+ +----+ +----+
* @param e
*/
void afterNodeRemoval(Node<K,V> e) { // unlink
// 移除節點
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
tail = b;
} else {
a.before = b;
}
}
綜上：linkedhashmap相對hashmap其實就是多加了一個鏈表把所有的資料關聯起來，只有在遍歷的時候才能體現出來有序，其他的操作是沒有差別的
關于hashtable
首先hashtable是執行緒安全的，因為它所有的函式都加上了synchronized
鏈表頭插法，沒有紅黑樹的轉換
初始化容量的時候默認是11，是奇數，而hashmap全都是2的冪次方
hashtable允許key為null
rehash函式
常用的hash函式是選一個數m取模（余數），這個數在課本中推薦m是素數，但是經常見到選擇m=2n，因為對2n求余數更快，并認為在key分布均勻的情況下，key%m也是在[0,m-1]區間均勻分布的，但實際上，key%m的分布同m是有關的，
證明如下： key%m = key - xm，即key減掉m的某個倍數x，剩下比m小的部分就是key除以m的余數，顯然，x等于key/m的整數部分，以floor(key/m)表示，假設key和m有公約數g，即key=ag, m=bg, 則 key - xm = key - floor(key/m)m = key - floor(a/b)m，由于0 <= a/b <= a，所以floor(a/b)只有a+1中取值可能，從而推匯出key%m也只有a+1中取值可能，a+1個球放在m個盒子里面，顯然不可能做到均勻，
由此可知，一組均勻分布的key，其中同m公約數為1的那部分，余數后在[0,m-1]上還是均勻分布的，但同m公約數不為1的那部分，余數在[0, m-1]上就不是均勻分布的了，把m選為素數，正是為了讓所有key同m的公約數都為1，從而保證余數的均勻分布，降低沖突率，
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 這里重新計算容量的辦法是容量擴大一倍，然后+1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE) {
// Keep running with MAX_ARRAY_SIZE buckets
return;
}
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 重新把舊的原始轉移到新陣列上
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
// 這里因為容量是奇數，那么就需要使用%取余，而不是位運算 -》 a & (b - 1)
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
參考
https://www.cnblogs.com/tuyang1129/p/12368842.html -- 鏈表拆分
https://www.cnblogs.com/lyhc/p/10743550.html - linkedhashmap
http://zhaox.github.io/algorithm/2015/06/29/hash
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539014.html
標籤：其他
上一篇：深入淺出Seata的AT模式
下一篇：每日演算法之鏈表中環的入口結點