Question

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 输出键值对的顺序是完全随机的！