一致性哈希算法（C++11實現(xiàn)）

#include <iostream>
#include <string>
#include <stdint.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <cmath>
#include <set>
#include <initializer_list>
#include <vector>
#include <algorithm>
//定義哈希反函數(shù)對象
template<typename K, typename V> class Hash;
//虛擬節(jié)點
template<typename N> class VNode;
//哈希仿函數(shù)對象,v為std::string, 映射為uint32_t
template<>
class Hash<std::string, uint32_t> {
public:
    uint32_t operator()(const std::string & key) const {
        int p = 16777619;
        uint32_t hash = 2166136261L;
        for (int i = 0, num = key.size(); i < num; ++i) {
            hash = (hash ^ key[i]) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if (hash < 0) {
            hash = abs((long)hash);
        }
        return hash;
    }
};
//哈希環(huán)算法對象，內(nèi)部可調(diào)用不同哈希算法將node映射到uint32_t
template<typename V>
class HashRingAlgorithm {
public:
    HashRingAlgorithm() {}
    virtual ~HashRingAlgorithm() {}
public:
    uint32_t hash(const V & v) const {
        Hash<V, uint32_t> h;
        return h(v);
    }
};

/*
 * 虛擬節(jié)點,模板參數(shù)N為server真實節(jié)點
*/
template<typename N>
class VNode {
public:
    VNode() {};//just make compiler happy
    VNode(const N & n, uint32_t idx) {
        key_ = std::string(n) + "#" + std::to_string(idx);
        rnode_ = n;
    };

    virtual ~VNode() {

    };

    operator std::string() const {
        return key_;
    }

    N getRNode() const {
        return rnode_;
    }
private:
    std::string key_;
    N rnode_;//真實節(jié)點
};


/*
 * 一致性哈希環(huán)對象，頂層對象,N為Server類，K為映射key如std::string
*/
template<typename N, typename K>
class ConsitentHashRing {
public:
    ConsitentHashRing(uint32_t vn_count = 1000) {
        vn_count_ = vn_count;
    }

    virtual ~ConsitentHashRing() {
        vnodes_map_.clear();
    }
public:
    void addNode(const N & n) {
        for (uint32_t i = 0; i < vn_count_; i++) {
            VNode<N> vnode(n, i);
            uint32_t hash = hash_algorithm_.hash(vnode);
            vnodes_map_[hash] = vnode;
            real_nodes_.push_back(n);
        }
    }

    N  getNode(const K & v) const {
        uint32_t hash = hash_algorithm_.hash(v);
        auto it = vnodes_map_.lower_bound(hash);
        if (it == vnodes_map_.end()) {
            return vnodes_map_.begin()->second.getRNode();
        }
        return it->second.getRNode();
    }

