-
Notifications
You must be signed in to change notification settings - Fork 0
/
consistenthash.go
64 lines (52 loc) · 1.07 KB
/
consistenthash.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package consistenthash
import (
"hash/crc32"
"sort"
"strconv"
)
// Hash maps bytes to uint32.
type Hash func(data []byte) uint32
// Map contains all hashed keys.
type Map struct {
hash Hash
replicas int
keys []int // Sorted
hashes map[int]string
}
// New creates a Map instance
func New(replicas int, fn Hash) *Map {
if fn == nil {
fn = crc32.ChecksumIEEE
}
m := &Map{
replicas: replicas,
hash: fn,
hashes: make(map[int]string),
}
return m
}
// Add adds some keys to the hash.
func (m *Map) Add(keys ...string) {
for _, k := range keys {
for i := 0; i < m.replicas; i++ {
hash := int(m.hash([]byte(k + strconv.Itoa(i))))
m.keys = append(m.keys, hash)
m.hashes[hash] = k
}
}
sort.Ints(m.keys)
}
// Get gets the closest item in the hash to the provided key.
func (m *Map) Get(key string) string {
if len(m.keys) == 0 {
return ""
}
h := int(m.hash([]byte(key)))
// Binary search for appropriate replica.
i := sort.Search(len(m.keys),
func(i int) bool {
return m.keys[i] >= h
},
)
return m.hashes[m.keys[i%len(m.keys)]]
}