Java HashMap内部如何存储条目

Question

假设您有一个键类（KeyClass），其中包括重写的equals、hashCode和clone方法。假设它有两个原始字段，一个字符串（name）和一个整数（id）。

现在您定义：

KeyClass keyOriginal, keyCopy, keyClone;

keyOriginal = new KeyClass("original", 1);
keyCopy = new KeyClass("original", 1);
keyClone = KeyClass.clone();

现在

keyOriginal.hashCode() == keyCopy.hashCode() == keyClone.hashCode()
keyOriginal.equals(keyCopy) == true
keyCopy.equals(keyClone) == true

就HashMap而言，keyOriginal、keyCopy和keyClone是无法区分的。

如果你使用keyOriginal向HashMap中添加一个条目，你可以使用keyCopy或keyClone来检索它，也就是说

map.put(keyOriginal, valueOriginal);
map.get(keyCopy) will return valueOriginal
map.get(keyClone) will return valueOriginal

另外，如果你在将键放入映射之后改变了它，就无法检索到原始值。举个例子：

keyOriginal.name = "mutated";
keyOriginal.id = 1000;

Now map.get(keyOriginal) will return null

那么我的问题是

当你使用map.keySet()时，它将返回映射中所有键。HashMap类如何知道映射中所存储的所有键、值和条目的完整列表呢？

编辑 据我所知，它通过将Entry键作为一个final变量来实现。

static class Entry<K,V> implements Map.Entry<K,V> { 
  final K key; 

我理解在将键放入映射中后，即使我改变了该键，原始键仍然保留。但是，即使保留了原始键引用，仍然可以更改其内容。因此，如果更改了内容并且K,V仍存储在原始位置，则如何进行检索？ 编辑 如果在将键放入哈希表后更改键，则检索将失败。因此，不建议使用具有可变哈希表键。

- Basanth Roy

---

为什么不直接查看源代码呢？它是公开且易于访问的。 - user177800

如果它不能这样做，那也不会成为一个数据结构，你认为它如何能够查找你想要的特定键呢？ - Nim

对于好奇的人，这是源代码：http://www.docjar.com/html/api/java/util/HashMap.java.html - Alexander Pavlov

查找单个键只需要计算hashCode，然后使用equals比较每个冲突的键。但是HashMap需要知道存储在其中的所有键，而不需要客户端传递键。因此，下面Louis的答案看起来就是这样实现的。 - Basanth Roy

Answer 1

HashMap维护了一张条目表，其中包含按照它们的哈希码组织的关联键和值的引用。如果您改变了一个键，则哈希码将改变，但是在HashMap中的条目仍然根据原始哈希码放置在哈希表中。这就是为什么map.get(keyOriginal)会返回null。

map.keySet()只是遍历哈希表，返回每个条目的键。

- Louis Wasserman

---

如果您更改键，则哈希码将更改，但HashMap中的条目仍根据原始哈希码放置在哈希表中。我已经阅读了源代码。因此，我认为它通过将Entry键设置为final变量来工作。static class Entry<K,V> implements Map.Entry<K,V> { final K key; (http://www.docjar.com/html/api/java/util/HashMap.java.html)。因此，即使我将其放入映射后更改键，原始键也会保留。我的理解正确吗？谢谢。 - Basanth Roy

它保存了对键的引用。如果您更改键，则HashMap的entrySet()将看到修改后的键，但get(key)将在错误的位置查找，因此当您尝试map.get(key)时，它将返回null。基本上，在Map中具有可变键只会带来麻烦，实际上继续在Map中突变键就像是向自己的膝盖开枪。 - Louis Wasserman

再次感谢您。但是我仍然没有理解这个问题。您有一个keyOriginal和keyCopy，它们具有相同的字段值。现在将keyOriginal放入映射表中。假设它进入了内部哈希映射表的100号位置。现在如果您更改keyOriginal，它仍然存储在100号位置。现在，如果您调用map.get(keyCopy)，它确实会返回原始关联的值。如果keyOriginal.equals(keyCopy)为false，它是如何做到的？ - Basanth Roy

你测试过了吗？如果那是真的，我会非常惊讶。我强烈预计 map.get(keyCopy) 会返回 null。 - Louis Wasserman

是的，我已经测试过了。我会在一个新问题中添加测试代码。我不能在这里添加，因为它太长了。 - Basanth Roy

Answer 2

如果您更改了条目但未更改hashCode，则是安全的。因此，最佳实践是使hashCode、equals和compareTo中的所有字段都是final和不可变的。

- Peter Lawrey

---

谢谢。好信息。-- "如果你改变了条目但没有改变hashCode，那么是安全的。" -- 我想补充说，你仍然不安全，因为equals会失败。 - Basanth Roy

所以我想可以这样说，如果在添加到映射之后改变键（hashCode不同且equals为false），那么检索将失败。 - Basanth Roy

除非这是你的本意。;) 如果它必须是可变的，你可以删除键，更新它并重新添加它。只有当你在它作为映射的键（或Set的元素）时更改键才会成为问题。 - Peter Lawrey

是的，真的，这不是我在这种情况下的意图。 - Basanth Roy

Answer 3

简单来说，HashMap 是计算机内存中包含键和值的对象。每个键都是唯一的（请阅读哈希码），并且每个键指向一个单独的值。

在您的代码示例中，在每种情况下从映射中出来的值都是相同的，因为键是相同的。当您更改键时，没有办法获取其值，因为您从未使用变异的键向 HashMap 添加项目。

如果您添加了以下行：

map.put("mutated", 2);

在修改键之前，您将不再获得 null 值。

- schottsfired