consistent_hashing.cpp

/**
 * Consistent hashing ring: keys map to first virtual node >= hash on a sorted ring.
 * Simplified: uint32_t ring, std::map for ordered nodes.
 */
#include <cstdint>
#include <iostream>
#include <map>
#include <string>
#include <vector>

class ConsistentHashRing {
    std::map<std::uint32_t, std::string> ring_;  // position -> physical node id

    static std::uint32_t hashKey(const std::string& s) {
        std::uint32_t h = 2166136261u;
        for (unsigned char c : s) {
            h ^= c;
            h *= 16777619u;
        }
        return h;
    }

public:
    void addNode(const std::string& nodeId, int virtualReplicas) {
        for (int i = 0; i < virtualReplicas; ++i) {
            std::uint32_t p = hashKey(nodeId + "#" + std::to_string(i));
            ring_[p] = nodeId;
        }
    }

    void removeNode(const std::string& nodeId, int virtualReplicas) {
        for (int i = 0; i < virtualReplicas; ++i) {
            std::uint32_t p = hashKey(nodeId + "#" + std::to_string(i));
            ring_.erase(p);
        }
    }

    std::string routeKey(const std::string& key) const {
        if (ring_.empty()) return {};
        std::uint32_t p = hashKey(key);
        auto it = ring_.lower_bound(p);
        if (it == ring_.end()) it = ring_.begin();
        return it->second;
    }
};

int main() {
    ConsistentHashRing ring;
    const int v = 50;
    ring.addNode("node-A", v);
    ring.addNode("node-B", v);
    ring.addNode("node-C", v);

    std::vector<std::string> keys = {"user:1", "user:2", "cache:session:42", "shard:7"};
    for (const auto& k : keys) {
        std::cout << k << " -> " << ring.routeKey(k) << "\n";
    }

    std::cout << "\nAfter removing node-B:\n";
    ring.removeNode("node-B", v);
    for (const auto& k : keys) {
        std::cout << k << " -> " << ring.routeKey(k) << "\n";
    }
    return 0;
}