golang版consistent hash

package main

import (
    "errors"
    "hash/crc32"
    "sort"
    "strconv"
    "sync"
)

//声明新切片类型
type units []uint32

func (x units) Len() int {
    return len(x)
}

func (x units) Less(i, j int) bool {
    return x[i] < x[j]
}

func (x units) Swap(i, j int) {
    x[i], x[j] = x[j], x[i]
}

//当hash环上没有数据时提示错误
var errEmpty = errors.New("hash ring is empty")

//创建结构体保存一致性hash信息
type Consistent struct {
    //hash环 key为哈希值 值为存放节点的信息
    circle map[uint32]string
    //已经排序的节点hash切片
    sortedHashes units
    //虚拟节点个数，用来增加hash的平衡性
    VirtualNode int
    //多线程，并发同步
    sync.RWMutex
}

//创建一致性hash算法结构体  设置默认节点数量
func NewConsistent() *Consistent {
    return &Consistent{
        circle:      make(map[uint32]string),
        VirtualNode: 20,
    }
}

//向hash环中添加节点
func (c *Consistent) Add(element string) {
    c.Lock()
    defer c.Unlock()
    c.add(element)
}

//动态删除节点
func (c *Consistent) Remove(element string) {
    c.Lock()
    defer c.Unlock()
    c.remove(element)
}

//根据数据标识获取最近服务器节点信息 其实是返回的ip地址
func (c *Consistent) Get(name string) (string, error) {
    c.RLock()
    defer c.RUnlock()

    //如果为零则返回错误
    if len(c.circle) == 0 {
        return "", errEmpty
    }
    //计算hash值
    key := c.hashKey(name)
    //在hash环上查找最近的节点
    i := c.search(key)
    return c.circle[c.sortedHashes[i]], nil
}

//自动生成key值
//根据服务器相关信息加上index 生成服务器相关的key
func (c *Consistent) generateKey(element string, index int) string {
    //副本key生成逻辑
    r := element + "#" + strconv.Itoa(index)
    return r
}

//获取hash位置  根据传入的key获取对应的hash值
func (c *Consistent) hashKey(key string) uint32 {
    return crc32.ChecksumIEEE([]byte(key))
}

//更新排序 方便查找
func (c *Consistent) updateSortedHashes() {
    //相当于清空切片里面的内容
    hashes := c.sortedHashes[:0]
    //判断切片容量，是否过大，如果过大则重置，可能节点被删了，但切片容量没有释放
    //这个用于排序的切片的容量除以虚拟节点个数的4倍  大于 hash环上的节点数  则清空里面的值
    if cap(c.sortedHashes)/(c.VirtualNode*4) > len(c.circle) {
        hashes = nil
    }
    //添加hashs
    for k := range c.circle {
        hashes = append(hashes, k)
    }
    //对所有节点hash值进行排序
    //方便之后进行二分法查找
    sort.Sort(hashes)
    //重新赋值
    c.sortedHashes = hashes
}

//添加节点
//向hash环里面添加服务器信息
func (c *Consistent) add(element string) {
    //循环虚拟节点 设置副本
    //虚拟节点加上generateKey()里面的规则 生成虚拟节点的信息  根据虚拟节点的信息进行hash
    for i := 0; i < c.VirtualNode; i++ {
        //根据生成的虚拟节点添加到hash环中
        c.circle[c.hashKey(c.generateKey(element, i))] = element
    }
    //下面对生成以后的虚拟节点进行排序
    c.updateSortedHashes()
}

//删除节点
//需要传入服务器的信息比如是ip
func (c *Consistent) remove(element string) {
    //根据传入的服务器的信息删除所欲的副节点
    for i := 0; i < c.VirtualNode; i++ {
        delete(c.circle, c.hashKey(c.generateKey(element, i)))
    }
    //然后更新排序 方便二分法查找hash环上的节点
    c.updateSortedHashes()
}

//顺时针查找最近的节点
func (c *Consistent) search(key uint32) int {
    //查找算法
    f := func(x int) bool {
        return c.sortedHashes[x] > key
    }
    //使用“二分查找”算法来搜索指定切片满足条件的最小值
    i := sort.Search(len(c.sortedHashes), f)
    //如果超出范围则设置i=0
    if i >= len(c.sortedHashes) {
        i = 0
    }
    return i
}