Go 语言实现哈希表

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

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

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

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

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

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

在这个代码段中，你可以看到在这个哈希表中使用的哈希函数。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 输出键值对的顺序是完全随机的！