Consistent Hashing

What's being tested

These problems test consistent hashing as a data-structure and routing algorithm: map arbitrary keys to nodes while minimizing remapping after addNode / removeNode. Interviewers expect clean APIs, deterministic hashing, sorted-ring lookup, virtual nodes, and complexity analysis.

Patterns & templates

• Sorted ring representation — store hash positions in sorted order; getNode(key) finds first position >= hash(key), wrapping to index 0.

• Binary search lookup — use bisect_left / TreeMap.ceilingEntry; getNode is O(log V) where V = nodes * virtualNodes.

• Virtual nodes — insert labels like nodeId#replicaIndex; improves distribution versus one hash point per physical node.

• addNode(node) — hash each virtual node, insert into ring/map, track ownership metadata; O(R log V) for R replicas.

• removeNode(node) — delete all virtual-node hashes for that node; maintain node -> hashes to avoid scanning the whole ring.

• Collision handling — deterministic hashes can collide; resolve with bucket lists, rehashing salt, or storing hash -> [virtualNodes].

• Weighted distribution — allocate more virtual nodes to higher-capacity servers, e.g. replicas = baseReplicas * weight.

Common pitfalls

Pitfall: Using Python’s built-in hash() for routing; it is process-randomized, so use stable hashing like md5, sha1, mmh3, or crc32.

Pitfall: Forgetting ring wraparound when bisect_left returns the end; the correct node is the first point on the ring.

Pitfall: Claiming removals are cheap without tracking each node’s virtual hashes; otherwise removeNode can degrade to scanning all virtual nodes.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.