下面将 hashTable.go
中的 Go 语言代码分成五个部分来讲解哈希表。
下面是 hashTable.go
中的第一部分:
Copy package main
import (
"fmt
)
const SIZE = 15
type Node struct {
Value int
Next *Node
}
这一部分是哈希表中节点的定义,毫无疑问,我们使用 Go 的结构体进行了实现。SIZE
常量表示哈希表中桶的数量。
下面的 Go 代码是 hashTable.go
中的第二段:
Copy type HashTable struct {
Table map [ int ] * Node
Size int
}
func hashFunction (i, size int ) int {
return (i % size)
}
在这个代码段中,你可以看到在这个哈希表中使用的哈希函数。hashFunction()
使用了模运算符 。这里使用模运算符的主要原因是这个哈希表要处理的是整数值的键。如果你要应对的是字符串或浮点数的键,那么你的哈希函数的逻辑应该与这不同。
真正的哈希表存在一个 HashTable
结构体中,它有两个字段。第二个字段表示哈希表的大小,第一个字段则是连接整数和链表(*Node
)的 map。因此,这个哈希表中链表的数量与桶的数量相等。这也意味着哈希表上每个桶中的节点都会使用链表存储。之后会进一步对链表进行介绍。
hashTable.go
的第三部分如下:
Copy func insert (hash * HashTable , value int ) int {
index := hashFunction (value, hash.Size)
element := Node {Value: value, Next: hash.Table[index]}
hash.Table[index] = & element
return index
}
insert()
函数用于向哈希表中插入元素。注意,当前 insert()
的实现不会检查值是否重复。
下面是 hashTable.go
的第四部分:
Copy func traverse (hash * HashTable ) {
for k := range hash.Table {
if hash.Table[k] != nil {
t := hash.Table[k]
for t != nil {
fmt. Printf ( " %d -> " , t.Value)
t = t.Next
}
}
fmt. Println ()
}
}
traverse()
函数用于输出哈希表所有的值。这个函数访问哈希表中所有链表,然后依次输出每个链表上存储的值。
hashTable.go
的最后一部分代码如下:
Copy func main () {
table := make ( map [ int ] * Node , SIZE)
hash := & HashTable {Table: table, Size: SIZE}
fmt. Println ( "Numbder of spaces:" , hash.Size)
for i := 0 ; i < 120 ; i ++ {
insert (hash, i)
}
traverse (hash)
}
在这部分代码中,你将创建一个新的、命名为 hash
的哈希表,它接收一个 table
变量,这个变量是一个保存了哈希表中所有桶的 map。正如你所知道的,这个哈希表的槽是使用链表实现的。我们使用 map 保存哈希表中的链表,而没用切片或数组,这主要是因为切片或数组的键只能是正整数,但 map 的键则几乎可以满足你的所有需求。
执行 hashTable.go
将生成如下输出:
Copy $ go run hashTable.go
108 - > 93 - > 78 - > 63 - > 48 - > 33 - > 18 - > 3 - >
109 - > 94 - > 79 - > 64 - > 49 - > 34 - > 19 - > 4 - >
117 - > 102 - > 87 - > 72 - > 57 - > 42 - > 27 - > 12 - >
119 - > 104 - > 89 - > 74 - > 59 - > 44 - > 29 - > 14 - >
111 - > 96 - > 81 - > 66 - > 51 - > 36 - > 21 - > 6 - >
112 - > 97 - > 82 - > 67 - > 52 - > 37 - > 22 - > 7 - >
116 - > 101 - > 86 - > 71 - > 56 - > 41 - > 26 - > 11 - >
114 - > 99 - > 84 - > 69 - > 54 - > 39 - > 24 - > 9 - >
118 - > 103 - > 88 - > 73 - > 58 - > 43 - > 28 - > 13 - >
105 - > 90 - > 75 - > 60 - > 45 - > 30 - > 15 - > 0 - >
106 - > 91 - > 76 - > 61 - > 46 - > 31 - > 16 - > 1 - >
107 - > 92 - > 77 - > 62 - > 47 - > 32 - > 17 - > 2 - >
110 - > 95 - > 80 - > 65 - > 50 - > 35 - > 20 - > 5 - >
113 - > 98 - > 83 - > 68 - > 53 - > 38 - > 23 - > 8 - >
115 - > 100 - > 85 - > 70 - > 55 - > 40 - > 25 - > 10 - >
这个哈希表已经完美平衡,因为它所需要做的是将连续数放入模运算 所计算出的槽中。但是现实世界的问题中可能不会出现这么方便的结果!
在欧几里得除法中,两个自然数 a 和 b 之间的余数可以通过公式 a = bq + r 进行计算,这里的 q 是商,r 是余数。余数的值的范围是 0 到 b-1,这个范围中的值都是模运算可能的结果。
注意,如果多次运行 hashTable.go
,你所得到的那些输出的行的顺序很可能不同,因为 Go 的 map 输出键值对的顺序是完全随机的!