Consistent Hashing with Virtual Buckets in Python

import random

class VirtualBuckets:
    """Maps many virtual buckets onto few physical buckets using consistent hashing."""
    
    def __init__(self, physical_buckets, virtual_factor=100):
        self.physical = list(physical_buckets)
        self.virtual_factor = virtual_factor
        self.ring = []
        self._build_ring()
    
    def _build_ring(self):
        """Create virtual buckets and distribute them across physical buckets."""
        for phys_idx, phys in enumerate(self.physical):
            for v in range(self.virtual_factor):
                # Create a deterministic pseudo-random hash for each virtual bucket
                seed = f"{phys}_{v}"
                random.seed(seed)
                hash_val = random.random()
                self.ring.append((hash_val, phys_idx))
        self.ring.sort(key=lambda x: x[0])
    
    def get_bucket(self, key):
        """Find the physical bucket for a given key using binary search."""
        # Hash the key to a position on the ring
        random.seed(key)
        key_hash = random.random()
        
        # Binary search for the first ring entry >= key_hash (circular wrap)
        lo, hi = 0, len(self.ring)
        while lo < hi:
            mid = (lo + hi) // 2
            if self.ring[mid][0] >= key_hash:
                hi = mid
            else:
                lo = mid + 1
        idx = lo % len(self.ring)
        return self.physical[self.ring[idx][1]]

# Demonstrate with a mock setup
if __name__ == "__main__":
    buckets = VirtualBuckets(["A", "B", "C"], virtual_factor=50)
    
    # Test keys
    test_keys = ["apple", "banana", "cherry", "date", "elderberry",
                 "fig", "grape", "honeydew", "kiwi", "lemon"]
    
    for key in test_keys:
        print(f"{key} -> bucket {buckets.get_bucket(key)}")
    
    # Show distribution
    distribution = {}
    for i in range(1000):
        bucket = buckets.get_bucket(f"key_{i}")
        distribution[bucket] = distribution.get(bucket, 0) + 1
    print(f"\nDistribution over 1000 keys: {distribution}")