一致性哈希

常用综合题型

说明

把节点和键都映射到环上；键归属顺时针遇到的第一个节点。

分析

将节点和键的哈希值放在一个环上，从键的位置顺时针寻找第一个节点作为归属。节点增减通常只影响环上一段键，适合分布式缓存或分片。

节点位置10、100、200时，键90归属100；新增95后它转交95。移动的范围为(10,95]，其他键归属不变。映射只决定责任节点，不负责数据复制、迁移期间一致性或故障恢复。

查看图表代码

适用前提与边界

节点分布不均时会产生倾斜，实践中常为每个真实节点设置多个虚拟节点。 空节点列表返回-1；示例使用uint32减法回绕表示环上距离，多个节点哈希相同还需定义归属和冲突处理。

示例输入与调用

fmt.Println(Owner([]uint32{10, 100, 200}, 90))

运行输出

1

完整 Go 示例

package main

import "fmt"

func Owner(nodes []uint32, key uint32) int {
	if len(nodes) == 0 {
		return -1
	}
	best := -1
	var distance uint32
	for i, node := range nodes {
		d := node - key
		if best < 0 || d < distance {
			best, distance = i, d
		}
	}
	return best
}

func main() {
	fmt.Println(Owner([]uint32{10, 100, 200}, 90))
}