Implementation

A hash ring with virtual nodes on Python's bisect, ported to C++, Java and TypeScript. Sharing one hash, all four agree on every key.

Python

Avoid the built-in hash(): string hashing is randomized per process. We use 64-bit FNV-1a plus MurmurHash3's fmix64 finalizer to spread similar names like node#1.

import bisect

MASK = (1 << 64) - 1


def hash64(text: str) -> int:
    x = 0xCBF29CE484222325  # FNV-1a offset basis
    for b in text.encode("utf-8"):
        x = ((x ^ b) * 0x100000001B3) & MASK
    x ^= x >> 33  # fmix64 finalizer
    x = (x * 0xFF51AFD7ED558CCD) & MASK
    x ^= x >> 33
    x = (x * 0xC4CEB9FE1A85EC53) & MASK
    return x ^ (x >> 33)


class HashRing:
    def __init__(self, vnodes: int = 100):
        self.vnodes = vnodes
        self.points: list[int] = []  # sorted positions
        self.owner: dict[int, str] = {}  # position -> node

    def add(self, node: str) -> None:
        for i in range(self.vnodes):
            p = hash64(f"{node}#{i}")
            bisect.insort(self.points, p)
            self.owner[p] = node

    def remove(self, node: str) -> None:
        for i in range(self.vnodes):
            p = hash64(f"{node}#{i}")
            del self.owner[p]
            self.points.pop(bisect.bisect_left(self.points, p))

    def get(self, key: str) -> str:
        if not self.points:
            raise LookupError("ring is empty")
        i = bisect.bisect_left(self.points, hash64(key))
        if i == len(self.points):  # wrap around
            i = 0
        return self.owner[self.points[i]]

• hash64: XOR each byte, multiply by the FNV prime, keep 64 bits with & MASK.
• points, owner: sorted positions and a position-to-node map.
• add: derives vnode positions from node#i and keeps them sorted via insort.
• remove: recomputes the same positions, so nothing per node is stored. (64-bit collisions are negligible and ignored.)
• get: bisect_left finds the first point at or after the key; past the end, wrap.

C++

std::map is sorted, so lower_bound is the clockwise search.

#include <cstdint>
#include <map>
#include <stdexcept>
#include <string>

std::uint64_t hash64(const std::string& text) {
    std::uint64_t x = 0xCBF29CE484222325ULL;
    for (unsigned char b : text) x = (x ^ b) * 0x100000001B3ULL;
    x ^= x >> 33; x *= 0xFF51AFD7ED558CCDULL;
    x ^= x >> 33; x *= 0xC4CEB9FE1A85EC53ULL;
    return x ^ (x >> 33);
}

class HashRing {
public:
    explicit HashRing(int vnodes = 100) : vnodes_(vnodes) {}
    void add(const std::string& node) {
        for (int i = 0; i < vnodes_; ++i) ring_[hash64(node + "#" + std::to_string(i))] = node;
    }
    void remove(const std::string& node) {
        for (int i = 0; i < vnodes_; ++i) ring_.erase(hash64(node + "#" + std::to_string(i)));
    }
    const std::string& get(const std::string& key) const {
        if (ring_.empty()) throw std::runtime_error("ring is empty");
        auto it = ring_.lower_bound(hash64(key));
        return (it == ring_.end() ? ring_.begin() : it)->second;
    }
private:
    int vnodes_;
    std::map<std::uint64_t, std::string> ring_;
};