hash散列表

哈希表（也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
下面我們來(lái)寫(xiě)一個(gè)簡(jiǎn)單的hash散列表，首先對(duì)上一節(jié)中的代碼我們做一些改進(jìn)，在這里我們聲明一個(gè)結(jié)構(gòu)體類型，作為幾點(diǎn)數(shù)據(jù)的類型，然后對(duì)代碼的參數(shù)進(jìn)行一些修改。

package LinkNodesimport ("fmt" )//用結(jié)構(gòu)體做數(shù)據(jù)域的類型 type DM struct {K stringV string }//聲明全局變量，保存頭節(jié)點(diǎn) var head *Node var curr *Node //當(dāng)前節(jié)點(diǎn)//聲明節(jié)點(diǎn)類型 type Node struct {//數(shù)據(jù)域Data DM//地址域NextNode *Node }//創(chuàng)建頭節(jié)點(diǎn) func CreateHeadNode(k string, v string) *Node {var node *Node = new(Node)// 設(shè)置數(shù)據(jù)結(jié)構(gòu)體中的數(shù)據(jù)域node.Data.K = knode.Data.V = v//設(shè)置地址域node.NextNode = nil//保存頭節(jié)點(diǎn)head = nodecurr = nodereturn node }//在指定的節(jié)點(diǎn)（curr）添加新節(jié)點(diǎn) func AddNode(k string, v string, curr *Node) *Node {var newNode *Node = new(Node)//設(shè)置新節(jié)點(diǎn)重的數(shù)據(jù)域newNode.Data.K = knewNode.Data.V = v//設(shè)置地址域newNode.NextNode = nil//掛接節(jié)點(diǎn)curr.NextNode = newNodecurr = newNodereturn newNode }//在指定的節(jié)點(diǎn)后遍歷鏈表 func ShowNodes(n *Node) {var node = nfor {if node.NextNode == nil {fmt.Println(node.Data)break} else {fmt.Println(node.Data)node = node.NextNode}} }//計(jì)算節(jié)點(diǎn)的個(gè)數(shù) func NodeCnt() int {var cnt = 1var node = headfor {if node.NextNode == nil {break} else {node = node.NextNodecnt++}}return cnt }

接下來(lái)我們來(lái)創(chuàng)建一個(gè)新的文件夾HashMp,然后創(chuàng)建新的文件MyHashMap.go，在這里我們聲明一個(gè)長(zhǎng)度為16的數(shù)組，如果想改成32或者64等其他長(zhǎng)度的數(shù)組，要對(duì)散列算法進(jìn)行更改。

package HashMpimport ("MyHashMap/LinkNodes""fmt" )//聲明全局?jǐn)?shù)組 var bultArr [16]*LinkNodes.Node//給數(shù)組初始化 func CreateBulet() {var arr = [16]*LinkNodes.Node{}for i := 0; i < 16; i++ {arr[i] = LinkNodes.CreateHeadNode("頭節(jié)點(diǎn)", "頭節(jié)點(diǎn)")}bultArr = arr }//將key轉(zhuǎn)換成數(shù)組下標(biāo)的散列算法 func HashCode(key string) int {var index int = 0index = int(key[0])for k := 0; k < len(key); k++ {//1103515245是十六位的hash因子散列值index *= (1103515245 + int(key[k]))}index >>= 27index &= 16 - 1return index }//向數(shù)組中添加健值對(duì) func AddKeyValue(k string, v string) {//計(jì)算建所對(duì)應(yīng)的木桶下表var pos = HashCode(k)//獲得木桶數(shù)組var head *LinkNodes.Node = bultArr[pos]//向指定下標(biāo)的頭節(jié)點(diǎn)添加節(jié)點(diǎn)LinkNodes.AddNode(k, v, head) }//獲取數(shù)據(jù) func GetValueByKey(k string) string {var pos = HashCode(k)var head *LinkNodes.Node = bultArr[pos]//通過(guò)頭節(jié)點(diǎn)遍歷列表//LinkNodes.ShowNodes(head)//查找對(duì)應(yīng)下標(biāo)下的鏈表，判斷在key域節(jié)點(diǎn)中的key一致時(shí)打印for {if head.Data.K == k {fmt.Println(head.Data.V)break} else {head = head.NextNodeif head.NextNode == nil {}} } return ""}

在主函數(shù)中使用方法：

package mainimport ("MyHashMap/HashMp""fmt" )func main() {fmt.Println("Hello World!")//測(cè)試hashMp八下的散列因子是否平均分布//fmt.Println(HashMp.HashCode("三羊"))HashMp.CreateBulet()HashMp.AddKeyValue("abc","hello")HashMp.AddKeyValue("bcd","world")HashMp.GetValueByKey("bcd") }

輸出內(nèi)容為：

Hello World!world

總結(jié)

以上是生活随笔為你收集整理的密码学-hash散列表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。