-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash_map.go
90 lines (75 loc) · 1.66 KB
/
hash_map.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
package grokking_algorithms
import (
"crypto/sha1"
"encoding/binary"
)
type HashMap interface {
Set(string, string)
Get(string) (string, bool)
}
func NewHashMap() HashMap {
return &hashMap{size: 0, len: 10, slice: make([]*keyValue, 10, 10)}
}
type hashMap struct {
size int
len uint64
slice []*keyValue
}
func (h *hashMap) Set(key, value string) {
h.size++
h.addKeyValue(key, value)
if h.mapOverflow() {
h.increaseMapLen()
}
}
func (h *hashMap) mapOverflow() bool {
return float32(h.size)/float32(len(h.slice)) >= 0.7
}
func (h *hashMap) increaseMapLen() {
h.len = uint64(len(h.slice) * 2)
oldSlice := h.slice
h.slice = make([]*keyValue, h.len, h.len)
for _, kv := range oldSlice {
for kv != nil {
h.addKeyValue(kv.key, kv.value)
kv = kv.next
}
}
}
func (h *hashMap) addKeyValue(key string, value string) {
index := h.getKeyIndex(key)
if kv := h.slice[index]; kv == nil {
h.slice[index] = &keyValue{key: key, value: value}
} else {
kv.add(key, value)
}
}
func (h *hashMap) Get(key string) (string, bool) {
index := h.getKeyIndex(key)
return h.slice[index].find(key)
}
func (h *hashMap) getKeyIndex(key string) uint64 {
return generateHash(key) % h.len
}
func generateHash(value string) uint64 {
hash := sha1.New()
hash.Write([]byte(value))
return binary.BigEndian.Uint64(hash.Sum(nil))
}
type keyValue struct {
key string
value string
next *keyValue
}
func (kv *keyValue) add(key, value string) {
next := *kv
*kv = keyValue{key: key, value: value, next: &next}
}
func (kv *keyValue) find(key string) (string, bool) {
if kv == nil {
return "", false
} else if kv.key == key {
return kv.value, true
}
return kv.next.find(key)
}