golang 实现一致性 hash 算法

package JiKe
import (
	"errors"
	"hash/crc32"
	"sort"
	"strconv"
	"sync"
)
type Consistent struct {
	//排序的hash虚拟结点
	hashSortedNodes []uint32
	//虚拟结点对应的结点信息
	circle map[uint32]string
	//已绑定的结点
	nodes map[string]bool
	//map读写锁
	sync.RWMutex
	//虚拟结点数
	virtualNodeCount int
}
func (c *Consistent) hashKey(key string) uint32 {
	return crc32.ChecksumIEEE([]byte(key))
}
func (c *Consistent) Add(node string, virtualNodeCount int) error {
	if node == "" {
		return nil
	}
	c.Lock()
	defer c.Unlock()
	if c.circle == nil {
		c.circle = map[uint32]string{}
	}
	if c.nodes == nil {
		c.nodes = map[string]bool{}
	}
	if _, ok := c.nodes[node]; ok {
		return errors.New("node already existed")
	}
	c.nodes[node] = true
	//增加虚拟结点
	for i := 0; i < virtualNodeCount; i++ {
		virtualKey := c.hashKey(node + strconv.Itoa(i))
		c.circle[virtualKey] = node
		c.hashSortedNodes = append(c.hashSortedNodes, virtualKey)
	}
	//虚拟结点排序
	sort.Slice(c.hashSortedNodes, func(i, j int) bool {
		return c.hashSortedNodes[i] < c.hashSortedNodes[j]
	})
	return nil
}
func (c *Consistent) GetNode(key string) string {
	c.RLock()
	defer c.RUnlock()
	hash := c.hashKey(key)
	i := c.getPosition(hash)
	return c.circle[c.hashSortedNodes[i]]
}
func (c *Consistent) getPosition(hash uint32) int {
	i := sort.Search(len(c.hashSortedNodes), func(i int) bool { return c.hashSortedNodes[i] >= hash })
	if i < len(c.hashSortedNodes) {
		if i == len(c.hashSortedNodes)-1 {
			return 0
		} else {
			return i
		}
	} else {
		return len(c.hashSortedNodes) - 1
	}
}

package JiKe
import (
	"fmt"
	"math"
	"sort"
	"strconv"
	"testing"
)
func Test_ConsistentHash(t *testing.T) {
	virtualNodeList := []int{100, 150, 200}
  //测试10台服务器
	nodeNum := 10
  //测试数据量100W
	testCount := 1000000
	for _, virtualNode := range virtualNodeList {
		consistentHash := &Consistent{}
		distributeMap := make(map[string]int64)
		for i := 1; i <= nodeNum; i++ {
			serverName := "172.17.0." + strconv.Itoa(i)
			consistentHash.Add(serverName, virtualNode)
			distributeMap[serverName] = 0
		}
		//测试100W个数据分布
		for i := 0; i < testCount; i++ {
			testName := "testName"
			serverName := consistentHash.GetNode(testName + strconv.Itoa(i))
			distributeMap[serverName] = distributeMap[serverName] + 1
		}
		var keys []string
		var values []float64
		for k, v := range distributeMap {
			keys = append(keys, k)
			values = append(values, float64(v))
		}
		sort.Strings(keys)
		fmt.Printf("####测试%d个结点,一个结点有%d个虚拟结点,%d条测试数据\n", nodeNum, virtualNode, testCount)
		for _, k := range keys {
			fmt.Printf("服务器地址:%s 分布数据数:%d\n", k, distributeMap[k])
		}
		fmt.Printf("标准差:%f\n\n", getStandardDeviation(values))
	}
}
//获取标准差
func getStandardDeviation(list []float64) float64 {
	var total float64
	for _, item := range list {
		total += item
	}
	//平均值
	avg := total / float64(len(list))
	var dTotal float64
	for _, value := range list {
		dValue := value - avg
		dTotal += dValue * dValue
	}
	return math.Sqrt(dTotal / avg)
}