Go 语言实现哈希表

下面将 hashTable.go 中的 Go 语言代码分成五个部分来讲解哈希表。

下面是 hashTable.go 中的第一部分:

  1. package main
  2. import (
  3. "fmt
  4. )
  5. const SIZE = 15
  6. type Node struct {
  7. Value int
  8. Next *Node
  9. }

这一部分是哈希表中节点的定义,毫无疑问,我们使用 Go 的结构体进行了实现。SIZE 常量表示哈希表中桶的数量。

下面的 Go 代码是 hashTable.go 中的第二段:

  1. type HashTable struct {
  2. Table map[int]*Node
  3. Size int
  4. }
  5. func hashFunction(i, size int) int {
  6. return (i % size)
  7. }

在这个代码段中,你可以看到在这个哈希表中使用的哈希函数。hashFunction() 使用了模运算符。这里使用模运算符的主要原因是这个哈希表要处理的是整数值的键。如果你要应对的是字符串或浮点数的键,那么你的哈希函数的逻辑应该与这不同。

真正的哈希表存在一个 HashTable 结构体中,它有两个字段。第二个字段表示哈希表的大小,第一个字段则是连接整数和链表(*Node)的 map。因此,这个哈希表中链表的数量与桶的数量相等。这也意味着哈希表上每个桶中的节点都会使用链表存储。之后会进一步对链表进行介绍。

hashTable.go 的第三部分如下:

  1. func insert(hash *HashTable, value int) int {
  2. index := hashFunction(value, hash.Size)
  3. element := Node{Value: value, Next: hash.Table[index]}
  4. hash.Table[index] = &element
  5. return index
  6. }

insert() 函数用于向哈希表中插入元素。注意,当前 insert() 的实现不会检查值是否重复。

下面是 hashTable.go 的第四部分:

  1. func traverse(hash *HashTable) {
  2. for k := range hash.Table {
  3. if hash.Table[k] != nil {
  4. t := hash.Table[k]
  5. for t != nil {
  6. fmt.Printf("%d -> ", t.Value)
  7. t = t.Next
  8. }
  9. }
  10. fmt.Println()
  11. }
  12. }

traverse() 函数用于输出哈希表所有的值。这个函数访问哈希表中所有链表,然后依次输出每个链表上存储的值。

hashTable.go 的最后一部分代码如下:

  1. func main() {
  2. table := make(map[int]*Node, SIZE)
  3. hash := &HashTable{Table: table, Size: SIZE}
  4. fmt.Println("Numbder of spaces:", hash.Size)
  5. for i := 0; i < 120; i++ {
  6. insert(hash, i)
  7. }
  8. traverse(hash)
  9. }

在这部分代码中,你将创建一个新的、命名为 hash 的哈希表,它接收一个 table 变量,这个变量是一个保存了哈希表中所有桶的 map。正如你所知道的,这个哈希表的槽是使用链表实现的。我们使用 map 保存哈希表中的链表,而没用切片或数组,这主要是因为切片或数组的键只能是正整数,但 map 的键则几乎可以满足你的所有需求。

执行 hashTable.go 将生成如下输出:

  1. $ go run hashTable.go
  2. 108 -> 93 -> 78 -> 63 -> 48 -> 33 -> 18 -> 3 ->
  3. 109 -> 94 -> 79 -> 64 -> 49 -> 34 -> 19 -> 4 ->
  4. 117 -> 102 -> 87 -> 72 -> 57 -> 42 -> 27 -> 12 ->
  5. 119 -> 104 -> 89 -> 74 -> 59 -> 44 -> 29 -> 14 ->
  6. 111 -> 96 -> 81 -> 66 -> 51 -> 36 -> 21 -> 6 ->
  7. 112 -> 97 -> 82 -> 67 -> 52 -> 37 -> 22 -> 7 ->
  8. 116 -> 101 -> 86 -> 71 -> 56 -> 41 -> 26 -> 11 ->
  9. 114 -> 99 -> 84 -> 69 -> 54 -> 39 -> 24 -> 9 ->
  10. 118 -> 103 -> 88 -> 73 -> 58 -> 43 -> 28 -> 13 ->
  11. 105 -> 90 -> 75 -> 60 -> 45 -> 30 -> 15 -> 0 ->
  12. 106 -> 91 -> 76 -> 61 -> 46 -> 31 -> 16 -> 1 ->
  13. 107 -> 92 -> 77 -> 62 -> 47 -> 32 -> 17 -> 2 ->
  14. 110 -> 95 -> 80 -> 65 -> 50 -> 35 -> 20 -> 5 ->
  15. 113 -> 98 -> 83 -> 68 -> 53 -> 38 -> 23 -> 8 ->
  16. 115 -> 100 -> 85 -> 70 -> 55 -> 40 -> 25 -> 10 ->

这个哈希表已经完美平衡,因为它所需要做的是将连续数放入模运算所计算出的槽中。但是现实世界的问题中可能不会出现这么方便的结果!

在欧几里得除法中,两个自然数 a 和 b 之间的余数可以通过公式 a = bq + r 进行计算,这里的 q 是商,r 是余数。余数的值的范围是 0 到 b-1,这个范围中的值都是模运算可能的结果。

注意,如果多次运行 hashTable.go,你所得到的那些输出的行的顺序很可能不同,因为 Go 的 map 输出键值对的顺序是完全随机的!