阿里妹導讀
本文透過一個程式設計師小明遇到的實際問題，深入探討了在使用 HashMap 時由於鍵物件的可變性導致的資料訪問異常。
如果你只想看結論，給你上個一句話省流版：
一、前言
一天程式設計師小明跑到師兄面前說 ：“師兄，我看到一個很詭異的現象，百思不得其解”。
師兄說：“莫慌，你且慢慢說來”
程式設計師小明說道：“我放到 Map 中的資料還在，但是怎麼也取不出來了…”
師兄，於是幫小明看了他的程式碼，發現了很多不為人知的秘密….
二、場景復現
小明 定義了一個 Player 作為 Map 的 key ：
publicclassPlayer {private String name;publicPlayer(String name){this.name = name; }// 省略了getter和setter方法 @Overridepublic boolean equals(Object o){if (this == o) {returntrue; }if (!(o instanceof Player)) {returnfalse; } Player player = (Player) o;return name.equals(player.name); } @OverridepublicinthashCode(){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的名字更改為Erickai.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的名字更改為Erickai.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方法 @Overridepublic boolean equals(Object o){if (this == o) {returntrue; }if (!(o instanceof Player)) {returnfalse; } Player player = (Player) o;return name.equals(player.name); } @OverridepublicinthashCode(){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方法 @Overridepublic boolean equals(Object o){if (this == o) {returntrue; }if (!(o instanceof Player)) {returnfalse; } Player player = (Player) o;return name.equals(player.name); } @OverridepublicinthashCode(){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資料分析。
點選閱讀原文檢視詳情。
