Go 语言实现哈希表
下面将 hashTable.go 中的 Go 语言代码分成五个部分来讲解哈希表。
下面是 hashTable.go 中的第一部分：
package main
import (
"fmt
)
const SIZE = 15
type Node struct {
Value int
Next *Node
}这一部分是哈希表中节点的定义，毫无疑问，我们使用 Go 的结构体进行了实现。SIZE 常量表示哈希表中桶的数量。
下面的 Go 代码是 hashTable.go 中的第二段：
type HashTable struct {
Table map[int]*Node
Size int
}
func hashFunction(i, size int) int {
return (i % size)
}在这个代码段中，你可以看到在这个哈希表中使用的哈希函数。hashFunction() 使用了模运算符。这里使用模运算符的主要原因是这个哈希表要处理的是整数值的键。如果你要应对的是字符串或浮点数的键，那么你的哈希函数的逻辑应该与这不同。
真正的哈希表存在一个 HashTable 结构体中，它有两个字段。第二个字段表示哈希表的大小，第一个字段则是连接整数和链表（*Node）的 map。因此，这个哈希表中链表的数量与桶的数量相等。这也意味着哈希表上每个桶中的节点都会使用链表存储。之后会进一步对链表进行介绍。
hashTable.go 的第三部分如下：
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 的第四部分：
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 的最后一部分代码如下：
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 将生成如下输出：
$ 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 输出键值对的顺序是完全随机的！
