hashmap中的bucket到底是什么?

h4cxqtbf  于 2021-07-12  发布在  Java
关注(0)|答案(4)|浏览(732)

最近,在一次采访中,有人问我,hashmap中的bucket到底是什么?是数组还是数组列表?
我搞糊涂了。我知道hashmaps是由数组支持的。所以我可以说bucket是一个数组,在开始存储hashcode时的容量是16,链表的开始指针指向哪个?
我知道hashmap在内部是如何工作的,只是想知道在数据结构方面什么是bucket。

t9eec4r0

t9eec4r01#

不,bucket是指数组中的每个元素。在早期的java版本中,每个bucket都包含一个Map条目的链表。在新的java版本中,每个bucket要么包含一个条目树结构,要么包含一个条目链表。
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.
 ...
q5iwbnjs

q5iwbnjs2#


希望这能帮助您更好地理解hash-map的实现。

eanckbw9

eanckbw93#

bucket就是一个节点数组。所以single bucket是java.util.hashmap.node类的一个示例。每个节点都是一个类似于linkedlist的数据结构,或者可能类似于treemap(因为java 8),hashmap自行决定什么对性能更有利--将bucket保留为linkedlist或treemap。只有在hashcode()函数设计不好的情况下才会选择treemap,因为在单个bucket中会放置大量条目。在hashmap中查看bucket的外观:

/**
     * 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;
xdyibdwo

xdyibdwo4#

bucket基本上是一种数据结构,用于操作系统的分页算法。用一种非常通俗的语言。
表示特定hashcode的对象存储在该bucket中(基本上,您可以将链表数据结构的头视为用bucket表示的hashcode值)
对象的引用存储在链接列表中,链接列表的头表示hashcode的值。
jvm创建它们,其大小取决于jvm分配的内存。

相关问题