一致性哈希四算法实现（Ring Hash / Ketama / Maglev / Jump Hash）

package ringhash

import (
	"crypto/md5"
	"encoding/binary"
	"sort"
	"strconv"
)

// ConsistentHash 一致性哈希主结构体
type ConsistentHash struct {
	replicas int               // 每台真实机器派生出的虚拟节点（分身）数量
	ring     []uint32          // 哈希环：所有分身的数字位置，从小到大排序
	hashMap  map[uint32]string // 分身数字 → 真实机器名
}

func New(replicas int) *ConsistentHash {
	return &ConsistentHash{
		replicas: replicas,
		hashMap:  make(map[uint32]string),
	}
}

// hashText 把任意文字算成一个 0~42 亿之间的固定数字
func (ch *ConsistentHash) hashText(text string) uint32 {
	sum := md5.Sum([]byte(text))
	return binary.BigEndian.Uint32(sum[:4])
}

// AddNode 往环里添加一台机器（扩容）
func (ch *ConsistentHash) AddNode(node string) {
	for i := 0; i < ch.replicas; i++ {
		// 分身命名："机器A-0", "机器A-1" ...
		hash := ch.hashText(node + "-" + strconv.Itoa(i))
		ch.ring = append(ch.ring, hash)
		ch.hashMap[hash] = node
	}
	// 环上的数字必须始终从小到大有序，像钟表刻度
	sort.Slice(ch.ring, func(i, j int) bool { return ch.ring[i] < ch.ring[j] })
}

// GetNode 替数据顺时针找机器
func (ch *ConsistentHash) GetNode(key string) string {
	if len(ch.ring) == 0 {
		return ""
	}
	hash := ch.hashText(key)
	// 二分找第一个 >= hash 的分身
	idx := sort.Search(len(ch.ring), func(i int) bool { return ch.ring[i] >= hash })
	if idx == len(ch.ring) {
		idx = 0 // 走完一圈没找到就环回起点
	}
	return ch.hashMap[ch.ring[idx]]
}

// RemoveNode 从环里移除一台机器（缩容/宕机）
func (ch *ConsistentHash) RemoveNode(node string) {
	// 1. 先把这台机器所有分身从映射表删掉
	for i := 0; i < ch.replicas; i++ {
		delete(ch.hashMap, ch.hashText(node+"-"+strconv.Itoa(i)))
	}
	// 2. 再把已经查不到归属的分身从环里剔除；原本有序，剔除后依然有序，无需重排
	kept := ch.ring[:0]
	for _, hash := range ch.ring {
		if _, ok := ch.hashMap[hash]; ok {
			kept = append(kept, hash)
		}
	}
	ch.ring = kept
}

package ketama

import (
	"crypto/md5"
	"sort"
	"strconv"
)

// KetamaNode 哈希环上的一个虚拟节点刻度
type KetamaNode struct {
	HashVal  uint32 // 在环上的数字位置
	RealNode string // 对应的真实机器名
}

type KetamaRing struct {
	ring []KetamaNode // 严格有序的虚拟节点环
}

func New(nodes []string) *KetamaRing {
	kr := &KetamaRing{}
	for _, node := range nodes {
		kr.AddNode(node)
	}
	return kr
}

// AddNode 严格按 Ketama 标准配方添加机器：40 轮 × 每轮 4 个分身 = 160 个 vnode
func (kr *KetamaRing) AddNode(node string) {
	for i := 0; i < 40; i++ {
		// 固定命名规则：机器名-轮次
		sum := md5.Sum([]byte(node + "-" + strconv.Itoa(i)))
		// 一份 16 字节 MD5 切成 4 组，每组 4 字节小端拼成一个 uint32 → 一次产 4 个分身
		for k := 0; k < 4; k++ {
			hashVal := uint32(sum[k*4+3])<<24 |
				uint32(sum[k*4+2])<<16 |
				uint32(sum[k*4+1])<<8 |
				uint32(sum[k*4])
			kr.ring = append(kr.ring, KetamaNode{HashVal: hashVal, RealNode: node})
		}
	}
	// 严格按数字从小到大排序
	sort.Slice(kr.ring, func(i, j int) bool { return kr.ring[i].HashVal < kr.ring[j].HashVal })
}

