原文鏈接http://zhhll.icu/2020/12/10/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/HashMap%E8%AF%A6%E8%A7%A3/
HashMap詳解
介紹
HashMap是在專案中使用的最多的Map，實作了Map介面，繼承AbstractMap，基于哈希表的Map介面實作，不包含重復的鍵，一個鍵對應一個值，在HashMap存盤的時候會將key、value作為一個整體Entry進行存盤，
HashMap中會根據hash演算法來計算key所對應的存盤位置，
繼承關系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
資料結構
陣列+鏈表+紅黑樹
默認采用陣列+鏈表的方式存盤元素，當元素出現哈希沖突時，HashMap使用鏈地址法來解決hash沖突，會存盤在該位置的鏈表中，當鏈表中元素個數超過8個時，會嘗試將鏈表轉為紅黑樹存盤，但是在轉換前，會判斷一次當前陣列的長度，當陣列長度大于64時才會處理，否則進行擴容操作
原始碼決議
重要引數
初始大小和加載因子
-
初始大小用來規定哈希表陣列的長度
-
加載因子用來表示哈希表元素的填滿程度，加載因子越大哈希表的空間利用率越高，但是哈希沖突的幾率也會越大
靜態常量
/**
* 默認初始容量16，必須為2的次冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量 最大為1<<30 即2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認加載因子 0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* hash沖突鏈表節點個數大于8時，會轉化為紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* hash沖突時，當紅黑樹存盤中節點少于6時,則轉化為單鏈表存盤
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 鏈表轉為紅黑樹的最小表容量，如果沒有達到該容量，將進行擴容
* 該值設定至小為4*TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
為什么容量一定要是2次冪
在計算陣列下標時使用的是(n - 1) & hash來計算的，當n為2次冪時，n-1的低位將全是1，哈希值進行與操作時保證低位不變，最終得到的index結果，完全取決于key的hashCode的最后幾位，從而保證分布均勻，效果等同于取模，且性能比取模高，
Node
HashMap中的元素都存盤在Node陣列中，看一下Node的結構
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
// 該Node節點的hash值
final int hash;
final K key;
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 = https://www.cnblogs.com/life-time/p/value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key +"=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = https://www.cnblogs.com/life-time/p/value;
value = newValue;
return oldValue;
}
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;
}
}
如果是鏈表，則使用的是Node存盤(單向鏈表)；如果是紅黑樹，則使用的是TreeNode
建構式
無參建構式
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
指定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
指定初始容量和加載因子
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);
}
/**
* 回傳大于等于cap最小的2的冪
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
// 右移一位，在進行按位或 保證了除最高位之外全是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;
}
傳入map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
方法分析
put方法添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 將key的hash值進行高16位和低16位異或操作，增加低16位的隨機性，減少哈希沖突
*/
static final int hash(Object key) {
int h;
// 右移16位是為了使得hash值得高位參與運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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為null，resize()進行陣列初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 使用(n-1)&hash找到下標位置，如果當前沒有元素，則創建Node物件，放到陣列該位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 陣列該位置已有值，hash沖突
Node<K,V> e; K k;
// 哈希值與key值都相同，則進行value值替代
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // hash值相等，但是key不相等，且為紅黑樹
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // hash值相等，但是key不等，且為鏈表
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 是否超過閾值，超過則進行鏈表轉紅黑樹 表示添加之后的長度和TREEIFY_THRESHOLD進行比較
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 = https://www.cnblogs.com/life-time/p/e.value; // 進行
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 元素個數大于新增閾值，進行resize()擴容
resize();
afterNodeInsertion(evict);
return null;
}
擴容
當hashMap中的容量達到閾值時，就會開始擴容操作
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) { // 當前長度超過了最大容量，新增閾值為Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 容量擴容為2倍且當新容量小于最大容量，原來的容量大于默認初始容量時，閾值擴容為2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 此時oldCap<=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;
@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;
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 = e.next;
if ((e.hash & oldCap) == 0) { // 哈希值和原陣列容量進行&操作，為0，則放入原陣列的索引位置
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 非0則放入原陣列索引位置+原陣列長度的新位置
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;
}
紅黑樹轉換
將單向鏈表轉為雙向鏈表，在遍歷雙向鏈表轉為紅黑樹
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 判斷是否容量到達紅黑樹轉換的最小容量
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null; // hd指向首節點，tl指向尾結點
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // 將鏈表轉為紅黑樹
if (tl == null) // 如果尾結點為null，說明還沒有首節點
hd = p; // 當前節點為首節點
else { // 尾結點不為null，構造一個雙向鏈表，將當前節點追加到雙向鏈表的末尾
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 將原本的單鏈表轉化為一個節點型別為TreeNode的雙向鏈表
if ((tab[index] = hd) != null) // 把轉換后的雙向鏈表，替換陣列原來位置上的單向鏈表
hd.treeify(tab); // 將當前雙向鏈表樹形化
}
}
雙向鏈表轉為紅黑樹
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null; //定義紅黑樹根節點
for (TreeNode<K,V> x = this, next; x != null; x = next) { // 從TreeNode雙向鏈表的頭節點開始遍歷
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 不存在根節點
x.parent = null;
x.red = false; // 紅黑樹根節點為黑色
root = x; // 當前元素設為根節點
}
else { // 存在根節點
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) { //遍歷紅黑樹
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) // 當前紅黑樹節點p的hash值大于雙向鏈表節點x的哈希值
dir = -1;
else if (ph < h) // 當前紅黑樹節點p的hash值小于雙向鏈表節點x的哈希值
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) // 兩者相等，使用比較器比較
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { // 當前紅黑樹p為葉子節點
x.parent = xp;
if (dir <= 0) // 根據dir的值，確認是p的左節點還是右節點
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x); // 進行平衡調整
break;
}
}
}
}
// 將TreeNode雙向鏈表轉換為紅黑樹之后，將根節點作為陣列的當前位置
moveRootToFront(tab, root);
}
將紅黑樹的根節點移動到陣列的索引所在位置
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 陣列當前索引的元素
if (root != first) { // 根節點不是當前元素
Node<K,V> rn;
tab[index] = root; // 將根節點設定為當前索引的元素
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
紅黑樹插入
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
紅黑樹拆分
在進行擴容操作時，會重新計算索引位置，拆分之后的紅黑樹需要判斷個數，從而決定做去樹化還是樹化
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null; // 保存在原索引的紅黑樹
TreeNode<K,V> hiHead = null, hiTail = null; // 保存在新索引的紅黑樹
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) { // 與鏈表操作基本一致
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) { // 原索引位置
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) { // 新索引位置
if (hc <= UNTREEIFY_THRESHOLD) // 紅黑樹節點小于去樹化閾值，進行去樹化操作
tab[index + bit] = hiHead.untreeify(map);
else { // 大于去樹化閾值，進行樹化操作
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
去樹化操作
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
put操作的大致步驟如下：
- 對key進行hash操作，找到索引位置，如果此時索引位置為null，直接插入
- 如果此時索引位置不為null，說明出現了hash沖突，使用equals()比較key的值，如果存在與該key相同的值，則替換value
- 如果不存在與該key相同的值，且此時存盤結構為鏈表，則插入鏈表尾部，如果鏈表長度超過8個且陣列長度大于64時，進行鏈表轉紅黑樹
- 當陣列中資料達到閾值，則需要進行擴容，擴容時需要進行去樹化
get方法獲取元素
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// hash為key的hash值
// key為所要查找的key物件
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 陣列不為null且該索引位置的頭節點不為null
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 {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);// 進行遍歷匹配
}
}
return null;
}
高并發問題
由于HashMap不是執行緒安全的，在高并發的情況下會出現問題，在插入時可能會出現問題
假如HashMap到達了擴容的臨界點，此時有兩個執行緒在同一時刻對HashMap進行put操作，兩個執行緒都會進行擴容可能會形成鏈表環，使得下一次讀操作出現死回圈，
由于本身的博客百度沒有收錄，博客地址http://zhhll.icu
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/253816.html
標籤：Java
下一篇：Soul的限流斷路器的使用和流程