Hash散列原理(map的原理), 代码实现链表结构, 这也是go中map本质
map又名 hash表
优化后的数据结构
知识点:
数据结构的链表
hash散列算法
链表单位组成: 地址域, 数值域
代码构建 链表, 行为上和 map 一样
创建链表的包文件
1
2
3
4package LinkNodes
import ("fmt")
var head *Node
var curr *Node // 全局变量
定义节点结构体
1
2
3
4
5
6
7//节点类型
type Node struct {
//数据域
Data string
//地址域
NextNode *Node
}创建头结点的方法
1
2
3
4
5
6
7
8
9func CreateHeadNode(data string) *Node {
var node *Node = new(Node)
node.Data = data
node.NextNode = nil
head = node
curr = node
return node
}添加新节点的方法
1
2
3
4
5
6
7
8
9
10
11//添加新节点
func AddNode(data string) *Node {
var newNode *Node = new(Node)
newNode.Data = data
newNode.NextNode = nil
//挂接节点 //两个
curr.NextNode = newNode ///
curr = newNode
return newNode
}挂接节点的意义在于, 连成 链 的结构, 让两个节点产生关系
- 老节点的地址域 储存新节点的地址
curr.NextNode=newnode - 当前节点curr的变量=新节点
- 老节点的地址域 储存新节点的地址
插入节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23func InserNodeIndex(index int, data string) *Node {
if index == 0 {
//插入头结点
var node *Node = new(Node)
node.Data = data
node.NextNode = head
head = node
} else if index > NodeCnt()-1 {
//添加节点
AddNode(data)
} else {
//中间插入节点
var midnode *Node = new(Node)
var n = head
for i := 0; i < index-1; i++ {
n = n.NextNode //定位到当前节点的前一个节点
}
midnode.Data = data
midnode.NextNode = n.NextNode
n.NextNode = midnode
}
return nil
}
整体链表包代码
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
136package LinkNodes
import (
"fmt"
)
// 声明全局变量, 保存头结点
var head *Node
var curr *Node
//节点类型
type Node struct {
//数据域
Data string
//地址域
NextNode *Node
}
// 创建头结点
func CreateHeadNode(data string) *Node {
var node *Node = new(Node)
node.Data = data
node.NextNode = nil
head = node
curr = node
return node
}
//添加新节点
func AddNode(data string) *Node {
var newNode *Node = new(Node)
newNode.Data = data
newNode.NextNode = nil
//挂接节点 //两个
curr.NextNode = newNode ///
curr = newNode
return newNode
}
func ShowNodes() {
var node = head
for {
fmt.Println(node.Data)
node = node.NextNode
if node.NextNode == nil {
fmt.Println(node.Data)
break
}
}
}
// 计算节点个数
func NodeCnt() int {
var node = head
var n int
n = 2
if node.NextNode != nil {
n++
node = node.NextNode
}
n++
return n
}
// 插入节点 根据下标插入节点
func InserNodeIndex(index int, data string) *Node {
if index == 0 {
//插入头结点
var node *Node = new(Node)
node.Data = data
node.NextNode = head
head = node
} else if index > NodeCnt()-1 {
//添加节点
AddNode(data)
} else {
//中间插入节点
var midnode *Node = new(Node)
var n = head
for i := 0; i < index-1; i++ {
n = n.NextNode //定位到当前节点
}
midnode.Data = data
midnode.NextNode = n.NextNode
n.NextNode = midnode
/*
//中间插入节点
var n = head
for i := 0; i < index-1; i++ {
n = n.NextNode
}
var newNode *Node = new(Node)
newNode.Data = data
newNode.NextNode = n.NextNode
n.NextNode = newNode
*/
}
return nil
}
//删除节点
func DeleteNodeIndex(Index int) {
var n = head
if Index == 0 {
head = n.NextNode
} else {
for i := 0; i < Index-1; i++ { //目标节点的前一个节点
n = n.NextNode
}
n.NextNode = n.NextNode.NextNode
}
}
// 修改节点
func UpdateNodeByIndex(index int, data string) {
var node = head
if index == 0 {
head.Data = data
} else {
for i := 0; i < index; i++ {
node = node.NextNode
}
node.Data = data
}
}
以上完成了一个 链表的 数据结构
哈希散列
现在我们创建一个装载链表的容器, 一个容量16的数组, 数据类型: Node
并且我们将 node 节点的data字段从string优化为struc结构体.
首先 我们有16个数组容量 分别是0-15
将HashCode的功能就是将 平均分散任意的字符串转换为 0~15 的数值
本质上我们就将数值平均分类处理了
1 | // 数据分散分布在容器内 |
1 | //将key 转换成数组下标的散列算法 |
1 | // 向数组添加键值对 |
1 | // 获取数据 |
1 | // main函数 |