# 散列表
# 散列表分类
- 线性探索散列表
- 链表式散列表
# 时间复杂度
- 修改(增删改)时间复杂度 O(1)
- 查询时间复杂度O(1)
package hash
import (
"bytes"
"crypto/md5"
"crypto/sha1"
"encoding/binary"
"fmt"
)
//无链表的散列表
type NoLinkHashTable struct {
Buckets []Bucket
Capacity int32
Used int32
}
//桶
type Bucket struct {
HKey string
Data int
}
func NolinkHashTable(length int32) {
//新建算列表
ht := NoLinkHashTable{}
ht.Capacity = length
ht.Buckets = make([]Bucket, length)
for i := 0; i < 5; i++ {
ht.hSet("abc", i)
}
fmt.Println(ht)
one := ht.hGet("abc")
fmt.Println(one)
}
func (ht *NoLinkHashTable) hSet(key string, value int) {
bucket := Bucket{key, value}
hashCode := GetHashCode(key, 1)
index := hashCode % (ht.Capacity - 1)
ht.addBucket(index, key, bucket)
}
func (ht *NoLinkHashTable) hGet(key string) Bucket {
hashCode := GetHashCode(key, 1)
index := hashCode % (ht.Capacity - 1)
return ht.findBucket(index, key)
}
func (ht *NoLinkHashTable) findBucket(index int32, key string) Bucket {
var empty = Bucket{}
if ok := ht.Buckets[index]; ok != empty {
if ht.Buckets[index].HKey == key {
return ht.Buckets[index]
} else {
index++
}
for {
if ok := ht.Buckets[index]; ok != empty {
if ht.Buckets[index].HKey == key {
return ht.Buckets[index]
} else {
index++
}
} else {
return empty
}
}
}
return empty
}
func (ht *NoLinkHashTable) addBucket(index int32, key string, bucket Bucket) {
if ht.Capacity == ht.Used {
panic("Table is full")
}
var empty = Bucket{}
if ok := ht.Buckets[index]; ok != empty {
if ok.HKey == key {
ht.Buckets[index] = bucket
return
}
//已经存在
index++
for {
//fmt.Println(index)
if index >= ht.Capacity {
index = 0
}
if ok := ht.Buckets[index]; ok != empty {
if ok.HKey == key {
ht.Buckets[index] = bucket
return
}
index++
} else {
ht.Buckets[index] = bucket
ht.Used++
break
}
}
} else {
ht.Buckets[index] = bucket
ht.Used++
}
}
func GetHashCode(key string, hashType int) int32 {
var Result []byte
switch hashType {
case 1:
Md5Inst := md5.New()
Md5Inst.Write([]byte(key))
Result = Md5Inst.Sum([]byte(""))
case 2:
Sha1Inst := sha1.New()
Sha1Inst.Write([]byte(key))
Result = Sha1Inst.Sum([]byte(""))
}
bin_buf := bytes.NewBuffer(Result)
var x int32
binary.Read(bin_buf, binary.BigEndian, &x)
return x
}
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
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