哈希图中的存储桶到底是什么？

Question

最近，在一次采访中有人问我，哈希图中的存储桶到底是什么？是数组还是arraylist还是什么？

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

我知道哈希图在内部是如何工作的，只是想知道就数据结构而言，存储桶到底是什么。

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.
 ...