什么是hashmap中的桶？

Question

最近,在一次采访中我被问到,hashmap中究竟是什么？无论是数组还是arraylist还是什么？

我很困惑.我知道哈希映射是由数组支持的.那么我可以说bucket是一个容量为16的数组,在开始存储哈希码时,链接列表的起始指针是什么？

我知道hashmap内部是如何工作的,只是想知道数据结构方面究竟是什么样的桶.

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

Answer 2

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

Answer 3

桶正是一个节点数组。所以单桶是 java.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;