Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
114 lines (88 sloc) 4.13 KB

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

You can’t perform that action at this time.