Java hashmap中的bucket究竟是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/37959941/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What exactly is bucket in hashmap?
提问by dgupta3091
Recently, in an interview I was asked, what exactly is a bucket in hashmap? Whether it is an array or a arraylist or what?
最近，在一次采访中我被问到，hashmap 中的桶到底是什么？无论是数组还是数组列表还是什么？
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 ?
我很困惑。我知道哈希图是由数组支持的。那么我可以说存储桶是一个容量为 16 的数组，在开始存储哈希码并且链接列表有它们的起始指针吗？
I know how a hashmap internally works, just wanted to know what exactly is a bucket in terms of data structures.
我知道 hashmap 内部是如何工作的，只是想知道就数据结构而言，bucket 到底是什么。
采纳答案by Eran
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 版本中，每个存储桶都包含一个 Map 条目的链接列表。在新的 Java 版本中，每个桶包含条目的树结构或条目的链表。
From the implementation notes in Java 8:
来自 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.
...
回答by Arun
I hope this may help you to understand the implementation of hash map well.
我希望这可以帮助您更好地理解哈希映射的实现。
回答by Piyush Desai
Buckets are basically a data structure that is being used in the Paging algorithm of the Operating System . To be in a very Laymans language.
存储桶基本上是在操作系统的分页算法中使用的数据结构。使用非常外行的语言。
The objects representing a particular hashcode is being stored in that bucket.(basically you can consider the header of the linked list data structure to be the hashcode value which is represented in the terms of bucket)
表示特定哈希码的对象存储在该存储桶中。（基本上，您可以将链表数据结构的标头视为以存储桶表示的哈希码值）
The references of the object is being stored in the link list , whose header represents the value of the Hashcode.
对象的引用被存储在链表中，链表的头部代表了哈希码的值。
The JVM creates them and the size, depends upon the memory being allocated by the JVM.
JVM 创建它们和大小，取决于 JVM 分配的内存。
回答by stinger
Buckets exactlyis an array of Nodes. So single bucket is an instance of class java.util.HashMap.Node. Each Node is a data structure similar to LinkedList, or may be like a TreeMap (since Java 8), HashMap decides itself what is better for performance--keep buckets as LinkedList or TreeMap. TreeMap will be only chosen in case of poorly designed hashCode() function, when lots of entries will be placed in single bucket. See how buckets look like in HashMap:
桶正是一个节点数组。所以单桶是 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;
