阿里妹導讀
本文透過一個程式設計師小明遇到的實際問題,深入探討了在使用 HashMap 時由於鍵物件的可變性導致的資料訪問異常。
如果你只想看結論,給你上個一句話省流版:
一、前言
一天程式設計師小明跑到師兄面前說 :“師兄,我看到一個很詭異的現象,百思不得其解”。
師兄說:“莫慌,你且慢慢說來”
程式設計師小明說道:“我放到 Map 中的資料還在,但是怎麼也取不出來了…”
師兄,於是幫小明看了他的程式碼,發現了很多不為人知的秘密….
二、場景復現
小明 定義了一個 Player 作為 Map 的 key :
publicclassPlayer {
private String name;
publicPlayer(String name){
this.name = name;
}
// 省略了getter和setter方法
@Override
public boolean equals(Object o){
if (this == o) {
returntrue;
}
if (!(o instanceof Player)) {
returnfalse;
}
Player player = (Player) o;
return name.equals(player.name);
}
@Override
publicinthashCode(){
return name.hashCode();
}
}
Player 類在 name 屬性上有一個 setter ,所以它是可變的。此外,hashCode() 方法使用 name 屬性來計算雜湊碼。這意味著更改 Player 物件的名字可以使它具有不同的雜湊碼。
此時,有懂行的小夥伴已經看出了一點端倪
小明寫了如下程式碼,一切看起來還挺正常:
Map<Player, Integer> myMap = new HashMap<>();
Player kai = new Player("Kai");
Player tom = new Player("Tom");
Player amanda = new Player("Amanda");
myMap.put(kai, 42);
myMap.put(amanda, 88);
myMap.put(tom, 200);
assertTrue(myMap.containsKey(kai));
接下來,讓小明將玩家 kai 的名字從 “Kai” 更改為 “Eric”,然後懵逼了….
// 將Kai的名字更改為Eric
kai.setName("Eric");
assertEquals("Eric", kai.getName());
Player eric = new Player("Eric");
assertEquals(eric, kai);
// 現在,map中既不包含Kai也不包含Eric:
assertFalse(myMap.containsKey(kai));
assertFalse(myMap.containsKey(eric));
assertNull(myMap.get(kai));
assertNull(myMap.get(eric));
如上面的測試所示,更改 kai 的名字為 “Eric” 後,無法再使用 kai 或 eric 來檢索 “Eric” -> 42 的 Entry。
但,物件 Player(“Eric”) 還存在於 map 中作為一個鍵:
// 然而 Player("Eric") 以依然存在:
long ericCount = myMap.keySet()
.stream()
.filter(player -> player.getName()
.equals("Eric"))
.count();
assertEquals(1, ericCount);
小明,百思不得其解?
給你 2 分鐘的時間,是否可以清楚地解釋其中的緣由?如果不能,說明你對 HashMap 的瞭解還不夠。
[此處留白,大家思考一下]
三、原始碼淺析
這部分內容可能略顯枯燥,如果不喜歡可以跳過,看第四部分。
3.1 put 方法
3.1.1 put 方法概述
java.util.HashMap#put
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value){
return putVal(hash(key), key, value, false, true);
}
3.1.2 hash 方法
java.util.HashMap#hash
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
staticfinalinthash(Object key){
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該方法的主要目的是減少雜湊碰撞和更好地分配雜湊桶。高 16 位和低 16 位進行 XOR 操作,可以使得原本高 16位產生的影響,也能夠反映到低 16 位中來。這是一種簡單、快速但效果顯著的方法來減少雜湊碰撞。
該方法配合雜湊表的“冪次掩碼”(power-of-two masking)能夠更好的分散雜湊值,避免大量的雜湊值衝突在一起,從而提高雜湊表的效能。
3.1.3 putVal 方法
java.util.HashMap#putVal
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定義了一個用於表示雜湊表的陣列 tab,一個節點 p 用於指向特定的雜湊桶,
// 以及兩個整型變數 n 和 i 用於儲存雜湊表的大小和計算的索引位置。
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果雜湊表未初始化或其長度為0,它將呼叫 resize() 方法來初始化或擴容雜湊表。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//計算鍵的雜湊值應該對映到的索引,並檢查該位置是否為空。
//如果為空,則建立一個新節點並將其置於該位置。
if ((p = tab[i = (n - 1) & hash]) == 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))))
e = p;
//如果首個節點是一個紅黑樹節點,則呼叫 putTreeVal 方法來處理。
elseif (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);
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;
}
}
//如果找到了一個存在的節點,則根據 onlyIfAbsent 引數來決定是否要更新值,然後返回舊值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//增加 modCount 來表示 HashMap 被修改了,並檢查當前大小是否超過了閾值來決定是否要調整大小
++modCount;
if (++size > threshold)
resize();
//最後呼叫 afterNodeInsertion 方法(它在 HashMap 中是一個空方法,但在其子類 LinkedHashMap 中是有定義的),
//然後返回 null 來表示沒有舊值。
afterNodeInsertion(evict);
return null;
}
putVal 方法是一個非常核心和複雜的方法,它處理了很多細節,包括初始化雜湊表,確定正確的桶,處理連結串列和紅黑樹結構,以及正確的插入或更新節點的值。
一句話:找到合適的位置,放到該位置上。
3.2 containsKey 方法
3.2.1 containsKey 概覽
既然是 containsKey 不符合預期,我們就看下它的邏輯:
java.util.HashMap#containsKey
/**
* Returns <tt>true</tt> if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return <tt>true</tt> if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key){
return getNode(hash(key), key) != null;
}
3.2.2 hash 方法
同上
3.2.3 getNode 方法
java.util.HashMap#getNode
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
//首先定義了一些變數,包括雜湊表陣列 tab、要查詢的首個節點 first、
//一個輔助節點 e、陣列的長度 n 和一個泛型型別的 k 用於暫存 key。
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//這裡首先檢查雜湊表是否為空或長度是否大於 0 ,然後根據 hash 值找到對應的桶。
//(n - 1) & hash 這段程式碼是為了將 hash 值限制在陣列的邊界內,確保它能找到一個有效的桶。
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
//檢查第一個節點是否就是我們要找的節點,這裡比較了 hash 值和 key。
//注意這裡首先透過 == 來比較引用,如果失敗了再透過 equals 方法來比較值,這樣可以提高效率。
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果第一個節點不是我們要找的,就檢查下一個節點是否存在。
if ((e = first.next) != null) {
//如果首個節點是一個樹節點(即這個桶已經轉換為紅黑樹結構),則呼叫 getTreeNode 方法來獲取節點。
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//這是一個 do-while 迴圈,用來遍歷連結串列結構的桶中的每一個節點,直到找到匹配的節點或到達連結串列的尾部。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//如果沒有找到匹配的節點,則返回 null。
return null;
}
getNode 方法是 HashMap 中用於獲取指定鍵對應的節點的核心方法。它首先使用雜湊值來定位到正確的桶,然後在桶內使用連結串列或紅黑樹(如果桶中的元素過多時會轉換為紅黑樹來提高效能)來查詢正確的節點。
它充分利用了 Java 的多型特性和簡潔的迴圈結構來保證程式碼的簡潔和效能。
一句話:找到位置,取出來,判斷是否存在。
3.3 get 方法
java.util.HashMap#get
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key){
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
邏輯和 containsKey 一致,只是 getNode 之後,如果為 null 返回 null, 否則返回 e.value。
一句話:找到位置,取出來
四、迴歸問題
注:下面的作圖可能並不嚴謹,只是幫助理解,如有偏差請勿較真。
師兄給小明同學畫圖講解了一番…
4.1 三次 put 後的效果
Map<Player, Integer> myMap = new HashMap<>();
Player kai = new Player("Kai");
Player tom = new Player("Tom");
Player amanda = new Player("Amanda");
myMap.put(kai, 42);
myMap.put(tom, 200);
myMap.put(amanda, 88);
assertTrue(myMap.containsKey(kai));

其中綠色部分是鍵物件(注意是物件),紅色部分是值。
有同學可能說,這裡為為啥有個 Eric ? 這裡是假設在 map 中放入一個 eric ,它的目標位置。
敲黑板:位置和 Key 物件的 hashCode 有關係和 Value 無關。
4.2 修改後
// 將Kai的名字更改為Eric
kai.setName("Eric");
assertEquals("Eric", kai.getName());

敲黑板:Map 並沒有執行任何的寫操作,因此雖然 kai 的 name 被修改為了 Eric ,但是 kai 的位置並沒有發生變化。
4.3 執行判斷
Player eric = new Player("Eric");
assertEquals(eric, kai);
// 現在,map中既不包含Kai也不包含Eric:
assertFalse(myMap.containsKey(kai));
assertFalse(myMap.containsKey(eric));
當執行 myMap.containsKey(kai)
時,會根據其 name 即 Eric 去判斷是否有該 key 是否存在。

正如第一張圖所示,此時真正的 Eric 的位置並沒有元素,因此返回 false。
當執行 assertEquals(eric, kai); 時,由於重寫了 equals 方法,name 相等即為相等,所以兩者相等。
當執行 myMap.containsKey(eric) 時,和 myMap.containsKey(kai) 效果等價。
五、啟示
5.1 永不修改 HashMap 中的鍵
因此,永遠不要修改 HashMap 中的鍵,避免出現一些奇奇怪怪的現象,奇怪的現象遠不止前文所示。
修改 HashMap 的鍵可能會導致的幾個問題:
-
雜湊碼更改
當你修改一個 HashMap 中的鍵時,該鍵的雜湊碼可能會更改,導致該鍵的雜湊值不再與它當前所在的桶匹配。這將導致在使用該鍵進行查詢時找不到相關的條目。 -
導致資料不一致
由於鍵的雜湊碼已更改,這將導致資料結構的不一致。這意味著,即使你能夠以某種方式訪問修改後的鍵,你也將得到一個不一致的對映,其中鍵不再對映到正確的值。 -
違反對映的契約
修改 HashMap 中的鍵實際上違反了 Map 介面的基本契約,即每個鍵都應該對映到一個值。透過更改鍵,你實際上是在不透過 put 或 remove 方法的情況下更改對映,這是不允許的。 -
可能導致記憶體洩漏
修改 HashMap 中的鍵可能還會導致記憶體洩漏問題。因為如果你失去了訪問修改後的鍵的方式,那麼該鍵及其對應的值將無法從 Map 中刪除,從而導致記憶體洩漏。 -
破壞雜湊表的效能
HashMap 依賴於均勻的雜湊分佈來實現其期望的時間複雜度。修改鍵可以破壞雜湊分佈,從而大大降低雜湊表的效能。
5.2 防禦性程式設計
既然,永遠不要修改 HashMap 的 Key ,比如直接讓鍵類定義成不可變型別就好了。
最佳化如下:
public final classPlayer {
// 不允許修改
private final String name;
publicPlayer(String name){
this.name = name;
}
public String getName(){
return name;
}
// 注意,我們沒有提供setter方法
@Override
public boolean equals(Object o){
if (this == o) {
returntrue;
}
if (!(o instanceof Player)) {
returnfalse;
}
Player player = (Player) o;
return name.equals(player.name);
}
@Override
publicinthashCode(){
return name.hashCode();
}
}
5.3 自定義鍵類時謹慎重寫 equals 和 hashCode 方法
當自定義物件作 Map 的鍵時,一定要根據實際的場景慎重考慮是否要重寫 equals 和 hashCode 方法。
不恰當重寫 equals 和 hashCode 方法可能會導致一些奇奇怪怪的問題,以後用另外一篇來討論。比如兩個 Key 物件,分別對應兩個不同的值,導致後一個值覆蓋前一個值的"問題" (其實也未必是問題)。
publicclassPlayer {
private String name;
publicPlayer(String name){
this.name = name;
}
// 省略了getter和setter方法
@Override
public boolean equals(Object o){
if (this == o) {
returntrue;
}
if (!(o instanceof Player)) {
returnfalse;
}
Player player = (Player) o;
return name.equals(player.name);
}
@Override
publicinthashCode(){
return name.hashCode();
}
}
Map<Player, Integer> myMap = new HashMap<>();
Player kai1 = new Player("Kai");
Player kai2 = new Player("Kai");
myMap.put(kai1, 42);
// 此時 kai2 覆蓋了 kai1 的值
myMap.put(kai2, 88);
assertEquals(88,(int)myMap.get(kai1));
assertEquals(88,(int)myMap.get(kai2));
不重寫 hashCode 和 equals 方法:
publicclassPlayer {
private String name;
publicPlayer(String name){
this.name = name;
}
// 省略了getter和setter方法
}
驗證:
Map<Player, Integer> myMap = new HashMap<>();
Player kai1 = new Player("Kai");
Player kai2 = new Player("Kai");
myMap.put(kai1, 42);
myMap.put(kai2, 88);
assertEquals(42,(int)myMap.get(kai1));
assertEquals(88,(int)myMap.get(kai2));
六、總結
每一個問題背後都是一個絕佳的學習機會。每一個奇奇怪怪的問題背後都有很多知識盲點。
希望大家可以抓住每一個問題知其然,知其所然,不斷精進技術。
基於Hologres輕量高效能OLAP分析解決方案
本方案基於阿里雲Hologres和DataWorks資料整合,透過簡單的產品操作即可完成資料庫RDS即時同步資料到Hologres,並透過Hologres強大的查詢分析效能,完成一站式高效能的OLAP資料分析。
點選閱讀原文檢視詳情。