哈希表
-
什么是哈希表瑞躺？
- 散列表（Hash table酱虎，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)幕垦。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄傅联，以加快查找的速度先改。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表蒸走。
- 給定表M仇奶，存在函數(shù)f(key)，對(duì)任意給定的關(guān)鍵字值key比驻，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址该溯，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)别惦。
-
那什么是哈希狈茉？
- Hash，一般是一個(gè)整數(shù)掸掸，通過某種算法氯庆，可以把一個(gè)字符串"壓縮" 成一個(gè)整數(shù)蹭秋，這個(gè)數(shù)稱為Hash，常見的MD5,SHA1等
從這里可以看出來堤撵，我們常用的map或者說dictionary都屬于哈希表里的關(guān)系
那么我們就來簡(jiǎn)單的實(shí)現(xiàn)下仁讨，簡(jiǎn)單的map吧
拉鏈法（鏈地址法）
- 在講解步驟之前，首先說下為什么要用拉鏈法粒督，而不是其他
- 首先拉鏈法的學(xué)習(xí)只需要數(shù)組和鏈表的知識(shí)點(diǎn)即可
- 其次陪竿，拉鏈法很簡(jiǎn)單的就解決了哈希表沖突
- 其特點(diǎn)：
- 數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難屠橄。
- 而鏈表的特點(diǎn)是：尋址困難族跛，插入和刪除容易。
- 所以锐墙，哈希里拉鏈法就是尋址容易礁哄，插入刪除簡(jiǎn)單
實(shí)現(xiàn)步驟
-
//1.首先定義結(jié)構(gòu)體 type MpNode struct { Data Dict // 定義數(shù)據(jù) 數(shù)據(jù)為存放k v 的結(jié)構(gòu)體 Next *MpNode // 下個(gè)節(jié)點(diǎn) } type Dict struct { Key string Value interface{} }//2 初始化 //初始化鏈表的頭節(jié)點(diǎn) func newNodeHead() *MpNode { node := new(MpNode) node.Data.Key = "頭key" node.Data.Value = "頭value" node.Next = nil return node }//鏈方法 //3 封裝結(jié)構(gòu)體對(duì)象方法 // 封裝key value 存放方法 func (node *MpNode) data(k string, v interface{}) *MpNode { if node == nil { node = newNodeHead() } node.Data.Key = k node.Data.Value = v return node }//4 向該鏈空節(jié)點(diǎn)創(chuàng)建新數(shù)據(jù) func (node *MpNode) add(k string, v interface{}) { // 首先判斷k是否是該鏈已有的key 因?yàn)楦鶕?jù)哈希算法簡(jiǎn)化后 同樣的字符串會(huì)在同樣的鏈里存放 if node.getKey(k) != nil { return } //遍歷到尾節(jié)點(diǎn) for node.Next != nil { node = node.Next } // 創(chuàng)建新的尾節(jié)點(diǎn) node.Next = node.Next.data(k, v) }
到這里我們已經(jīng)初步實(shí)現(xiàn)了單鏈里存儲(chǔ)key，value值
-
//5 測(cè)試下添加數(shù)據(jù)是否有問題 func MpDemo() { node := newNodeHead() node.add("1", "2") node.add("2", 3) node.Log()//看下面 fmt.Println(node.Length()) }//6 發(fā)現(xiàn)這樣打印看不太方便 于是寫個(gè)遍歷值 func (node *MpNode) Log() { if node.Next == nil { return } fmt.Println(node.Next.Data) node.Next.Log() }// 7計(jì)算鏈表長(zhǎng)度 防止數(shù)據(jù)堆積 為后續(xù)優(yōu)化做準(zhǔn)備 func (node *MpNode) Length() int { if node == nil { return 0 } i := 0 for node.Next != nil { i++ node = node.Next } return i }//8 開始創(chuàng)建數(shù)組鏈表 也就是哈希表 // 定義數(shù)組鏈表 var Arr [16]*MpNode//9 初始化哈希表 func NewHash() { for i := 0; i < 16; i++ { Arr[i] = newNodeHead() } }//哈希表方法 //10 往表里存key值 func SetKey(k string, v interface{}) { // 存k先判斷存哪里 這里才使用了散列算法計(jì)算 num := hashNum(k) Arr[num].add(k, v) }==這里你會(huì)發(fā)現(xiàn)溪北，欸桐绒，哈希算法怎么寫？于是我找了個(gè)簡(jiǎn)單的之拨，并且能手撕的算法==
//11 獲取16以內(nèi)的散列算法 func hashNum(key string) int { var index int = 0 index = int(key[0]) // 詢價(jià)累積新的數(shù)值 for k := 0; k < len(key); k++ { index *= (1103515245 + int(key[k])) } // 右位移2^27次方 這里可以位移任何數(shù) 只要?jiǎng)e太大導(dǎo)致直接清空 index >>= 27 // 按位& 這里想要求32以內(nèi)就 32-1即可 也就是說 index跟 1111 進(jìn)行& 得到15以內(nèi)的數(shù) 跟11111取余則得31以內(nèi)的數(shù) index &= 16 - 1 return index }//12 根據(jù)key取value func (node *MpNode) getKey(k string) interface{} { if node.Next == nil { return nil } for node.Next != nil { if node.Next.Data.Key == k { return node.Next.Data.Value } else { node = node.Next } } return nil } //13 根據(jù)valve取key 后面發(fā)現(xiàn)如果要寫這個(gè) 就要給每個(gè)數(shù)組都遍歷一遍后 就暫且放棄 等后續(xù)優(yōu)化 //func (node *MpNode) getValue(v interface{}) string { // if node.Next == nil { // return "" // } // for node.Next != nil { // if node.Next.Data.Value == v { // return node.Next.Data.Key // } else { // node = node.Next // } // } // return "" //}//14 取key值 func GetKey(k string) interface{} { num := hashNum(k) return Arr[num].getKey(k) }到目前為止茉继，整個(gè)算法結(jié)構(gòu)已經(jīng)初步完成
運(yùn)行這個(gè)map吧！
-
首先整個(gè)算法在考慮封裝等各種因素蚀乔，對(duì)外只包含3個(gè)方法
- NewHash 創(chuàng)建一個(gè)哈希表
- SetKey 存鍵值對(duì)
- GetKey 取鍵值對(duì)
附上全代碼
package data import "fmt" //1.首先定義結(jié)構(gòu)體 type MpNode struct { Data Dict // 定義數(shù)據(jù) 數(shù)據(jù)為存放k v 的結(jié)構(gòu)體 Next *MpNode // 下個(gè)節(jié)點(diǎn) } type Dict struct { Key string Value interface{} } //8 開始創(chuàng)建數(shù)組鏈表 也就是哈希表 // 定義數(shù)組鏈表 var Arr [16]*MpNode //2 初始化 //初始化鏈表的頭節(jié)點(diǎn) func newNodeHead() *MpNode { node := new(MpNode) node.Data.Key = "頭key" node.Data.Value = "頭value" node.Next = nil return node } //9 初始化哈希表 func NewHash() { for i := 0; i < 16; i++ { Arr[i] = newNodeHead() } } //鏈方法 //3 封裝結(jié)構(gòu)體對(duì)象方法 // 封裝key value 存放方法 func (node *MpNode) data(k string, v interface{}) *MpNode { if node == nil { node = newNodeHead() } node.Data.Key = k node.Data.Value = v return node } //12 根據(jù)key取value func (node *MpNode) getKey(k string) interface{} { if node.Next == nil { return nil } for node.Next != nil { if node.Next.Data.Key == k { return node.Next.Data.Value } else { node = node.Next } } return nil } //13 根據(jù)valve取key 后面發(fā)現(xiàn)如果要寫這個(gè) 就要給每個(gè)數(shù)組都遍歷一遍后 就暫且放棄 等后續(xù)優(yōu)化 //func (node *MpNode) getValue(v interface{}) string { // if node.Next == nil { // return "" // } // for node.Next != nil { // if node.Next.Data.Value == v { // return node.Next.Data.Key // } else { // node = node.Next // } // } // return "" //} //4 向該鏈空節(jié)點(diǎn)創(chuàng)建新數(shù)據(jù) func (node *MpNode) add(k string, v interface{}) { // 首先判斷k是否是該鏈已有的key 因?yàn)楦鶕?jù)哈希算法簡(jiǎn)化后 同樣的字符串會(huì)在同樣的鏈里存放 if node.getKey(k) != nil { return } //遍歷到尾節(jié)點(diǎn) for node.Next != nil { node = node.Next } // 創(chuàng)建新的尾節(jié)點(diǎn) node.Next = node.Next.data(k, v) } //6 發(fā)現(xiàn)這樣打印看不太方便 于是寫個(gè)遍歷值 func (node *MpNode) Log() { if node.Next == nil { return } fmt.Println(node.Next.Data) node.Next.Log() } // 7計(jì)算鏈表長(zhǎng)度 防止數(shù)據(jù)堆積 為后續(xù)優(yōu)化做準(zhǔn)備 func (node *MpNode) Length() int { if node == nil { return 0 } i := 0 for node.Next != nil { i++ node = node.Next } return i } //哈希表方法 //10 往表里存key值 func SetKey(k string, v interface{}) { // 存k先判斷存哪里 這里才使用了散列算法計(jì)算 num := hashNum(k) Arr[num].add(k, v) } //14 取key值 func GetKey(k string) interface{} { num := hashNum(k) return Arr[num].getKey(k) } //11 獲取16以內(nèi)的散列算法 func hashNum(key string) int { var index int = 0 index = int(key[0]) // 詢價(jià)累積新的數(shù)值 for k := 0; k < len(key); k++ { index *= (1103515245 + int(key[k])) } // 右位移2^27次方 這里可以位移任何數(shù) 只要?jiǎng)e太大導(dǎo)致直接清空 index >>= 27 // 按位& 這里想要求32以內(nèi)就 32-1即可 也就是說 index跟 1111 進(jìn)行& 得到15以內(nèi)的數(shù) 跟11111取余則得31以內(nèi)的數(shù) index &= 16 - 1 return index } //5 測(cè)試下添加數(shù)據(jù)是否有問題 func MpDemo() { //node := newNodeHead() //node.add("1", "2") //node.add("2", 3) //node.Log() //fmt.Println(node.Length()) }
