悲催,放到Map中的元素取不出來了

阿里妹導讀
本文透過一個程式設計師小明遇到的實際問題,深入探討了在使用 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資料分析。    
點選閱讀原文檢視詳情。

相關文章