import hashlib
import bisect
from typing import List, Dict, Optional

class ConsistentHash:
    def __init__(self, nodes: List[str] = None, replicas: int = 150):
        """
        replicas: number of virtual nodes per physical node
        More virtual nodes = more even distribution
        """
        self.replicas = replicas
        self.ring: Dict[int, str] = {}  # hash → node name
        self.sorted_keys: List[int] = []  # Sorted hash positions

        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str) -> None:
        """Add a physical node with N virtual nodes"""
        for i in range(self.replicas):
            virtual_node_key = f"{node}:replica_{i}"
            hash_val = self._hash(virtual_node_key)
            self.ring[hash_val] = node
            bisect.insort(self.sorted_keys, hash_val)

    def remove_node(self, node: str) -> None:
        """Remove a physical node and all its virtual nodes"""
        for i in range(self.replicas):
            virtual_node_key = f"{node}:replica_{i}"
            hash_val = self._hash(virtual_node_key)
            if hash_val in self.ring:
                del self.ring[hash_val]
                self.sorted_keys.remove(hash_val)

    def get_node(self, key: str) -> Optional[str]:
        """Get the responsible node for a key"""
        if not self.ring:
            return None

        hash_val = self._hash(key)

        # Find the first node clockwise from this key's position
        idx = bisect.bisect(self.sorted_keys, hash_val)

        # Wrap around the ring
        if idx == len(self.sorted_keys):
            idx = 0

        return self.ring[self.sorted_keys[idx]]
Consistent Hashing

Consistent Hashing

Consistent Hashing
