/
hashtable.go
109 lines (92 loc) · 2.1 KB
/
hashtable.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
package hashtable
import (
"fmt"
"hash/fnv"
"strconv"
"github.com/donng/Play-with-Data-Structures/14-Hash-Table/06-Resizing-in-Hash-Table/RBTree"
)
const upperTol = 10
const lowerTol = 2
const initCapacity = 7
type HashTable struct {
hashtable []*RBTree.RBTree
M int
size int
}
func New(M int) *HashTable {
var hashtable []*RBTree.RBTree
for i := 0; i < M; i++ {
hashtable = append(hashtable, RBTree.New())
}
return &HashTable{hashtable, M, 0}
}
func (h *HashTable) GetSize() int {
return h.size
}
func (h *HashTable) Add(key interface{}, value interface{}) {
m := h.hashtable[h.hash(key)]
if m.Contains(key) {
m.Add(key, value)
} else {
m.Add(key, value)
h.size++
if h.size >= upperTol*h.M {
h.resize(2 * h.M)
}
}
}
func (h *HashTable) Remove(key interface{}) interface{} {
m := h.hashtable[h.hash(key)]
if m.Contains(key) {
ret := m.Remove(key)
h.size--
if h.size < lowerTol*h.M && h.M/2 > initCapacity {
h.resize(h.M / 2)
}
return ret
} else {
return nil
}
}
func (h *HashTable) Set(key interface{}, value interface{}) {
m := h.hashtable[h.hash(key)]
if !m.Contains(key) {
panic(fmt.Sprintf("%s doesn't exist!", key))
}
m.Set(key, value)
}
func (h *HashTable) Contains(key interface{}) bool {
return h.hashtable[h.hash(key)].Contains(key)
}
func (h *HashTable) Get(key interface{}) interface{} {
return h.hashtable[h.hash(key)].Get(key)
}
func (h *HashTable) resize(newM int) {
var newHashTable []*RBTree.RBTree
for i := 0; i < newM; i++ {
newHashTable = append(newHashTable, RBTree.New())
}
oldM := h.M
h.M = newM
for i := 0; i < oldM; i++ {
m := h.hashtable[i]
for _, key := range m.KeySet() {
newHashTable[h.hash(key)].Add(key, m.Get(key))
}
}
h.hashtable = newHashTable
}
func (h *HashTable) hash(key interface{}) int {
return (int(HashCode(key)) & 0x7fffffff) % h.M
}
func HashCode(source interface{}) uint64 {
switch source.(type) {
case int:
source = strconv.Itoa(source.(int))
case float64:
source = strconv.FormatFloat(source.(float64), 'f', 6, 64)
}
h := fnv.New64a()
h.Write([]byte(source.(string)))
return h.Sum64()
}