前言
之前也了解到过一致性哈希算法，但是没有用go实现过，刚好最近看GeeCache，动手实现下一致性哈希算法
正文:
我们先来想下一致性哈希算法的数据结构含有哪些内容:
1.map 用来存储虚拟节点对应的真实节点，是一个映射表
2.hash 哈希函数
3.key 哈希环，存储所有虚拟节点
4.replicas 虚拟节点的倍数
了解过一致性哈希算法的朋友，应该是能够理解为什么要有上面的内容，下面我们用代码实现下:
type Hash func([]byte) uint32 type Map struct { hash Hash // hash算法 key []int // hash环 replicas int // 虚拟节点的数量 m map[int]string // 虚拟节点和真实节点的映射表 }
下面，我们实现获取节点的方法:
将key经过hash运算，在哈希环上顺时针找到第一个节点，存入
func (m *Map) Get(key string) string { hash := int(m.hash([]byte(key))) // 获取key对应的hash值 // 顺时针找到第一个虚拟节点 idx := sort.Search(len(m.key), func(i int) bool { return m.key[i] >= hash }) // 返回对应的真实节点:记得对哈希环取余 return m.m[m.key[idx % len(m.key)]] }
添加节点的方法
func (m *Map) Add(key ...string) { for _,realKey := range key{ for i := 0; i < m.replicas; i++ { // 真实节点对应的虚拟节点 hash := int(m.hash([]byte(strconv.Itoa(i)+realKey))) // 添加到换上 m.key = append(m.key,hash) // 添加到映射表上 m.m[hash] = realKey } } // 递增排序，方便顺时针查找 sort.Ints(m.key) }
以上就是一致性哈希的实现方法，也挺好理解的。记录下~
| 不骄不躁，保持学习
文章评论