Is HashMap internally implemented in Java using LinkedList or Array?

java arrays linked-list hashmap hashset
dexterousashish picture dexterousashish · Sep 24, 2013 · Viewed 22.7k times · Source

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?

Answer

Bernhard Barker picture Bernhard Barker · Sep 24, 2013

It basically looks like this:

 this is the main array
   ↓
[Entry] → Entry → Entry      ← here is the linked-list
[Entry]
[Entry] → Entry
[Entry]
[null ]
[null ]

So you have the main array where each index corresponds to some hash value (mod'ed* to the size of the array).

Then each of them will point to the next entry with the same hash value (again mod'ed*). This is where the linked-list comes in.

*: As a technical note, it's first hashed with a different function before being mod'ed, but, as a basic implementation, just modding will work.

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
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
why LinkedList doesn't have initialCapacity in java?

I wonder why LinkedList doesn't have initialCapacity. I know good when to use ArrayList and when LinkedList. Its good practice to define Collection final size like: List<String> arraylist = new ArrayList<String>(5); For LinkedList for example: …

Read More