写点什么

学习 Go 语言数据结构:实现哈希表

作者:宇宙之一粟
  • 2022 年 8 月 30 日
    广东
  • 本文字数:1474 字

    阅读完需:约 5 分钟

学习 Go 语言数据结构:实现哈希表

前言


哈希表是开发过程中最常使用的一种数据结构,该数据结构不是使用自定义的键来存储 map 中的值,而是对键执行散列函数,以返回数组中一个项目的确切索引。


原理


  • 链接法

  • 开放定址法


  1. 创建一个长度等于哈希表中键/值对的预期数量的数组。数组越大,发生碰撞的机会就越低

  2. 创建一个散列函数,它将获取您要添加的键的值并将其转换为数字。此功能越好,碰撞的机会就越低

  3. 取散列函数生成的数字并计算与数组长度的模数。(例如,如果散列为 1234,数组长度为 100,则计算 1234 % 100)。这将是要存储值的数组中的索引。


Go 语言实现


将哈希表表示为 map,实现四个功能:

  • Insert()

  • Search()

  • Delete()

  • Size()


首先,可以为底层数据存储选择一个数组大小(桶数量)。在目前的实现是固定大小的,但在实际的版本将能够在键的数量达到数组的长度时,动态地创建一个更大的数组(Java JDK 7 hashmap 的实现方式)。


const ArraySize = 7 // 哈希表的桶数量
复制代码


其次,像链表一样,也需要节点用来存储数据定义:

// 桶结构(本质即链表)type bucket struct {	head *bucketNode}
// 桶节点type bucketNode struct { key string next *bucketNode}
复制代码

定义哈希表数据结构:

  • 第一个字段 Table 被定义为一个 map,并将一个整数与链表节点(*Node) 关联

  • 第二个字段 Size 为哈希表的长度

// 哈希表结构体type HashTable struct {	array [ArraySize]*bucket}
复制代码

最终,哈希表能有的链表数量与其桶数量相同。


哈希映射中最重要的事情之一可能是哈希函数。接下来是哈希函数,hashFunction() 函数使用了模运算符:

// 哈希函数func hash(key string) int {	sum := 0	for _, v := range key {		sum += int(v)	}	return sum % ArraySize}
复制代码


接下来是插入、查找和删除功能:

// 插入将传入一个 key 参数,并将其添加到哈希表中func (ht *HashTable) Insert(key string) {	index := hash(key)	ht.array[index].insert(key)}
// 查找将接收一个 key 参数,如果在表中,则返回 true,如果不在,则返回 falsefunc (ht *HashTable) Search(key string) bool { index := hash(key) return ht.array[index].search(key)}
// 删除将接收一个 key 参数,并从哈希表中删除它func (ht *HashTable) Delete(key string) { index := hash(key) ht.array[index].delete(key)}
复制代码


以下是通过链表的方式实现的查找、插入和删除:

// 链表查找func (b *bucket) search(k string) bool {
currNode := b.head for currNode != nil { if currNode.key == k { return true } currNode = currNode.next } return false}
// insert 将输入一个 key ,用 key 创建一个节点,并将该节点放入桶内func (b *bucket) insert(k string) { if !b.search(k) { newNode := &bucketNode{key: k} newNode.next = b.head b.head = newNode } else { fmt.Print(k, "already exists!") }}
// delete 将接收一个 key ,并从桶中删除该节点func (b *bucket) delete(k string) {
if b.head.key == k { b.head = b.head.next return }
prevNode := b.head for prevNode.next != nil { if prevNode.next.key == k { // 删除 prevNode.next = prevNode.next.next return } prevNode = prevNode.next }}
复制代码


main 函数如下:

func main() {	hashTable := Init()	list := []string{		"A",		"B",		"C",		"D",	}
for _, v := range list { hashTable.Insert(v) }
hashTable.Delete("C")}
复制代码

总结


哈希表可以在 O(1) 的时间内访问键和值。哈希表非常适用于字典,或其他需要搜索大量数据的应用中。


发布于: 刚刚阅读数: 4
用户头像

宇宙古今无有穷期,一生不过须臾,当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖,江湖却没有我的影子 热爱技术,专注于后端全栈,轻易不换岗 拒绝内卷,工作于软件工程师,弹性不加班 热衷分享,执着于阅读写作,佛系不水文

评论

发布
暂无评论
学习 Go 语言数据结构:实现哈希表_哈希表_宇宙之一粟_InfoQ写作社区