資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究使用分離連結法實現雜湊表的Go語言程式
在計算機科學中，雜湊表是一種用於快速資料檢索的關鍵資料結構。它也稱為雜湊對映，它基於鍵值對儲存和檢索資料。在本文中，我們將使用獨立連結法在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”新增到雜湊表中。要檢索鍵為“fruit”的值，請使用雜湊函式查詢儲存該值的索引，你就能找到該值。
語法
func Initialize(size int) *HashTable
該語法定義了一個名為`Initialize`的函式，該函式為雜湊表分配記憶體，設定其大小，並透過接受一個整數大小作為輸入並返回指向`HashTable`結構的指標來初始化用於分離連結的內部對映。
func (ht *HashTable) HashCode(key int) int
該語法定義了一個名為`HashCode`的函式，該函式接受一個整數鍵作為輸入，並使用雜湊表大小的模運算返回鍵值對應該放置的索引。
演算法
首先，我們將使用連結串列陣列填充雜湊表。
要計算雜湊碼，請提供一個鍵。
要將雜湊碼對映到陣列中的索引，請使用模運算。
將元素插入到連結串列中計算出的索引處。
在檢索過程中，計算雜湊碼，查詢索引處的連結串列，然後搜尋元素。
示例1
在這個示例中，為了在Go語言中實現雜湊表，我們構建了一個使用分離連結法解決衝突的雜湊表。它使用一個`HashTable`結構，該結構包含一個連結串列節點陣列，這些節點用於儲存鍵值對。`Initialize`函式初始化雜湊表，`HashCode`方法使用模運算計算索引，而`Insert`函式新增元素，透過連結節點處理衝突。在`main`函式中，建立一個雜湊表，插入元素，並顯示生成的雜湊表，演示了使用分離連結法的衝突解決機制。
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("Hash Table after insertions:")
DisplayHashTable(hashTable)
}
輸出
Hash Table after insertions: 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`方法將值插入雜湊表，透過將值附加到現有索引來處理衝突。在`main`函式中，建立雜湊表，插入值，並顯示雜湊表的最終狀態，其中考慮了分離連結。
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("Hash Table after insertions:")
DisplayHashTable(hashTable)
}
輸出
Hash Table after insertions: Index 5: [42] Index 3: [78] Index 6: [91] Index 9: [104] Index 2: [117]
現實生活中的應用
圖書館目錄：圖書館經常使用帶有獨立連結的雜湊表來處理這些記錄。每本書的唯一識別符號（例如ISBN）都可以由雜湊表分配一個索引。當在雜湊過程中許多卷被分配相同的索引時，圖書館使用分離連結來正確處理這些情況。這種方法確保書籍得到有效地組織和檢索。
Web應用程式中的使用者會話：Web應用程式中的使用者會話通常使用帶有分離連結的雜湊表來管理。為了有效地獲取他們自己的會話資料，每個使用者的會話ID都可以進行雜湊處理。即使使用者的ID在雜湊過程中導致相同的索引，分離連結也能確保多個使用者的會話得到正確儲存和檢索。
結論
雜湊表是用於高效資料檢索和儲存的重要資料結構，它透過將鍵對映到陣列中的索引來實現，從而允許快速訪問值。分離連結是用於處理雜湊表中衝突的常用技術之一。在本文中，我們看到了在Go語言中實現雜湊表的兩種方法。第一種方法使用連結串列陣列，在陣列中組織元素，直接定址索引進行檢索。第二種方法使用對映，提供動態的鍵值對，適應不同的衝突，可能減少記憶體使用，同時保持有效的資料訪問。
226 次瀏覽
