java - hashMap 是否实现为链表数组

Question

在阅读HashMap时我看到它是作为一个桶数组实现的？现在这些桶总是链表吗？如果是这样，为什么它们被称为桶而不是链表？

Answer 1

查看 的源代码HashMap告诉我们它是作为一个 Entries 数组实现的：

transient Entry[] table;

每个 Entry 都有一个 field next，因此它们创建了一个链表结构：

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

“桶”是一个更高级别的术语，在文献中和解释哈希映射时使用。这里的“桶”被实现为单个链表。

Answer 2

在 Java 的 Hashmap 中，桶被实现为一个链表（每个Entry都引用另一个名为 的条目next）。

术语“桶”是指一个概念。链表实现细节。

Answer 3

Java，使用“分离链”的概念，它被实现为一个链表数组，以避免冲突。但是，情况并非总是如此。一个 hashmap 可以完全实现为一个数组（线性探测）；这虽然有更高的机会产生碰撞。

关于你的“桶”问题。你可以把链表想象成一个桶。但是，如果您的 HashMap 实现使用适当的 HashFunction（在 hashmap 数组中分配值的算法），那么您的“桶”最好只有一个项目。