第五周作业
发布于: 2020 年 10 月 25 日
1. 用你熟悉的编程语言实现一致性 hash 算法。
package consistent_hashimport ( "fmt" "hash/crc32" "sort" "sync")const ( VirtualNodesFactor = 150)type node struct { key string Data interface{}}type ConsistentHash struct { sync.RWMutex virtualNodes map[uint32]*node actNodes map[string]*node sortRing []uint32}func NewConsistentHash() *ConsistentHash { return &ConsistentHash{ virtualNodes: make(map[uint32]*node), actNodes: make(map[string]*node), sortRing: []uint32{}, }}func (c *ConsistentHash) Add(nk string, nd interface{}) bool { c.Lock() defer c.Unlock() if _, ok := c.actNodes[nk]; ok { return false } n := &node{ key: nk, Data: nd, } for i := 0; i < VirtualNodesFactor; i++ { c.virtualNodes[c.hashStr(fmt.Sprintf("%s#%d", nk, i))] = n } c.actNodes[nk] = n c.sortHashRing() return true}func (c *ConsistentHash) Get(key string) *node { hash := c.hashStr(key) c.RLock() defer c.RUnlock() if len(c.virtualNodes) == 0 { return nil } i := c.search(hash) return c.virtualNodes[c.sortRing[i]]}func (c *ConsistentHash) search(hash uint32) int { i := sort.Search(len(c.sortRing), func(i int) bool { return c.sortRing[i] >= hash }) if i < len(c.sortRing) { if i == len(c.sortRing)-1 { return 0 } else { return i } } else { return len(c.sortRing) - 1 }}func (c *ConsistentHash) Remove(key string) { c.Lock() defer c.Unlock() _, ok := c.actNodes[key] if !ok { return } delete(c.actNodes, key) for i := 0; i < VirtualNodesFactor; i++ { delete(c.virtualNodes, c.hashStr(fmt.Sprintf("%s#%d", key, i))) } c.sortHashRing()}func (c *ConsistentHash) hashStr(key string) uint32 { return crc32.ChecksumIEEE([]byte(key))}func (c *ConsistentHash) sortHashRing() { c.sortRing = []uint32{} for k := range c.virtualNodes { c.sortRing = append(c.sortRing, k) } sort.Slice(c.sortRing, func(i, j int) bool { return c.sortRing[i] < c.sortRing[j] })}
不知道是不是对题目理解有误。想完整的实现一致性哈希,但是力不从心。
划线
评论
复制
发布于: 2020 年 10 月 25 日阅读数: 24

fmouse
关注
还未添加个人签名 2018.08.07 加入
还未添加个人简介
评论