一致性哈希算法

template <typename T,        typename Hash,        typename Alloc = std::allocator<std::pair<const typename Hash::result_type,T > > >class consistent_hash_map

#include <map>#include <string>#include <list>#include <functional> #include <algorithm>


#ifndef __CONSISTENT_HASH_H__#define __CONSISTENT_HASH_H__


template <typename T,        typename Hash,        typename Alloc = std::allocator<std::pair<const typename Hash::result_type,T > > >class consistent_hash_map{public:     typedef typename Hash::result_type size_type;    typedef std::map<size_type,T,std::less<size_type>,Alloc> map_type;    typedef typename map_type::value_type value_type;    typedef value_type& reference;    typedef const value_type& const_reference;    typedef typename map_type::iterator iterator;    typedef typename map_type::reverse_iterator reverse_iterator;    typedef Alloc allocator_type;
public:        consistent_hash_map() {
    }
    ~consistent_hash_map() {
    }
public:    std::size_t size() const {        return nodes_.size();    }		    bool empty() const {        return nodes_.empty();    }
    std::pair<iterator,bool> insert(const T& node) {        size_type hash = hasher_(node);        return nodes_.insert(value_type(hash,node));    }

    void erase(iterator it) {        nodes_.erase(it);    }

    std::size_t erase(const T& node) {        size_type hash = hasher_(node);        return nodes_.erase(hash);    }
    iterator find(size_type hash) {        if(nodes_.empty()) {            return nodes_.end();        }
        iterator it = nodes_.lower_bound(hash);
        if (it == nodes_.end()) {            it = nodes_.begin();        }
        return it;    }
    iterator begin() { return nodes_.begin(); }    iterator end() { return nodes_.end(); }    reverse_iterator rbegin() { return nodes_.rbegin(); }    reverse_iterator rend() { return nodes_.rend(); }

private:
    Hash hasher_;    map_type nodes_;};

#endif

#include <stdint.h>#include <iostream>#include <string>#include <boost/functional/hash.hpp>#include <boost/format.hpp>#include <boost/crc.hpp>
#include "consistent_hash.hpp"
//所有主机列表const char* nodes[] = {    "192.168.1.100",    "192.168.1.101",    "192.168.1.102",    "192.168.1.103",    "192.168.1.104"};
//虚拟节点struct vnode_t {    vnode_t() {}    vnode_t(std::size_t n,std::size_t v):node_id(n),vnode_id(v) {}
    std::string to_str() const {        return boost::str(boost::format("%1%-%2%") % nodes[node_id] % vnode_id);    }
    std::size_t node_id;//主机ID,主机在主机列表中的索引    std::size_t vnode_id;//虚拟节点ID
};
//hasher,使用CRC32作为hash算法，注意需要定义result_typestruct crc32_hasher {    uint32_t operator()(const vnode_t& node) {        boost::crc_32_type ret;        std::string vnode = node.to_str();        std::cout<<"vnode:"<<vnode<<std::endl;        ret.process_bytes(vnode.c_str(),vnode.size());        return ret.checksum();    }    typedef uint32_t result_type;};
int main(int argc, char const *argv[]){    typedef consistent_hash_map<vnode_t,crc32_hasher> consistent_hash_t;    consistent_hash_t consistent_hash_;
    //为每个主机生成150个虚拟节点，然后加入consistent_hash_map中    for(std::size_t i=0;i<5;++i) {        for(std::size_t j=0;j<150;j++) {            consistent_hash_.insert(vnode_t(i,j));        }    }
    //遍历consistent_hash中的所有的vnode,统计每个虚拟节点的key的数量和每个主机包含key的数量：    std::cout<<"========================================================="<<std::endl;    std::size_t sums[] = {0,0,0,0,0};    consistent_hash_t::iterator i = consistent_hash_.begin(); //第一个节点    consistent_hash_t::reverse_iterator j = consistent_hash_.rbegin(); //最后一个节点    std::size_t n = i->first + UINT32_MAX - j->first; //计算第一个节点包含的key的数量    std::cout<<boost::format("vnode:%1%,hash:%2%,contains:%3%")             % i->second.to_str() % i->first % n << std::endl;    sums[i->second.node_id] += n; //更新主机包含的key数量。
    //计算剩余所有节点包含的key的数量,并更新主机包括的key的数量。    uint32_t priv = i->first;    uint32_t cur;    consistent_hash_t::iterator end = consistent_hash_.end();    while(++i != end) {        cur = i->first;        n = cur - priv;        std::cout<<boost::format("vnode:%1%,hash:%2%,contains:%3%")             % i->second.to_str() % cur % n << std::endl;        sums[i->second.node_id] += n;        priv = cur;    }            for(std::size_t i=0;i<5;++i) {        std::cout<<boost::format("node:%1% contains:%2%") % nodes[i] % sums[i] <<std::endl;     }        //查找某个hash值对应的vnode和主机    consistent_hash_t::iterator it;    it = consistent_hash_.find(290235110);    //it -> first是该节点的hash值，it -> second是该虚拟节点    std::cout<<boost::format("node:%1%,vnode:%2%,hash:%3%")                 % nodes[it->second.node_id] % it->second.vnode_id % it->first << std::endl;
    return 0;}