// GetNode 数据同样用 MD5 定位，二分顺时针撞机器
func (kr *KetamaRing) GetNode(key string) string {
	if len(kr.ring) == 0 {
		return ""
	}
	sum := md5.Sum([]byte(key))
	hashVal := uint32(sum[3])<<24 | uint32(sum[2])<<16 | uint32(sum[1])<<8 | uint32(sum[0])
	idx := sort.Search(len(kr.ring), func(i int) bool { return kr.ring[i].HashVal >= hashVal })
	if idx == len(kr.ring) {
		idx = 0 // 环回起点
	}
	return kr.ring[idx].RealNode
}

package maglev

import (
	"crypto/md5"
	"encoding/binary"
)

type Maglev struct {
	nodes       []string // 真实机器列表
	m           int      // 查找表大小，必须是质数（测试用 7，Google 生产用 65537）
	lookupTable []int    // 核心查找表：table[i] = 机器在 nodes 里的下标
}

func New(nodes []string, m int) *Maglev {
	mag := &Maglev{nodes: nodes, m: m, lookupTable: make([]int, m)}
	mag.populate()
	return mag
}

// hashText 把文字切成两个不同的 64 位大整数，决定它的"抓阄偏好"
func (mag *Maglev) hashText(text string) (uint64, uint64) {
	sum := md5.Sum([]byte(text))
	return binary.BigEndian.Uint64(sum[:8]), binary.BigEndian.Uint64(sum[8:])
}

// populate 核心：让每台机器轮流"抓阄"，填满整张查找表
func (mag *Maglev) populate() {
	n := len(mag.nodes)
	if n == 0 {
		return
	}
	// 1. 全部座位先置空（-1）
	for i := range mag.lookupTable {
		mag.lookupTable[i] = -1
	}
	// 2. 为每台机器算出它的"选座偏好序列"（长度 m 的一个排列）
	permutation := make([][]int, n)
	for i, node := range mag.nodes {
		h1, h2 := mag.hashText(node)
		offset := int(h1 % uint64(mag.m))
		skip := int(h2%uint64(mag.m-1)) + 1 // ∈ [1, m-1]，与素数 m 互素
		permutation[i] = make([]int, mag.m)
		for j := 0; j < mag.m; j++ {
			permutation[i][j] = (offset + j*skip) % mag.m
		}
	}
	// 3. 轮流抓阄：机器 0、1、2… 各占一个空座，直到 m 个座位全满
	next := make([]int, n) // 每台机器看到自己偏好序列的第几个了
	count := 0
	for {
		for i := 0; i < n; i++ {
			// 顺着偏好序列找它此刻最想要且还空着的座
			bucket := permutation[i][next[i]]
			for mag.lookupTable[bucket] != -1 {
				next[i]++
				bucket = permutation[i][next[i]]
			}
			mag.lookupTable[bucket] = i
			next[i]++
			count++
			if count == mag.m {
				return
			}
		}
	}
}

// Lookup 一次取模 + 数组访问，O(1)
func (mag *Maglev) Lookup(key string) string {
	if len(mag.nodes) == 0 {
		return ""
	}
	h1, _ := mag.hashText(key)
	return mag.nodes[mag.lookupTable[h1%uint64(mag.m)]]
}

package jumphash

import (
	"crypto/md5"
	"encoding/binary"
)

// HashKey 把任意文字变成一个 64 位大整数，喂给 Jump Hash
func HashKey(text string) uint64 {
	sum := md5.Sum([]byte(text))
	return binary.BigEndian.Uint64(sum[:8])
}

// JumpHash 跳跃一致性哈希：给定 key 和桶数，纯算术直接算出桶号 [0, numBuckets)
// 论文核心逻辑仅几行，零内存、无任何表
func JumpHash(key uint64, numBuckets int) int {
	if numBuckets <= 1 {
		return 0 // 只有 1 个或没有桶，只能落到第 0 个
	}
	var b, j int64 = -1, 0 // b=上一次成功跳到的桶；j=尝试跳向的新桶
	for j < int64(numBuckets) {
		b = j
		// 线性同余，用 key 自身推出下一个伪随机数
		key = key*2862933555777941757 + 1
		// 桶越多（j 越大）跳过去的概率越小（严格符合 1/j），期望 O(log N) 次
		j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
	}
	// j 越界说明这次没跳过去，返回最后一次成功跳到的桶 b
	return int(b)
}