Golang 程序实现带有独立链接的哈希表
在计算机科学中，哈希表是快速数据检索的关键数据结构。它也被称为 hashmap，它基于键值对存储和检索数据。在本文中，我们将在 Go 中实现带有独立链接的哈希表。在下面演示的示例中，我们将执行初始化、插入和显示哈希表等操作。
解释
作为一种数据结构，哈希表中的每个槽都有一个链接列表，其中包含散列到同一索引的项目，使独立链接成为一种冲突解决策略。在这种方法中，许多项目可能共享相同的索引，并且通过使用链接列表可以避免冲突。
这里我们有一个带有相应数组索引的哈希表以供理解:
Array Index: 0 1 2 3 4 Hash Table: | | | | | |
现在，如果我们想使用键从值开始，我们需要将键传递给哈希函数，它将生成一个索引来存储值，我们假设索引为 2。
要检索值，直接使用哈希函数查找索引并访问索引处的值。
Array Index: 0 1 2 3 4
Hash Table: | | |fruit| | |
^ key
value: "apple"
Retrieve("fruit"):
Array Index: 0 1 2 3 4
Hash Table: | | |fruit| | |
^ key
value: "apple"
这是使用简单哈希函数模拟哈希表操作，最初我们有一个基于数组的哈希表，其中有空槽，然后我们使用基于键确定其索引的哈希函数将键值对"apple"添加到哈希表中，要检索具有键水果的值，请使用哈希函数查找存储值的索引，您将找到该值。
语法
func Initialize(size int) *HashTable
语法定义了一个名为 Initialize 的函数，该函数为哈希表分配内存，设置其大小，并通过接受整数大小作为输入并返回指向 HashTable 结构的指针来初始化用于单独链接的内部映射。
func (ht *HashTable) HashCode(key int) int
该语法定义了一个名为 HashCode 的函数，该函数接受一个整数键作为输入，并使用哈希表大小的模数运算返回应放置键值对的索引。
算法
首先，我们将使用链接列表数组填充哈希表。
要计算哈希码，请提供一个键。
要将哈希码映射到数组中的索引，请使用模数运算。
将元素插入链接列表中计算出的索引处。
在检索过程中，计算哈希码，找到索引处的链接列表，然后搜索元素。
示例 1
在此示例中，在Go，我们使用包含链接列表节点数组的 HashTable 结构构建一个具有单独链接的哈希表以解决冲突，这些节点用于存储键值对。Initialize 函数初始化哈希表，HashCode 方法使用模运算计算索引，而 Insert 函数添加元素，通过链接节点处理冲突。在主函数中，创建了一个哈希表，插入了元素，并显示生成的哈希表，演示了使用单独链接的冲突解决机制。
package main
import "fmt"
type KeyValuePair struct{ Key, Value int }
type Node struct{ Data KeyValuePair; Next *Node }
type HashTable struct{ Size int; Table []*Node }
func Initialize(size int) *HashTable { return &HashTable{size, make([]*Node, size)} }
func (ht *HashTable) HashCode(key int) int { return key % ht.Size }
func (ht *HashTable) Insert(key, value int) {
index := ht.HashCode(key)
node := &Node{Data: KeyValuePair{key, value}}
if ht.Table[index] == nil { ht.Table[index] = node } else { current := ht.Table[index]; for current.Next != nil { current = current.Next }; current.Next = node }
}
func DisplayHashTable(ht *HashTable) {
for index, node := range ht.Table {
fmt.Printf("Index %d:", index)
for current := node; current != nil; current = current.Next {
fmt.Printf(" -> (%d, %d)", current.Data.Key, current.Data.Value)
}
fmt.Println()
}
}
func main() {
hashTable := Initialize(10)
hashTable.Insert(5, 42)
hashTable.Insert(13, 78)
hashTable.Insert(26, 91)
hashTable.Insert(39, 104)
hashTable.Insert(42, 117)
fmt.Println("插入后的哈希表:")
DisplayHashTable(hashTable)
}
输出
插入后的哈希表: Index 0: Index 1: Index 2: -> (42, 117) Index 3: -> (13, 78) Index 4: Index 5: -> (5, 42) Index 6: -> (26, 91) Index 7: Index 8: Index 9: -> (39, 104)
示例 2
在此示例中，使用 go 实现哈希表，用于创建具有单独链接的哈希表的 HashTable 结构由整数键到整数值切片的映射组成。Initialize 函数创建具有给定大小的哈希表，HashCode 方法使用模运算计算索引，而 Insert 方法将值插入哈希表中，通过将值附加到现有索引来解决冲突。在主函数中，创建哈希表，插入值，并显示考虑单独链接的哈希表的最终状态。
package main
import (
"fmt"
)
type HashTable struct {
Size int
Table map[int][]int
}
func Initialize(size int) *HashTable {
table := make(map[int][]int)
return &HashTable{Size: size, Table: table}
}
func (ht *HashTable) HashCode(key int) int {
return key % ht.Size
}
func (ht *HashTable) Insert(key int, value int) {
index := ht.HashCode(key)
if ht.Table[index] == nil {
ht.Table[index] = []int{value}
} else {
ht.Table[index] = append(ht.Table[index], value)
}
}
func DisplayHashTable(ht *HashTable) {
for index, values := range ht.Table {
fmt.Printf("Index %d: %v\n", index, values)
}
}
func main() {
hashTable := Initialize(10)
hashTable.Insert(5, 42)
hashTable.Insert(13, 78)
hashTable.Insert(26, 91)
hashTable.Insert(39, 104)
hashTable.Insert(42, 117)
fmt.Println("插入后的哈希表:")
DisplayHashTable(hashTable)
}
输出
插入后的哈希表: Index 5: [42] Index 3: [78] Index 6: [91] Index 9: [104] Index 2: [117]
实际实施
图书馆目录:图书馆通常使用具有独立链接的哈希表来处理这些记录。每本书的唯一标识符(例如 ISBN)都可能由哈希表分配一个索引。图书馆采用单独的链接来正确处理在哈希过程中为许多卷分配相同索引的情况。此方法可确保有效地排列和检索书籍。
Web 应用程序中的用户会话:在线应用程序中的用户会话通常使用具有独立链接的哈希表来管理。为了有效地获取自己的会话数据，每个用户的会话 ID 都可能受到哈希方法的影响。单独链接可确保正确存储和检索多个用户的会话，即使他们的 ID 在哈希过程中产生相同的索引。
结论
哈希表是用于高效数据检索和存储的基本数据结构，通过将键映射到数组中的索引，可以快速访问值。单独链接是用于处理哈希表中冲突的常用技术之一。在本文中，我们已经看到了在 Go 中实现哈希表的两种方法。第一种方法是使用链接列表数组，在数组内组织元素，直接寻址索引以进行检索。第二种方法是使用映射，提供动态键值配对，适应不同的冲突，在保持有效数据访问的同时潜在地减少内存使用量。
