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

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

前言

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

原理

  • 链接法
  • 开放定址法

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

  • 创建一个散列函数,它将获取您要添加的键的值并将其转换为数字。此功能越好,碰撞的机会就越低
  • 取散列函数生成的数字并计算与数组长度的模数。(例如,如果散列为 1234,数组长度为 100,则计算 1234 % 100)。这将是要存储值的数组中的索引。

Go 语言实现

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

  • ​Insert()​
  • ​Search()​
  • ​Delete()​
  • ​Size()​

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

const ArraySize = 7 // 哈希表的桶数量

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

[En]

Second, like linked lists, nodes are required to store data definitions:

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

定义哈希表数据结构:

  • 第一个字段 Table 被定义为一个 map,并将一个整数与链表节点(*Node) 关联
  • 第二个字段 Size 为哈希表的长度
// 哈希表结构体type HashTable struct {  array [ArraySize]*bucket}

最终,哈希表可以拥有与其存储桶相同数量的链表。

[En]

Eventually, a hash table can have the same number of linked lists as its buckets.

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

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

然后是插入、查找和删除功能:

[En]

Then there are the insert, find, and delete functions:

// 插入将传入一个 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)}

以下是通过链接列表进行的查找、插入和删除操作:

[En]

The following are lookups, inserts, and deletions through a linked list:

// 链表查找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)​​ 的时间内访问键和值。哈希表非常适用于字典,或其他需要搜索大量数据的应用中。

Original: https://blog.51cto.com/yuzhou1su/5635116
Author: 宇宙之一粟
Title: 学习 Go 语言数据结构:实现哈希表

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/500236/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球