悲催，放到 Map 中的元素取不出来了！！

作者：明明如月学长， CSDN 博客专家，大厂高级 Java 工程师，《性能优化方法论》作者、《解锁大厂思维：剖析《阿里巴巴Java开发手册》》、《再学经典：《EffectiveJava》独家解析》专栏作者。

热门文章推荐：

• （1）《为什么很多人工作 3 年 却只有 1 年经验？》
• （2）《从失望到精通：AI 大模型的掌握与运用技巧》
• （3）《AI 时代，程序员的出路在何方？》
• （4）《如何写出高质量的文章：从战略到战术》
• （5）《我的技术学习方法论》
• （6）《我的性能方法论》
• （7）《AI 时代的学习方式： 和文档对话》
• （8）《人工智能终端来了，你还在用过时的 iterm？》

一、前言

一天程序员小明跑到师兄面前说 ：“师兄，我看到一个很诡异的现象，百思不得其解”。
师兄说：“莫慌，你且慢慢说来”
程序员小明说道：“我放到 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();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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));

1
2
3
4
5
6
7
8
9

接下来，让小明将玩家 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));

1
2
3
4
5
6
7
8
9
10
11
12
13
14

如上面的测试所示，更改 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);

1
2
3
4
5
6
7
8

小明，百思不得其姐？

给你 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 key, or
 *         null if there was no mapping for key.
 *         (A null return can also indicate that the map
 *         previously associated null with key.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

该方法的主要目的是减少哈希碰撞和更好地分配哈希桶。高 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;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

putVal 方法是一个非常核心和复杂的方法，它处理了很多细节，包括初始化哈希表，确定正确的桶，处理链表和红黑树结构，以及正确的插入或更新节点的值。

一句话：找到合适的位置，放到该位置上。

3.2 containsKey 方法

3.2.1 containsKey 概览

既然是 containsKey 不符合预期，我们就看下它的逻辑：
java.util.HashMap#containsKey

    /**
     * Returns true if this map contains a mapping for the
     * specified key.
     *
     * @param   key   The key whose presence in this map is to be tested
     * @return true if this map contains a mapping for the specified
     * key.
     */
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

1
2
3
4
5
6
7
8
9
10
11
12

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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.
     *
     * 
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.)
     *
     * 
A return value of {@code null} does not necessarily
     * 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;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

逻辑和 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));

1
2
3
4
5
6
7
8
9
10
11

其中绿色部分是键对象（注意是对象），红色部分是值。

有同学可能说，这里为为啥有个 Eric ? 这里是假设在 map 中放入一个 eric ，它的目标位置。
敲黑板：位置和 Key 对象的 hashCode 有关系和 Value 无关。

4.2 修改后

// 将Kai的名字更改为Eric
kai.setName("Eric");
assertEquals("Eric", kai.getName());

1
2
3
4

敲黑板：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));
1
2
3
4
5
6

当执行 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();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

       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));
1
2
3
4
5
6
7
8
9
10

不重写 hashCode 和 equals 方法：

public class Player {
    private String name;

    public Player(String name) {
        this.name = name;
    }

    // 省略了getter和setter方法

}

1
2
3
4
5
6
7
8
9
10
11

验证：

        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));
1
2
3
4
5
6
7
8

六、总结

每一个问题背后都是一个绝佳的学习机会。每一个奇奇怪怪的问题背后都有很多知识盲点。
希望大家可以抓住每一个问题知其然，知其所然，不断精进技术。

---

创作不易，如果本文对你有帮助，欢迎点赞、收藏加关注，你的支持和鼓励，是我创作的最大动力。

欢迎加入我的知识星球，知识星球ID：15165241 （已经经营 3年多）一起交流学习。
https://t.zsxq.com/Z3bAiea 申请时标注来自CSDN。