问题描述
最近，在一次采访中，有人问我，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的数组，开始存储hashcode，哪些链表有起始指针?
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 ?
我知道哈希图在内部是如何工作的，只是想知道存储桶在数据结构方面到底是什么.
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 到底是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！