阿里妹导读
本文通过一个程序员小明遇到的实际问题，深入探讨了在使用 HashMap 时由于键对象的可变性导致的数据访问异常。
如果你只想看结论，给你上个一句话省流版：
一、前言
一天程序员小明跑到师兄面前说 ：“师兄，我看到一个很诡异的现象，百思不得其解”。
师兄说：“莫慌，你且慢慢说来”
程序员小明说道：“我放到 Map 中的数据还在，但是怎么也取不出来了...”
师兄，于是帮小明看了他的代码，发现了很多不为人知的秘密....
二、场景复现
小明 定义了一个 Player 作为 Map 的 key ：
public class Player { private String name; public Player(String name) { this.name = name; } // 省略了getter和setter方法 @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof Player)) { return false; } Player player = (Player) o; return name.equals(player.name); } @Override public int hashCode() { 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. */ static final int hash(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 方法来处理。 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); 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 class Player { // 不允许修改 private final String name; public Player(String name) { this.name = name; } public String getName() { return name; } // 注意，我们没有提供setter方法 @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof Player)) { return false; } Player player = (Player) o; return name.equals(player.name); } @Override public int hashCode() { return name.hashCode(); }}
5.3 自定义键类时谨慎重写 equals 和 hashCode 方法
当自定义对象作 Map 的键时，一定要根据实际的场景慎重考虑是否要重写 equals 和 hashCode 方法。不恰当重写 equals 和 hashCode 方法可能会导致一些奇奇怪怪的问题，以后用另外一篇来讨论。比如两个 Key 对象，分别对应两个不同的值，导致后一个值覆盖前一个值的"问题" (其实也未必是问题)。
public class Player { private String name; public Player(String name) { this.name = name; } // 省略了getter和setter方法 @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof Player)) { return false; } Player player = (Player) o; return name.equals(player.name); } @Override public int hashCode() { 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 方法：
public class Player { private String name; public Player(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数据分析。
