Java HashMap透析
- (*-*)浩轉載
- 2019-10-28 15:35:452496瀏覽
HashMap 是數組和鍊錶組合組成的複雜結構，哈希值決定了鍵值在數組的位置，當哈希值相同時則以鍊錶形式存儲，當鍊錶長度到達設定的閾值則會對其進行樹化，這樣做是為了確保資料安全和資料相關操作的效率
HashMap 效能表現取決於雜湊碼的有效性，所以hashCode 和equals 的基本約定規則特別重要，如：equals 相等，hashCode 一定要相等；重寫了hashCode 也要重寫equals；hashCode 需要保持一致性，狀態改變回傳的雜湊值仍然要一致；equals 的對稱、反射、傳遞等特性
HashMap 與Hashtable、TreeMap 的差異
HashMap：基於陣列的非同步雜湊表，支援null 鍵或值，是鍵值對存取資料場景的首選
Hashtable：基於數組的同步雜湊表，不支援null鍵或值，因為同步導致效能影響，很少被使用
TreeMap：基於紅黑樹提供順序存取的Map，比HashMap 節省空間，但它的資料操作（查、增、刪）時間複雜度均為：O（log(n)），這點與HashMap 不同。支援空值，當鍵為空時且未實現Comparator 接口，會出現NullPointerException ，實現了Comparator 接口並對null 對象進行判斷可實現正常存入
HashMap、Hashtable、TreeMap 均以鍵值對形式儲存或操作資料元素。 HashMap、TreeMap 繼承自AbstractMap 類，Hashtable 繼承自Dictionary 類，三者皆實作Map 介面
HashMap 原始碼解析
#HashMap()
public HashMap(int initialCapacity, float loadFactor){
// ...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}初始化HashMap 時只設定了一些初始值，但在開始處理資料時，如 .put() 方法內漸漸開始複雜起來
HashMap.put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义新tab数组及node对象
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果原table是空的或者未存储任何元素则需要先初始化进行tab的初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 当数组中对应位置为null时，将新元素放入数组中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 若对应位置不为空时处理哈希冲突
else {
Node<K,V> e; K k;
// 1 - 普通元素判断： 更新数组中对应位置数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2 - 红黑树判断：当p为树的节点时，向树内插入节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3 - 链表判断：插入节点
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;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回调以允许LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更新修改次数
++modCount;
// 检查数组是否需要进行扩容
if (++size > threshold)
resize();
// 回调以允许LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
}當table 為null，會透過 resize() 初始化，且 resize() 有兩個作用，一是創建並初始化table ，二是在table 容量不滿足需求時進行擴容：
if (++size > threshold)
resize();具體的鍵值對儲存位置計算方法為：
if ((p = tab[i = (n - 1) & hash]) == null)
// 向数组赋值新元素
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果新插入的结点和table中p结点的hash值，key值相同的话
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);
else {
for (int binCount = 0; ; ++binCount) {
// 代表这个单链表只有一个头部结点，则直接新建一个结点即可
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度大于8时，将链表转红黑树
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
p = e;
}
}
// 如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 回调以允许LinkedHashMap后置操作
return oldValue;
}
}留意.put() 方法中的hash 計算，它並不是key 的hashCode ，而是將key 的hashCode 高位資料移位到低位進行異或運算，這樣一些計算出來的哈希值主要差異在高位時的數據，就不會因HashMap 裡哈希尋址時被忽略容量以上的高位，那麼即可有效避免此類情況下的哈希碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap.resize()
final Node<K,V>[] resize() {
// 把当前底层数组赋值给oldTab，为数据迁移工作做准备
Node<K,V>[] oldTab = table;
// 获取当前数组的大小，等于或小于0表示需要初始化数组，大于0表示需要扩容数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取扩容的阈值（容量*负载系数）
int oldThr = threshold;
// 定义并初始化新数组长度和目标阈值
int newCap, newThr = 0;
// 判断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。若 if(oldCap > 0)=true 表示需扩容而非初始化
if (oldCap > 0) {
// 判断数组长度是否已经是最大，MAXIMUM_CAPACITY =（2^30）
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值设置为最大
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)
// 说明调用的是HashMap的有参构造函数，因为无参构造函数并没有对threshold进行初始化
newCap = oldThr;
// 表示需要初始化数组而不是扩容，零初始阈值表示使用默认值
else {
// 说明调用的是HashMap的无参构造函数
newCap = DEFAULT_INITIAL_CAPACITY;
// 计算目标阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 当目标阈值为0时需重新计算，公式：容量（newCap）*负载系数（loadFactor）
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;
// 将数组内此下标中的数据赋值给Node类型的变量e，并判断非空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1 - 普通元素判断：判断数组内此下标中是否只存储了一个元素，是的话表示这是一个普通元素，并开始转移
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 2 - 红黑树判断：判断此下标内是否是一颗红黑树，是的话进行数据迁移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3 - 链表判断：若此下标内包含的数据既不是普通元素又不是红黑树，则它只能是一个链表，进行数据转移
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
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;
}容量和負載係數決定了陣列容量，空餘太多會造成空間浪費，使用太滿會影響操作效能
如果能夠明確知道HashMap 將要存取的鍵值對的數量，可以考慮預先設定適當的容量大小。具體數值我們可以根據擴容發生的條件來做簡單預估，根據前面的程式碼分析，我們知道它需要符合計算條件：負載因子* 容量> 元素數量
所以，預先設定的容量需要滿足，大於預估元素數量/ 負載因子，同時它是2 的冪數
但需要注意的是：
如果沒有特別需求，不要輕易進行更改，因為JDK 自身的預設負載因子是非常符合通用場景的需求的。如果確實需要調整，建議不要設定超過 0.75 的數值，因為會顯著增加衝突，降低 HashMap 的效能。如果使用太小的負載因子，按照上面的公式，預設容量值也進行調整，否則可能會導致更頻繁的擴容，增加無謂的開銷，本身存取效能也會受影響。
HashMap.get()
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;
// 将table赋值给变量tab并判断非空 && tab 的厂部大于0 && 通过位运算得到求模结果确定链表的首节点赋值并判断非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断首节点hash值 && 判断key的hash值（地址相同 || equals相等）均为true则表示first即为目标节点直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 若首节点非目标节点，且还有后续节点时，则继续向后寻找
if ((e = first.next) != null) {
// 1 - 树：判断此节点是否为树的节点，是的话遍历树结构查找节点，查找结果可能为null
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 2 - 链表：若此节点非树节点，说明它是链表，遍历链表查找节点，查找结果可能为null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}HashMap 為什麼會被樹化
為了確保資料安全及相關操作效率
#因為在元素放置過程中，如果一個物件雜湊衝突，都被放置到同一個桶裡，則會形成一個鍊錶，我們知道鍊錶查詢是線性的，會嚴重影響存取的效能
而在現實世界，建構雜湊衝突的資料並不是非常複雜的事情，惡意程式碼就可以利用這些資料大量與伺服器端交互，導致伺服器端CPU 大量佔用，這就構成了雜湊碰撞拒絕服務攻擊，國內一線網路公司曾發生類似攻擊事件
以上是Java HashMap透析的詳細內容。更多資訊請關注PHP中文網其他相關文章！