hashmap中的bucket到底是什么？

Question

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

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

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

原文由 dgupta3091 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

不，桶是您所指的数组中的每个元素。在早期的 Java 版本中，每个桶都包含一个 Map 条目的链接列表。在新的 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.
 ...

原文由 Eran 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

原文由 Arun 发布，翻译遵循 CC BY-SA 3.0 许可协议