散列

散列为一种用于以常数平均时间执行插入，删除和查找的技术。一般的实现方法是使通过数据的关键字可以计算出该数据所在散列中的位置，类似于Python中的字典。关于散列需要解决以下问题：

  • 散列的关键字如何映射为一个数（索引）——散列函数
  • 当两个关键字的散列函数结果相同时，如何解决——冲突

散列函数

散列函数为关键字->索引的函数，常用的关键字为字符串，则需要一个字符串->整数的映射关系，常见的三种散列函数为：

  • ASCII码累加（简单）
  • 计算前三个字符的加权和$\sum key[i] * 27^{i}$ （不太好，3个字母的常用组合远远小于可能组合）
  • 计算所有字符加权和并对散列长度取余$(\sum key[i] * 32^{i}) \% tablesize$（较好）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 累加
func (n *node) hashSum() int {
	hash := 0
	for i := range n.key {
		hash += int(n.key[i])
	}
	return hash
}
// 前三个字符和
func (n *node) hashTop3() int {
	hash := 0
	time := utf8.RuneCountInString(n.key)
	if time > 3 {
		time = 3
	}
	for i := 0; i < time; i++ {
		hash += int(n.key[i])
	}
	return hash
}
// 所有字符和取余
func (n *node) hashMod(lenght int) int {
	hash := 0
	for i := range n.key {
		hash += int(n.key[i]) * 32
	}
	return hash % lenght
}

冲突

当不同关键字计算出的散列值相同时，发生冲突，本次使用分离链接法解决：

  • 每个散列中的数据结构有一个指针可以指向下一个数据，因此散列表可以看成链表头的集合
  • 当插入时，将数据插入在对应散列值的链表中
  • 访问时，遍历对应散列值的链表，直到找到关键字

代码实现

散列节点

结构体

1
2
3
4
5
6
7
8
9
10
type nodeData struct {
	data int
}

type node struct {
	key  string
	hash int
	data nodeData
	next *node
}

散列值计算（使用第三种）

1
2
3
4
func (n *node) HashCompute(lenght int) {
	n.hash = n.hashMod(lenght)
	// fmt.Println("key:", n.key, "hash:", n.hash)
}

构造函数

1
2
3
4
func newNode(data nodeData, key string) *node {
	temp := &node{key, 0, data, nil}
	return temp
}

散列表

结构体

1
2
3
type hashTable struct {
	table [17]node
}

插入方法

1
2
3
4
5
6
func (h *hashTable) insert(data nodeData, key string) {
	temp := newNode(data, key)
	temp.HashCompute(len(h.table))
	temp.next = h.table[temp.hash].next
	h.table[temp.hash].next = temp
}

访问方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (h *hashTable) visit(key string) (nodeData, error) {
	temp := newNode(nodeData{}, key)
	temp.HashCompute(len(h.table))
    //设计失误，仅有节点有计算散列值的方法，因此需要定义一个散列节点用于计算散列值
	point := h.table[temp.hash].next
	for point != nil {
		if point.key == key {
			return point.data, nil
		}
		point = point.next
	} //遍历链表，搜索关键字
	return temp.data, errors.New("not exsist")
    // 失败退出
}

构造函数

1
2
3
4
5
6
7
func newHashTable() *hashTable {
	temp := &hashTable{}
	for i := range temp.table {
		temp.table[i] = *newNode(nodeData{}, "")
	}
	return temp
}