Hash Map Design

Consistent Hashing

Distribute keys across servers arranged in a ring. Each key maps to the next server clockwise. When a server is added/removed, only keys near it are reassigned. Most keys stay put. Used in distributed systems.

O(log n) per op

O(n)

say this out loud

Adding a server should not reshuffle every key, so I hash servers and keys onto one ring and only the arc between neighbours moves.

How It Works

Consistent hashing distributes keys across servers so that adding or removing a server disturbs as few keys as possible. Both servers and keys are hashed onto a circular space (say 0 to 2³²-1); each key is owned by the first server clockwise from its position. With naive modulo hashing (hash % N), changing N remaps nearly every key; on the ring, removing a server reassigns only the keys it owned, roughly K/N of them, to its clockwise successor.

Real systems place each physical server at many virtual-node positions on the ring, which evens out load imbalance and spreads a failed server's keys across many survivors. Lookups use binary search over the sorted ring positions, costing O(log N).

Step-by-Step Visualization

Three servers, and every key must land on one of them. Positions 10, 50 and 80 on a ring of hash values

serversS2, S1, S3

1/9

Code

Java

class ConsistentHash {
  int replicas;
  TreeMap<Integer, String> ring = new TreeMap<>();

  ConsistentHash(int replicas) { this.replicas = replicas; }

  void addServer(String server) {
    for (int i = 0; i < replicas; i++) {
      int hash = (server + ":" + i).hashCode();
      ring.put(hash, server);
    }
  }

  String getServer(String key) {
    int hash = key.hashCode();
    Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
    return entry != null ? entry.getValue() : ring.firstEntry().getValue();
  }
}

Tips & Gotchas

1Arrange servers on a hash ring (0 to 2^32)

2Each key maps to the next server clockwise on the ring

3Adding/removing a server only affects keys near it

Practice Problems

1Design a URL Shortener
2Design Distributed Cache
3Random Pick with Weight

About the Hash Map Design Pattern

Some problems ask you to build data structures that combine a hash map with other structures to achieve specific performance guarantees.

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

What problem do virtual nodes solve?

With one position per server, random hashing produces uneven arc sizes, so some servers own far more keyspace than others, and a failing server dumps its entire load onto a single neighbor. Hashing each server to hundreds of ring positions smooths ownership toward uniform and spreads failover load across many machines.

How many keys move when a server joins the ring?

Only the keys falling between the new server's positions and their previous owners move, on average K/N of all K keys for N servers. That locality is the defining advantage over modulo-based sharding, where changing the server count remaps almost every key.