HashMap的实现是否会在链表中存储键值对？

Question

HashMap的实现是否会在链表中存储键值对？

java

3

我在一本书中读到，当我们将元素放入HashMap中时，它会在内部存储在桶中。我的问题是：

HashMap是否将键值对作为链表存储？或者只有发生冲突时才存储在链表中？
当两个不同的对象存储在同一个桶中时，它如何检索对象？

谢谢！

- Mike

可能是HashMap碰撞的重复问题。 - Matt Ball

我的问题非常具体，即使没有冲突，它是否有链表？ - Mike

这可能很有用：http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html#.ThYUH2GqLFk - zw324

要了解更多关于这些事情的内容，请阅读我的 Internal life of HashMap 教程。 - Volodymyr Levytskyi

3个回答

3

桶数组的数据类型是Map.Entry。当多个条目落入同一个桶中时，它们被存储在概念上是单向链表的位置，通过保持对下一个Entry的引用。只有“头”处的Entry位于作为桶的数组中。但是，从不使用java.util.LinkedList或其他实际列表类。条目仅通过保持对其桶伙伴的引用而形成列表。当桶中有多个条目时，它从实际位于Map.Entry[]中的条目开始，这是列表的头部，并且只是开始遍历和检查.equals()，直到找到匹配项或下一个为空。

- Affe

0

理解编程最好的方法是追踪源代码

在Eclipse中，如果配置了JDK，请按ctrl+shift+T，然后输入HashMap和AbstractMap
AbstractMap 和 HashMap

你只需要做一次！

- Prashant Bhate

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DNA · Accepted Answer

有许多关于http://en.wikipedia.org/wiki/Hash_table哈希表的细节。

另请参阅java.util.HashMap和HashSet的内部实现。

当然，你也可以使用源代码。

更新：为了明确回答你的问题，它存储一个Entry，该Entry具有对存储桶中下一项（如果有）的引用。如果桶中只有一项，则引用将为null：

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