-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash.go
135 lines (114 loc) · 3.04 KB
/
hash.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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package hashmaps
import (
"encoding/binary"
"fmt"
"reflect"
"unsafe"
)
// HashFn is a function that returns the hash of 't'.
type HashFn[T any] func(t T) uintptr
// GetHasher returns a hasher for the golang default types.
func GetHasher[Key any]() HashFn[Key] {
var key Key
kind := reflect.ValueOf(&key).Elem().Type().Kind()
switch kind {
case reflect.Int, reflect.Uint, reflect.Uintptr:
switch unsafe.Sizeof(key) {
case 2:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashWord))
case 4:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashDword))
case 8:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashQword))
default:
panic("unsupported integer byte size")
}
case reflect.Int8, reflect.Uint8:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashByte))
case reflect.Int16, reflect.Uint16:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashWord))
case reflect.Int32, reflect.Uint32:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashDword))
case reflect.Int64, reflect.Uint64:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashQword))
case reflect.Float32:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashFloat32))
case reflect.Float64:
return *(*func(Key) uintptr)(unsafe.Pointer(&hashFloat64))
case reflect.String:
return *(*func(Key) uintptr)(unsafe.Pointer(&fnv1aModified))
default:
panic(fmt.Sprintf("unsupported key type %T of kind %v", key, kind))
}
}
var hashByte = func(in uint8) uintptr {
key := uint32(in)
key *= 0xcc9e2d51
key = (key << 15) | (key >> 17)
key *= 0x1b873593
return uintptr(key)
}
var hashWord = func(in uint16) uintptr {
key := uint32(in)
key *= 0xcc9e2d51
key = (key << 15) | (key >> 17)
key *= 0x1b873593
return uintptr(key)
}
var hashDword = func(key uint32) uintptr {
key *= 0xcc9e2d51
key = (key << 15) | (key >> 17)
key *= 0x1b873593
return uintptr(key)
}
var hashFloat32 = func(in float32) uintptr {
p := unsafe.Pointer(&in)
key := *(*uint32)(p)
key *= 0xcc9e2d51
key = (key << 15) | (key >> 17)
key *= 0x1b873593
return uintptr(key)
}
var hashFloat64 = func(in float64) uintptr {
p := unsafe.Pointer(&in)
key := *(*uint64)(p)
key ^= (key >> 33)
key *= 0xff51afd7ed558ccd
key ^= (key >> 33)
key *= 0xc4ceb9fe1a85ec53
key ^= (key >> 33)
return uintptr(key)
}
// hashQword implements MurmurHash3's 64-bit Finalizer.
var hashQword = func(key uint64) uintptr {
key ^= (key >> 33)
key *= 0xff51afd7ed558ccd
key ^= (key >> 33)
key *= 0xc4ceb9fe1a85ec53
key ^= (key >> 33)
return uintptr(key)
}
// fnv1aModified implements a simpler and faster variant of the fnv1a algorithm,
// that seems good enough for string hashing.
var fnv1aModified = func(b []byte) uintptr {
const prime64 = uint64(1099511628211)
h := uint64(14695981039346656037)
for len(b) >= 8 {
z := binary.BigEndian.Uint64(b)
b = b[8:]
h = (h ^ z) * prime64
}
if len(b) >= 4 {
z := binary.BigEndian.Uint32(b)
b = b[4:]
h = (h ^ uint64(z)) * prime64
}
if len(b) >= 2 {
h = (h ^ uint64(b[0]^b[1])) * prime64
b = b[2:]
}
if len(b) > 0 {
h = (h ^ uint64(b[0])) * prime64
}
return uintptr(h)
}