AlgoMaster Logo

Design HashMap

easyFrequency10 min readUpdated June 23, 2026

Understanding the Problem

We need three operations: insert (or update), lookup, and delete. The core challenge is mapping arbitrary keys to storage locations efficiently.

One approach is an array indexed directly by the key. That works when the key range is small and known. A general hash map handles arbitrary keys by using a hash function to compress keys into a smaller range of indices, then resolving collisions when two keys map to the same index.

The design decisions are array size, hash function, and collision strategy. These choices determine the trade-off between memory usage and operation speed.

Key Constraints:

  • 0 <= key, value <= 10^6 → Keys are non-negative integers up to one million. A direct-address array of 10^6 + 1 slots is feasible but wasteful when only a few keys are stored.
  • At most 10^4 calls → The operation count is small, so even O(n) per operation would pass within time limits. The goal here is an efficient design, so we aim for O(1) average per operation.
  • The value -1 is reserved as the "not found" return, and values can be any integer in [0, 10^6], so -1 is safe to use as a sentinel for an absent key.

Approach 1: Brute Force (Direct Address Array)

Intuition

Keys range from 0 to 10^6, so we can allocate an array large enough to hold every possible key and use the key itself as the index. There is no hashing and no collision handling.

This is a direct-address table: the mapping is array[key] = value. We initialize every slot to -1 (meaning "no mapping"), and put, get, and remove become single array accesses.

Algorithm

  1. Create an integer array of size 10^6 + 1, initialized to -1
  2. put(key, value): Set array[key] = value
  3. get(key): Return array[key] (returns -1 if never set)
  4. remove(key): Set array[key] = -1

Example Walkthrough

Trace Example 1 on a direct-address array. Only the slots at indices 1, 2, and 3 ever change, so the trace tracks those three; every other slot stays at -1.

The returned values are 1, -1, 1, -1, matching the expected output for the four read operations.

Code

This wastes about 4MB of memory even when only a handful of entries are stored, and it does not generalize to larger or unbounded key ranges. The next approach uses a smaller array plus a hash function to map keys into it.

Approach 2: Array of Linked Lists (Chaining)

Intuition

Instead of an array that covers every possible key, we use a much smaller array (size 769) and a hash function to map each key to a bucket index: bucket = key % 769. Multiple keys can map to the same bucket, which is a collision.

To handle collisions, each bucket stores a linked list of (key, value) pairs. To put a key, we hash it to find the bucket, then walk the list to either update an existing entry or insert a new one. Get and remove work the same way: hash to the bucket, then search the list.

The bucket count 769 is prime. A prime distributes keys more evenly when keys share common factors. With a power-of-2 size like 1024, keys that share a factor of 2 cluster into a subset of buckets; with a size of 1000, keys 0, 1000, 2000 all map to bucket 0. A prime has no small common factors with structured key patterns, so it reduces this systematic clustering.

This is the core mechanism behind java.util.HashMap and Python's dict, though production implementations add dynamic resizing, stronger hash functions, and tree-based buckets for degenerate cases.

Algorithm

  1. Create an array of size 769, where each slot holds the head of a linked list
  2. Define a hash function: hash(key) = key % 769
  3. put(key, value):
    • Compute bucket = hash(key)
    • Walk the linked list at bucket
    • If a node with this key exists, update its value
    • Otherwise, insert a new node at the head of the list
  4. get(key):
    • Compute bucket = hash(key)
    • Walk the linked list at bucket
    • If a node with this key exists, return its value
    • Otherwise, return -1
  5. remove(key):
    • Compute bucket = hash(key)
    • Walk the linked list at bucket
    • If a node with this key exists, remove it from the list

Example Walkthrough

Trace the operations put(1,1), put(770,2), put(1539,3), then get(1), get(770), get(1539). All three keys collide because 1 % 769 = 770 % 769 = 1539 % 769 = 1, so they form one chain in bucket 1. New nodes are inserted at the head, so each put pushes onto the front of the chain. The visualization below shows bucket 1's chain, head on the left.

1put(1,1): bucket = 1%769 = 1. Chain empty, insert (1,1) at head
[(1,1)]
1/6

The three gets return 1, 2, 3, matching the expected output. Each lookup hashes to bucket 1, then scans the chain until the key matches.

Code

Chaining has one drawback: each node is a separate heap allocation, so walking a chain jumps around memory and gets little benefit from CPU caches. The next approach stores everything in one contiguous array and resolves collisions by probing for the next open slot.

Approach 3: Open Addressing (Linear Probing)

Intuition

Open addressing stores all entries directly in the array rather than in linked lists. On a collision (the target slot holds a different key), we check the next slot, then the next, until we find an empty one. This is linear probing.

Deletion needs care. Setting a removed key's slot back to "empty" can break a probe chain. If key A sits at index 5 and key B collided with A and landed at index 6, marking index 5 empty after removing A would make a later search for B stop at the empty slot at index 5 and never reach index 6. The fix is a tombstone marker that means "no live key here, but keep probing."

This approach needs a larger array than chaining to keep the load factor low. Linear probing stays fast while the load factor (entries divided by array size) is below about 0.7. With at most 10^4 entries, an array of size 20011 (a prime roughly double the maximum entry count) holds the load factor near 0.5.

Algorithm

  1. Create an array of size 20011, with each slot initialized to a sentinel "empty" state
  2. Define a hash function: hash(key) = key % 20011
  3. put(key, value):
    • Start at index = hash(key)
    • Probe forward until we find the key (update it), a tombstone (reuse the slot), or an empty slot (insert here)
  4. get(key):
    • Start at index = hash(key)
    • Probe forward until we find the key (return value) or an empty slot (key doesn't exist)
    • Skip over tombstones during the search
  5. remove(key):
    • Start at index = hash(key)
    • Probe forward until we find the key
    • Mark the slot as a tombstone

Example Walkthrough

To exercise probing, tombstones, and tombstone reuse, trace keys 5 and 20016, which collide because 5 % 20011 = 20016 % 20011 = 5. The visualization tracks slots 5 and 6 (every other slot stays EMPTY); each cell shows the stored key, with X for a tombstone and _ for EMPTY.

1put(5,50): hash 5 = slot 5, EMPTY. Insert key 5
[5, _]
1/6

The two read operations return 60 and 55. The tombstone at slot 5 keeps the probe path to key 20016 intact, and the later insert reuses that slot instead of leaving a permanent gap.

Code