Is HashMap internally implemented in Java using LinkedList or Array?

Question

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 1

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.

Answer 2

Each HashMap has an Array and in that Array it places each Entry in a position according to its key's hash code (e.g. int position = entry.getKey().hashCode() % array.length). The position where an Entry is stored is called a bucket.

If more than one Entry ends up in the same bucket, those Entries are combined in a LinkedList (also see @Dukeling's answer). Thus the bucket metaphor: each Array index is a "bucket" where you dump in all matching keys.

You have to use an Array for the buckets in order to achieve the desired constant time performance for random access. Within a bucket you have to traverse all elements to find the desired key anyways, so you can use a LinkedList as it is easier to append to (no resize needed).

This also shows the need for a good hash function, because if all keys hash to only a few values you will get long LinkedLists to search and a lot of (fast to access) empty buckets.