    int removeNode(const N & n) {
        for (auto it = vnodes_map_.begin(); it != vnodes_map_.end();) {
            if (it->second.getRNode() == n) {
                vnodes_map_.erase(it++);
            }
            else {
                it++;
            }
        }

        for (auto it = real_nodes_.begin(); it != real_nodes_.end(); it++) {
            if (*it == n) {
                real_nodes_.erase(it);
                break;
            }
        }
        return 0;
    }

private:
    uint32_t vn_count_;
    std::map<uint32_t, VNode<N>> vnodes_map_;
    std::vector<N> real_nodes_;
    HashRingAlgorithm<K> hash_algorithm_;
};

class ServerNode {
public:
    ServerNode() {};
    ServerNode(const std::string & host, uint16_t port) {
        host_ = host;
        port_ = port;
    }
    virtual ~ServerNode() {}
        //removeNode時，需要比較，所以需要實現(xiàn)operator==
    bool operator==(const ServerNode & s) const {
        if (s.host_ == host_ && s.port_ == port_) {
            return true;
        }
        return false;
    }
        //哈希映射時，目前使用std::string作為參數(shù)，所以需要隱式轉(zhuǎn)換
    operator std::string() const {
        return host_ + ":" + std::to_string(port_);
    }
public:
    std::string host_;
    uint16_t port_;
};

int main(char argc, char *argv[]) {
        //初始化測試
    ConsitentHashRing<ServerNode, std::string> hash_ring;
    hash_ring.addNode(ServerNode("192.168.128.1", 1935));
    hash_ring.addNode(ServerNode("192.168.128.2", 1935));
    hash_ring.addNode(ServerNode("192.168.128.3", 1935));
    hash_ring.addNode(ServerNode("192.168.128.4", 1935));
    hash_ring.addNode(ServerNode("192.168.128.5", 1935));
    hash_ring.addNode(ServerNode("192.168.128.6", 1935));
    hash_ring.addNode(ServerNode("192.168.128.7", 1935));
    hash_ring.addNode(ServerNode("192.168.128.8", 1935));
    hash_ring.addNode(ServerNode("192.168.128.9", 1935));

    int count[10] = { 0 };
    for (int i = 0; i < 10000; i++) {
        int m = rand() % 1000000;
        auto s = hash_ring.getNode(std::to_string(m));
        std::cout << std::string(s) << std::endl;
        if (s.host_ == "192.168.128.1") {
            count[0]++;
        }
        else if (s.host_ == "192.168.128.2") {
            count[1]++;
        }
        else if (s.host_ == "192.168.128.3") {
            count[2]++;
        }
        else if (s.host_ == "192.168.128.4") {
            count[3]++;
        }
        else if (s.host_ == "192.168.128.5") {
            count[4]++;
        }
        else if (s.host_ == "192.168.128.6") {
            count[5]++;
        }
        else if (s.host_ == "192.168.128.7") {
            count[6]++;
        }
        else if (s.host_ == "192.168.128.8") {
            count[7]++;
        }
        else if (s.host_ == "192.168.128.9") {
            count[8]++;
        }
        else if (s.host_ == "192.168.128.10") {
            count[9]++;
        }
    }
    for (int i = 0; i < 10; i++) {
        std::cout << "count[" << i << "] = " << count[i] << std::endl;
        count[i] = 0;
    }
    getchar();
        //添加一個節(jié)點測試
    hash_ring.addNode(ServerNode("192.168.128.10", 1935));
    for (int i = 0; i < 10000; i++) {
        int m = rand() % 1000000;
        auto s = hash_ring.getNode(std::to_string(m));
        std::cout << std::string(s) << std::endl;
        if (s.host_ == "192.168.128.1") {
            count[0]++;
        }
        else if (s.host_ == "192.168.128.2") {
            count[1]++;
        }
        else if (s.host_ == "192.168.128.3") {
            count[2]++;
        }
        else if (s.host_ == "192.168.128.4") {
            count[3]++;
        }
        else if (s.host_ == "192.168.128.5") {
            count[4]++;
        }
        else if (s.host_ == "192.168.128.6") {
            count[5]++;
        }
        else if (s.host_ == "192.168.128.7") {
            count[6]++;
        }
        else if (s.host_ == "192.168.128.8") {
            count[7]++;
        }
        else if (s.host_ == "192.168.128.9") {
            count[8]++;
        }
        else if (s.host_ == "192.168.128.10") {
            count[9]++;
        }
    }
    for (int i = 0; i < 10; i++) {
        std::cout << "count[" << i << "] = " << count[i] << std::endl;
        count[i] = 0;
    }

    getchar();
        //刪除一個節(jié)點測試
    hash_ring.removeNode(ServerNode("192.168.128.10", 1935));
    for (int i = 0; i < 10000; i++) {
        int m = rand() % 1000000;
        auto s = hash_ring.getNode(std::to_string(m));
        std::cout << std::string(s) << std::endl;
        if (s.host_ == "192.168.128.1") {
            count[0]++;
        }
        else if (s.host_ == "192.168.128.2") {
            count[1]++;
        }
        else if (s.host_ == "192.168.128.3") {
            count[2]++;
        }
        else if (s.host_ == "192.168.128.4") {
            count[3]++;
        }
        else if (s.host_ == "192.168.128.5") {
            count[4]++;
        }
        else if (s.host_ == "192.168.128.6") {
            count[5]++;
        }
        else if (s.host_ == "192.168.128.7") {
            count[6]++;
        }
        else if (s.host_ == "192.168.128.8") {
            count[7]++;
        }
        else if (s.host_ == "192.168.128.9") {
            count[8]++;
        }
        else if (s.host_ == "192.168.128.10") {
            count[9]++;
        }
    }
    for (int i = 0; i < 10; i++) {
        std::cout << "count[" << i << "] = " << count[i] << std::endl;
    }
    return 0;
}

測試結(jié)果（0-9對應(yīng)9個服務(wù)器）：
初始化測試：
count[0] = 1135
count[1] = 1248
count[2] = 1133
count[3] = 1096
count[4] = 1119
count[5] = 1057
count[6] = 992
count[7] = 1155
count[8] = 1065
count[9] = 0
添加一個節(jié)點測試：
count[0] = 1012
count[1] = 1061
count[2] = 969
count[3] = 987
count[4] = 1060
count[5] = 986
count[6] = 943
count[7] = 997
count[8] = 974
count[9] = 1011
刪除一個節(jié)點測試：
count[0] = 1097
count[1] = 1208
count[2] = 1112
count[3] = 1101
count[4] = 1103
count[5] = 1093
count[6] = 1053
count[7] = 1159
count[8] = 1074
count[9] = 0
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容