hashmap中的bucket究竟是什么? [英] What exactly is bucket in hashmap?

问题描述

最近，在一次采访中我被问到，hashmap 中的桶到底是什么?无论是数组还是数组列表还是什么?

Recently, in an interview I was asked, what exactly is a bucket in hashmap? Whether it is an array or a arraylist or what?

我糊涂了.我知道哈希图是由数组支持的.那么我可以说bucket是一个容量为16的数组，在开始存储哈希码并且链接列表有它们的开始指针吗?

I got confused. I know hashmaps are backed by arrays. So can I say that bucket is an array with a capacity of 16 in the start storing hashcodes and to which linked lists have their start pointer ?

我知道 hashmap 内部是如何工作的，只是想知道就数据结构而言，bucket 到底是什么.

I know how a hashmap internally works, just wanted to know what exactly is a bucket in terms of data structures.

推荐答案

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

No, a bucket is each element in the array you are referring to. In earlier Java versions, each bucket contained a linked list of Map entries. In new Java versions, each bucket contains either a tree structure of entries or a linked list of entries.

来自 Java 8 中的实现说明:

From the implementation notes in 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.
 ...

这篇关于hashmap中的bucket究竟是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！