hashmap中的bucket到底是什么？

Question

最近在采访中被问到，hashmap中的bucket到底是什么？它是数组还是数组列表还是什么？

我很困惑。我知道哈希图由数组支持。那么我可以说桶是一个容量为 16 的数组，开始存储哈希码，链表有它们的起始指针吗？

我知道 hashmap 的内部工作原理，只是想知道在数据结构方面 bucket 到底是什么。

Answer 1

不，桶是您所指的数组中的每个元素。在早期的 Java 版本中，每个桶都包含一个映射条目的链接列表。在新的 Java 版本中，每个存储桶包含条目的树结构或条目的链接列表。

来自Java 8 中的实施说明：

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.
 ...

Answer 2

我希望这可以帮助您更好地理解哈希映射的实现。

Answer 3

桶基本上是操作系统分页算法中使用的一种数据结构。使用非常通俗的语言。

表示特定哈希码的 objects 存储在该桶中。（基本上您可以将 linked 列表数据结构的 header 视为哈希码值以桶的形式表示）

object 的引用存储在 link 列表中，其 header 代表哈希码的值。

JVM 创建它们，大小取决于 JVM 分配的内存。

Answer 4

Buckets exactly 是一个节点数组。所以单桶是classjava.util.HashMap.Node的一个实例。每个 Node 都是一个类似于 LinkedList 的数据结构，或者可能像一个 TreeMap（因为 Java 8），HashMap 自己决定什么对性能更好——将桶保持为 LinkedList 或 TreeMap。只有在 hashCode() 函数设计不当的情况下才会选择 TreeMap，此时大量条目将被放置在单个存储桶中。查看桶在 HashMap 中的样子：

/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

Answer 5

Hashmap Bucket是基于索引计算存储多个节点和存储hashmap对象的节点，基于链表架构连接的每个节点。

hashmap中的bucket到底是什么？

What exactly is bucket in hashmap?

java

linked-list

hashmap

hashcode

bucket