java hashmap bucket 真的包含一个列表吗？
Does a java hashmap bucket really contain a list?
我一直确信 'bucket' 中的 java 散列映射包含链表或某种树，实际上您可以在网上的许多地方读到桶如何保留此列表，然后使用 equals 函数遍历条目以查找存储在同一存储桶中的条目（即具有相同的密钥），请记住这一点，有人可以解释为什么以下琐碎的代码无法按预期工作：-
private class MyString {
String internalString;
MyString(String string) {
internalString = string;
}
@Override
public int hashCode() {
return internalString.length(); // rubbish hashcode but perfectly legal
}
}
...
Map<MyString, String> map = new HashMap<>();
map.put(new MyString("key1"), "val1");
map.put(new MyString("key2"), "val2");
String retVal = map.get(new MyString("key1"));
System.out.println("Val returned = "+retVal);
在这个例子中，我希望两个映射条目位于（相同）存储桶的列表中，并且 retVal 等于“val1”，但它等于 null？
快速调试说明了原因，存储桶根本不包含列表，只有一个条目.....
我以为我要疯了，直到我在 baeldung 网站上看到这篇文章 (https://www.baeldung.com/java-map-duplicate-keys)
...但是，现有 Java 核心 Map 实现中的 none 允许 Map 处理单个键的多个值。
怎么回事，哈希映射中的桶是否包含列表？
Does a java hashmap bucket really contain a list?
视情况而定。
对于较旧的实现（Java 7 及更早版本），是的，它确实包含列表。 （是内部Node类型的单向链表。）
对于较新的实现（Java 8 及更高版本），它可以包含列表或二叉树，具体取决于散列到特定存储桶的条目数。如果数量少，就用单向链表。如果数字大于硬编码阈值（Java 8 中的 8），则 HashMap 将列表转换为平衡二叉树...因此桶搜索是 O(logN)而不是 O(N)。这减轻了产生大量冲突的散列码函数的影响（或者可以通过以特定方式选择键来使其发生的冲突。）
如果您想详细了解 HashMap 的工作原理，请阅读源代码。 （评论很好，评论解释了基本原理以及它是如何工作的。现在更糟糕的是......如果你对这种事情感兴趣。）
However, none of the existing Java core Map implementations allow a Map to handle multiple values for a single key.
这完全是另外一回事。那是关于一个键的多个值而不是存储桶中的多个键。
这篇文章是正确的。这与我的“一个桶包含一个列表或树”的声明并不矛盾。
简单地说，一个HashMap桶可以包含多个键/值对，其中键都是不同的。
我唯一会指责引用的文本的一点是它似乎暗示它是实现 [=16] =] 具有每个键限制的一个值。实际上，是 Map API 本身施加了此限制...除非您使用（比如说）List 作为地图的值类型。
我一直确信 'bucket' 中的 java 散列映射包含链表或某种树，实际上您可以在网上的许多地方读到桶如何保留此列表，然后使用 equals 函数遍历条目以查找存储在同一存储桶中的条目（即具有相同的密钥），请记住这一点，有人可以解释为什么以下琐碎的代码无法按预期工作：-
private class MyString {
String internalString;
MyString(String string) {
internalString = string;
}
@Override
public int hashCode() {
return internalString.length(); // rubbish hashcode but perfectly legal
}
}
...
Map<MyString, String> map = new HashMap<>();
map.put(new MyString("key1"), "val1");
map.put(new MyString("key2"), "val2");
String retVal = map.get(new MyString("key1"));
System.out.println("Val returned = "+retVal);
在这个例子中，我希望两个映射条目位于（相同）存储桶的列表中，并且 retVal 等于“val1”，但它等于 null？ 快速调试说明了原因，存储桶根本不包含列表，只有一个条目.....
我以为我要疯了，直到我在 baeldung 网站上看到这篇文章 (https://www.baeldung.com/java-map-duplicate-keys) ...但是，现有 Java 核心 Map 实现中的 none 允许 Map 处理单个键的多个值。
怎么回事，哈希映射中的桶是否包含列表？
Does a java hashmap bucket really contain a list?
视情况而定。
对于较旧的实现（Java 7 及更早版本），是的，它确实包含列表。 （是内部Node类型的单向链表。）
对于较新的实现（Java 8 及更高版本），它可以包含列表或二叉树，具体取决于散列到特定存储桶的条目数。如果数量少，就用单向链表。如果数字大于硬编码阈值（Java 8 中的 8），则 HashMap 将列表转换为平衡二叉树...因此桶搜索是 O(logN)而不是 O(N)。这减轻了产生大量冲突的散列码函数的影响（或者可以通过以特定方式选择键来使其发生的冲突。）
如果您想详细了解 HashMap 的工作原理，请阅读源代码。 （评论很好，评论解释了基本原理以及它是如何工作的。现在更糟糕的是......如果你对这种事情感兴趣。）
However, none of the existing Java core Map implementations allow a Map to handle multiple values for a single key.
这完全是另外一回事。那是关于一个键的多个值而不是存储桶中的多个键。
这篇文章是正确的。这与我的“一个桶包含一个列表或树”的声明并不矛盾。
简单地说，一个HashMap桶可以包含多个键/值对，其中键都是不同的。
我唯一会指责引用的文本的一点是它似乎暗示它是实现 [=16] =] 具有每个键限制的一个值。实际上，是 Map API 本身施加了此限制...除非您使用（比如说）List 作为地图的值类型。