-
Notifications
You must be signed in to change notification settings - Fork 15
/
hashmap.go
141 lines (128 loc) · 2.97 KB
/
hashmap.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
136
137
138
139
140
141
/*
This package defines a generic hashmap
This hashmap can store any Hasher object as key
and any object as value.
Similarly to Java HashMap, Hasher objects must define two functions:
- HashCode and
- HashEquals
*/
package hashmap
import (
"sync"
)
type HashMap struct {
mapArray []Bucket
capacity uint64
loadfactor float64
total int
sync.RWMutex
}
type Bucket []*KeyValue
type KeyValue struct {
Key Hasher
Value interface{}
}
type Hasher interface {
HashCode() uint64
HashEquals(k Hasher) bool
}
// Initializes a HashMap
func NewHashMap(size uint64, loadfactor float64) *HashMap {
return &HashMap{
mapArray: make([]Bucket, size),
capacity: size,
loadfactor: loadfactor,
total: 0,
}
}
// Returns the count for the given Edge
// If the edge is not present, returns 0 and false
// If the edge is present, returns the value and true
func (em *HashMap) Value(h Hasher) (interface{}, bool) {
em.RLock()
defer em.RUnlock()
index := indexFor(h.HashCode(), em.capacity)
if em.mapArray[index] != nil {
for _, kv := range em.mapArray[index] {
if h.HashEquals(kv.Key) {
return kv.Value, true
}
}
}
return nil, false
}
func (em *HashMap) PutValue(h Hasher, value interface{}) {
em.Lock()
defer em.Unlock()
index := indexFor(h.HashCode(), em.capacity)
if em.mapArray[index] == nil {
em.mapArray[index] = make(Bucket, 1, 3)
em.mapArray[index][0] = &KeyValue{h, value}
em.total++
} else {
for _, kv := range em.mapArray[index] {
if h.HashEquals(kv.Key) {
kv.Value = value
return
}
}
//fmt.Fprintf(os.Stderr, "Collision (%d)!!!\n", index)
em.mapArray[index] = append(em.mapArray[index], &KeyValue{h, value})
em.total++
}
em.rehash()
}
// returns the index in the hash map, given a hashcode
func indexFor(hashcode uint64, capacity uint64) uint64 {
return hashcode & (capacity - 1)
}
// Reconstructs the HashMap if the capacity is almost attained (loadfactor)
func (em *HashMap) rehash() {
// We rehash everything with a new capacity
if float64(em.total) >= float64(em.capacity)*em.loadfactor {
newcapacity := em.capacity * 2
newmap := make([]Bucket, newcapacity)
for _, b := range em.mapArray {
if b != nil {
for _, kv := range b {
index := indexFor(kv.Key.HashCode(), newcapacity)
if newmap[index] == nil {
newmap[index] = make(Bucket, 1, 5)
newmap[index][0] = kv
} else {
newmap[index] = append(newmap[index], kv)
}
}
}
}
em.capacity = newcapacity
em.mapArray = newmap
}
}
/* Returns all keys of the index */
func (em *HashMap) Keys() []Hasher {
keys := make([]Hasher, em.total)
total := 0
for _, b := range em.mapArray {
if b != nil {
for _, kv := range b {
keys[total] = kv.Key
total++
}
}
}
return keys
}
func (em *HashMap) KeyValues() []*KeyValue {
keyvalues := make([]*KeyValue, em.total)
total := 0
for _, b := range em.mapArray {
if b != nil {
for _, kv := range b {
keyvalues[total] = kv
total++
}
}
}
return keyvalues
}