1
package consistenthash
2

3
import (
4
  "fmt"
5
  "sort"
6
  "sync"
7
)
8

9
// HashRing 一致性哈希环
10
type HashRing struct {
11
  mu       sync.RWMutex
12
  replicas int            // 每个物理节点的虚拟节点数
13
  keys     []int          // 排序的哈希值（虚拟节点）
14
  hashMap  map[int]string // 虚拟节点哈希 → 物理节点名
15
}
16

17
// fnv1a FNV-1a 哈希函数
18
func fnv1a(s string) int {
19
  h := 2166136261
20
  for i := 0; i < len(s); i++ {
21
    h ^= int(s[i])
22
    h *= 16777619
23
  }
24
  if h < 0 {
25
    h = -h
26
  }
27
  return h
28
}
29

30
func NewHashRing(replicas int) *HashRing {
31
  return &HashRing{
32
    replicas: replicas,
33
    hashMap:  make(map[int]string),
34
  }
35
}
36

37
// AddNode 添加物理节点（含虚拟节点）
38
func (r *HashRing) AddNode(node string) {
39
  r.mu.Lock()
40
  defer r.mu.Unlock()
41

42
  for i := 0; i < r.replicas; i++ {
43
    h := fnv1a(fmt.Sprintf("%s:%d", node, i))
44
    r.hashMap[h] = node
45
    r.keys = append(r.keys, h)
46
  }
47
  sort.Ints(r.keys) // 保持有序以支持二分查找
48
}
49

50
// RemoveNode 移除物理节点（含虚拟节点）
51
func (r *HashRing) RemoveNode(node string) {
52
  r.mu.Lock()
53
  defer r.mu.Unlock()
54

55
  // 删除该节点的所有虚拟节点
56
  for i := 0; i < r.replicas; i++ {
57
    h := fnv1a(fmt.Sprintf("%s:%d", node, i))
58
    delete(r.hashMap, h)
59
  }
60
  // 重建排序键，移除已删除的虚拟节点
61
  r.keys = r.keys[:0]
62
  for k := range r.hashMap {
63
    r.keys = append(r.keys, k)
64
  }
65
  sort.Ints(r.keys)
66
}
67

68
// GetNode 查找键所属的物理节点
69
func (r *HashRing) GetNode(key string) string {
70
  r.mu.RLock()
71
  defer r.mu.RUnlock()
72

73
  if len(r.keys) == 0 {
74
    return ""
75
  }
76

77
  h := fnv1a(key)
78
  // 二分查找：第一个 >= h 的位置
79
  idx := sort.SearchInts(r.keys, h)
80
  if idx >= len(r.keys) {
81
    idx = 0 // 绕回环首
82
  }
83
  return r.hashMap[r.keys[idx]]
84
}

1
class HashRing {
2
  private ring = new Map<number, string>();
3
  private sortedKeys: number[] = [];
4

5
  constructor(private replicas = 100) {}
6

7
  /** FNV-1a 哈希 */
8
  private hash(key: string): number {
9
    let h = 2166136261;
10
    for (let i = 0; i < key.length; i++) {
11
      h ^= key.charCodeAt(i);
12
      h = Math.imul(h, 16777619);
13
    }
14
    return h >>> 0; // 无符号右移，确保非负
15
  }
16

17
  /** 添加节点（含虚拟节点） */
18
  addNode(node: string): void {
19
    for (let i = 0; i < this.replicas; i++) {
20
      const h = this.hash(`${node}:${i}`);
21
      this.ring.set(h, node);
22
      this.sortedKeys.push(h);
23
    }
24
    this.sortedKeys.sort((a, b) => a - b);
25
  }
26

27
  /** 移除节点（含虚拟节点） */
28
  removeNode(node: string): void {
29
    for (let i = 0; i < this.replicas; i++) {
30
      this.ring.delete(this.hash(`${node}:${i}`));
31
    }
32
    this.sortedKeys = this.sortedKeys.filter((k) => this.ring.has(k));
33
  }
34

35
  /** 查找键所属节点 */
36
  getNode(key: string): string | undefined {
37
    if (this.sortedKeys.length === 0) return undefined;
38

39
    const h = this.hash(key);
40
    // 二分查找第一个 >= h 的位置
41
    let lo = 0, hi = this.sortedKeys.length;
42
    while (lo < hi) {
43
      const mid = (lo + hi) >>> 1;
44
      if (this.sortedKeys[mid] < h) lo = mid + 1;
45
      else hi = mid;
46
    }
47
    // 绕回环首
48
    if (lo >= this.sortedKeys.length) lo = 0;
49
    return this.ring.get(this.sortedKeys[lo]);
50
  }
51
}