Hashes inside data structures

How hashing fills buckets, what load factor does to collisions, and why consistent and rendezvous hashing stop a cluster from reshuffling every key when a node leaves.

Buckets, collisions and load factor

A hash table turns the hash into a bucket index with a modulo or a bitmask. Two keys can land in the same bucket, so the table must resolve collisions, and the load factor decides how often that happens.

# chaining: each bucket holds a list
class HashMap:
    def __init__(self, capacity=8, load_factor=0.75):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
        self.load_factor = load_factor

    def _index(self, key):
        # bitmask works only because capacity is a power of two
        return hash(key) & (len(self.buckets) - 1)

    def put(self, key, value):
        if (self.size + 1) / len(self.buckets) > self.load_factor:
            self._resize()
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        self.size = 0
        for k, v in old:
            self.put(k, v)

Consistent hashing

Modulo arithmetic is fine for one table but catastrophic for a cluster. With hash(key) % N, changing N remaps almost every key, which invalidates every cache entry at once.

import bisect, hashlib

class Ring:
    """Consistent hash ring with virtual nodes."""
    def __init__(self, nodes, vnodes=100):
        self.points = []
        self.owner = {}
        for node in nodes:
            for i in range(vnodes):
                h = int(hashlib.sha256(f"{node}#{i}".encode()).hexdigest()[:8], 16)
                self.points.append(h)
                self.owner[h] = node
        self.points.sort()

    def node_for(self, key):
        h = int(hashlib.sha256(key.encode()).hexdigest()[:8], 16)
        i = bisect.bisect_left(self.points, h) % len(self.points)
        return self.owner[self.points[i]]

ring = Ring(["cache-a", "cache-b", "cache-c"])
for k in ("user:1", "user:2", "user:3"):
    print(k, ring.node_for(k))

• Removing one node from a ring of N moves roughly 1/N of keys, instead of all of them.
• Virtual nodes even out the load: without them, a node may own a huge or tiny arc by chance.
• The ring is a routing decision, not a security control; the hash only needs to be well distributed.
• Rendezvous hashing solves the same problem without a ring: score every node per key and take the maximum.

# rendezvous hashing: no ring, no virtual nodes
import hashlib

def pick(key, nodes):
    return max(nodes, key=lambda n: int(
        hashlib.sha256(f"{key}|{n}".encode()).hexdigest()[:16], 16))

nodes = ["cache-a", "cache-b", "cache-c"]
print(pick("user:1", nodes))

Stability across languages and runs

FAQ

Related

Cache keys, ETags and shard keys Non-cryptographic hashes: CRC32, FNV and xxHash

Last refreshed 2026-09-18.