What exactly is bucket in hashmap?

java linked-list hashmap hashcode bucket
dgupta3091 picture dgupta3091 · Jun 22, 2016 · Viewed 31.8k times · Source

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

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.

Answer

Eran picture Eran · Jun 22, 2016

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.

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

Related questions

When to use HashMap over LinkedList or ArrayList and vice-versa

What is the reason why we cannot always use a HashMap, even though it is much more efficient than ArrayList or LinkedList in add,remove operations, also irrespective of the number of the elements. I googled it and found some …

Read More
Is HashMap internally implemented in Java using LinkedList or Array?

How is HashMap internally implemented? I read somewhere that it uses LinkedList while other places it mentions Arrays. I tried studying the code for HashSet and found Entry array. Then where is LinkedList used?

Read More
Best way to store Country codes, names, and Continent in Java

I want to have a List or Array of some sort, storing this information about each country: 2 letter code Country name such as Brazil Continent/region of the world such as Eastern Europe, North America, etc. I will classify each …

Read More