-
Notifications
You must be signed in to change notification settings - Fork 0
/
HashMap.go
119 lines (99 loc) · 1.98 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
package main
import (
"fmt"
)
type HashMap struct {
key string
value string
hashCode int
next *HashMap
}
var table [16](*HashMap)
func initTable() {
for i := range table{
table[i] = &HashMap{"","",i,nil}
}
}
func getInstance() [16](*HashMap){
if(table[0] == nil){
initTable()
}
return table
}
func genHashCode(k string) int{
if len(k) == 0{
return 0
}
var hashCode int = 0
var lastIndex int = len(k) - 1
for i := range k {
if i == lastIndex {
hashCode += int(k[i])
break
}
hashCode += (hashCode + int(k[i]))*31
}
return hashCode
}
func indexTable(hashCode int) int{
return hashCode%16
}
func indexNode(hashCode int) int {
return hashCode>>4
}
func put(k string, v string) string {
var hashCode = genHashCode(k)
var thisNode = HashMap{k,v,hashCode,nil}
var tableIndex = indexTable(hashCode)
var nodeIndex = indexNode(hashCode)
var headPtr [16](*HashMap) = getInstance()
var headNode = headPtr[tableIndex]
if (*headNode).key == "" {
*headNode = thisNode
return ""
}
var lastNode *HashMap = headNode
var nextNode *HashMap = (*headNode).next
for nextNode != nil && (indexNode((*nextNode).hashCode) < nodeIndex){
lastNode = nextNode
nextNode = (*nextNode).next
}
if (*lastNode).hashCode == thisNode.hashCode {
var oldValue string = lastNode.value
lastNode.value = thisNode.value
return oldValue
}
if lastNode.hashCode < thisNode.hashCode {
lastNode.next = &thisNode
}
if nextNode != nil {
thisNode.next = nextNode
}
return ""
}
func get(k string) string {
var hashCode = genHashCode(k)
var tableIndex = indexTable(hashCode)
var headPtr [16](*HashMap) = getInstance()
var node *HashMap = headPtr[tableIndex]
if (*node).key == k{
return (*node).value
}
for (*node).next != nil {
if k == (*node).key {
return (*node).value
}
node = (*node).next
}
return ""
}
//examples
func main() {
getInstance()
put("a","a_put")
put("b","b_put")
fmt.Println(get("a"))
fmt.Println(get("b"))
put("p","p_put")
fmt.Println(get("p"))
}