Consistent Hashing

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

Code

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

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.

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

Other Hash Map Design Techniques