前言
之前也了解到過一致性哈希演算法，但是沒有用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) }
以上就是一致性哈希的實作方法，也挺好理解的，記錄下~
| 不驕不躁，保持學習
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/501066.html
標籤：其他