← back to index

How HashMap Handles Collisions

The linked-list shape Java's HashMap uses for hash collisions.

published Mar 18, 2019 tags #data-structures #java

~/posts/hashmap-collisions $ cat post.md

/ LANG EN / 中文
/ THEME / /

Background

How a hash table works is well-trodden ground, and there are plenty of deep-dives into specific languages’ implementations. I once got asked in an interview:

What if two hash values collide?

I answered: keep them in the same slot, compare on lookup. Then:

What structure are they stored in?

A linked list. Then they asked what each node in that list looks like. This post is to nail that down.

Collision handling

Java’s HashMap, in short (source omitted):

The underlying array holds instances of an Entry class. Entry carries key, value, hash, and doubles as a linked-list node by holding a pointer to the next Entry.

  • No collision: the new Entry lands directly in the slot.
  • Collision: the new element replaces the existing entry in the slot, and its next pointer is set to the entry that used to live there.

The upside of this design: linked-list traversal doesn’t need to special-case “first element”. A unique-hash entry simply has next = null; insertion logic is identical either way.

← back to index