前言
哈希表是开发过程中最常使用的一种数据结构,该数据结构不是使用自定义的键来存储 map 中的值,而是对键执行散列函数,以返回数组中一个项目的确切索引。
原理
创建一个长度等于哈希表中键/值对的预期数量的数组。数组越大,发生碰撞的机会就越低
创建一个散列函数,它将获取您要添加的键的值并将其转换为数字。此功能越好,碰撞的机会就越低
取散列函数生成的数字并计算与数组长度的模数。(例如,如果散列为 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
}
复制代码
定义哈希表数据结构:
// 哈希表结构体
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,如果不在,则返回 false
func (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)
的时间内访问键和值。哈希表非常适用于字典,或其他需要搜索大量数据的应用中。
评论