-
Notifications
You must be signed in to change notification settings - Fork 0
/
basicmap.go
80 lines (72 loc) · 1.49 KB
/
basicmap.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
package hashing
import (
"bytes"
"container/list"
"encoding/gob"
"errors"
"strconv"
)
type basicHashMap struct {
table []*list.List
}
func NewBasicHashMap() HashMap {
initSize := 64
table := make([]*list.List, 64)
for i := 0; i < initSize; i++ {
table[i] = list.New()
}
return &basicHashMap{table: table}
}
func hash(bytes []byte) int {
h := 0
for b := range bytes {
h = 31*h + b
}
return h
}
func (b *basicHashMap) Put(key string, value interface{}) error {
var buffer bytes.Buffer
err := gob.NewEncoder(&buffer).Encode(value)
if err != nil {
return errors.New("bad value")
}
h := hash([]byte(key))
index := h % len(b.table)
encodedValue := buffer.Bytes()
b.table[index].PushBack(pair{key, encodedValue})
return nil
}
func search(l *list.List, key string) (encodedValue []byte) {
element := l.Front()
for element != nil {
p := element.Value.(pair)
if p.key == key {
return p.value
}
}
return nil
}
func (b *basicHashMap) Get(key string, value interface{}) error {
h := hash([]byte(key))
index := h % len(b.table)
foundEncodedValue := search(b.table[index], key)
if foundEncodedValue == nil {
return errors.New("key not present")
}
buffer := bytes.NewReader(foundEncodedValue)
err := gob.NewDecoder(buffer).Decode(value)
if err != nil {
return errors.New("bad encoded value")
}
return nil
}
func (b *basicHashMap) ToString() string {
s := ""
for i, l := range b.table {
s += strconv.Itoa(i)
e := l.Front()
for e != nil {
s += e.Value.(pair).key
}
}
}