原理

我們都知道怎么使用goLang中的map來存儲鍵值對類型的數(shù)據(jù)，但是它的內(nèi)部實(shí)現(xiàn)是怎么樣的？

其實(shí)map是一種HashMap，表面上看它只有鍵值對結(jié)構(gòu)，實(shí)際上在存儲鍵值對的過程中涉及到了數(shù)組和鏈表。HashMap之所以高效，是因為其結(jié)合了順序存儲(數(shù)組)和鏈?zhǔn)酱鎯?鏈表)兩種存儲結(jié)構(gòu)。數(shù)組是HashMap的主干，在數(shù)組下有有一個類型為鏈表的元素。

這是一個簡單的HashMap的結(jié)構(gòu)圖：

HashMap結(jié)構(gòu)

當(dāng)我們存儲一個鍵值對時，HashMap會首先通過一個哈希函數(shù)將key轉(zhuǎn)換為數(shù)組下標(biāo)，真正的key-value是存儲在該數(shù)組對應(yīng)的鏈表里。

HashMap的數(shù)組往往是有限的，那當(dāng)要存儲的鍵值對很多數(shù)組不夠或者兩個鍵值對哈希運(yùn)算后的值相同時，不就會有不同的鍵值對存儲在同一個數(shù)組下嗎？是的，這個就叫做哈希碰撞。當(dāng)發(fā)生哈希碰撞時，鍵值對就會存儲在該數(shù)組對應(yīng)鏈表的下一個節(jié)點(diǎn)上。

盡管這樣，HashMap的操作效率也是很高的。當(dāng)不存在哈希碰撞時查找復(fù)雜度為O(1)，存在哈希碰撞時復(fù)雜度為O(N)。所以，但從性能上講HashMap中的鏈表出現(xiàn)越少，性能越好；當(dāng)然，當(dāng)存儲的鍵值對非常多時，從存儲的角度鏈表又能分擔(dān)一定的壓力。

代碼實(shí)現(xiàn)

KVMap

首先，HashMap存儲的是鍵值對，所以需要一個鍵值對類型。

//鏈表結(jié)構(gòu)里數(shù)據(jù)的數(shù)據(jù)類型 鍵值對typeKVstruct{? ? KeystringValuestring}

LinkNode

鍵值對又是主要存儲在鏈表里的，所以需要一個鏈表類。

//鏈表結(jié)構(gòu)typeLinkNodestruct{//節(jié)點(diǎn)數(shù)據(jù)Data KV//下一個節(jié)點(diǎn)NextNode *LinkNode}//創(chuàng)建只有頭結(jié)點(diǎn)的鏈表funcCreateLink()*LinkNode{//頭結(jié)點(diǎn)數(shù)據(jù)為空 是為了標(biāo)識這個鏈表還沒有存儲鍵值對varlinkNode = &LinkNode{KV{"",""},nil}returnlinkNode}

當(dāng)發(fā)生哈希碰撞時，鍵值對會存儲在新建的鏈表節(jié)點(diǎn)上。這里需要一個添加節(jié)點(diǎn)的功能，我們這里采用尾插法添加節(jié)點(diǎn)。

//尾插法添加節(jié)點(diǎn),返回鏈表總長度func(link *LinkNode)AddNode(dataKV) int {varcount=0//找到當(dāng)前鏈表尾節(jié)點(diǎn)tail := linkfor{count+=1iftail.NextNode==nil{break}else{? ? ? ? ? ? tail = tail.NextNode}? ? }varnewNode = &LinkNode{data,nil}? ? tail.NextNode= newNodereturncount+1}

HashMap

接下來，就是豬腳HashMap登場了。

//HashMap木桶(數(shù)組)的個數(shù)constBucketCount? =16typeHashMapstruct{//HashMap木桶Buckets [BucketCount]*LinkNode}//創(chuàng)建HashMapfuncCreateHashMap()*HashMap{? ? myMap := &HashMap{}//為每個元素添加一個鏈表對象fori :=0; i < BucketCount ; i++? {? ? ? ? myMap.Buckets[i] = CreateLink()? ? }returnmyMap}

我們需要一個哈希散列算法，將key轉(zhuǎn)化為一個0-BucketCount的整數(shù)，作為存放它的數(shù)組的下標(biāo)。這里這個散列算法，應(yīng)盡可能隨機(jī)地使新增的鍵值對均勻地分布在每個數(shù)組下。

一般像go的map和Java的HashMap都會有一個復(fù)雜的散列算法來達(dá)到這個目的，我們這里只是為了講HashMap原理，暫且就用一個簡單的方法來求出下標(biāo)。

//自定義一個簡單的散列算法，它可以將不同長度的key散列成0-BucketCount的整數(shù)funcHashCode(keystring)int{varsum =0fori :=0; i

往HashMap里添加鍵值對在這里順便給大家推薦一個架構(gòu)交流群：617434785，里面會分享一些資深架構(gòu)師錄制的視頻錄像：有Spring，MyBatis，Netty源碼分析，高并發(fā)、高性能、分布式、微服務(wù)架構(gòu)的原理，JVM性能優(yōu)化這些成為架構(gòu)師必備的知識體系。還能領(lǐng)取免費(fèi)的學(xué)習(xí)資源。相信對于已經(jīng)工作和遇到技術(shù)瓶頸的碼友，在這個群里會有你需要的內(nèi)容。

//添加鍵值對func(myMap *HashMap)AddKeyValue(keystring, valuestring){//1.將key散列成0-BucketCount的整數(shù)作為Map的數(shù)組下標(biāo)varmapIndex = HashCode(key)//2.獲取對應(yīng)數(shù)組頭結(jié)點(diǎn)varlink = myMap.Buckets[mapIndex]//3.在此鏈表添加結(jié)點(diǎn)iflink.Data.Key ==""&& link.NextNode ==nil{//如果當(dāng)前鏈表只有一個節(jié)點(diǎn)，說明之前未有值插入? 修改第一個節(jié)點(diǎn)的值 即未發(fā)生哈希碰撞link.Data.Key = key? ? ? ? link.Data.Value = value? ? ? ? fmt.Printf("node key:%v add to buckets %d first node\n", key, mapIndex)? ? }else{//發(fā)生哈希碰撞index := link.AddNode(KV{key, value})? ? ? ? fmt.Printf("node key:%v add to buckets %d %dth node\n", key, mapIndex, index)? ? }}

根據(jù)鍵從HashMap里取出對應(yīng)的值

//按鍵取值func(myMap *HashMap)GetValueForKey(keystring)string{//1.將key散列成0-BucketCount的整數(shù)作為Map的數(shù)組下標(biāo)varmapIndex = HashCode(key)//2.獲取對應(yīng)數(shù)組頭結(jié)點(diǎn)varlink = myMap.Buckets[mapIndex]varvaluestring//遍歷找到key對應(yīng)的節(jié)點(diǎn)head := linkfor{ifhead.Data.Key == key {? ? ? ? ? ? value = head.Data.Valuebreak}else{? ? ? ? ? ? head = head.NextNode? ? ? ? }? ? }returnvalue}

Main_test

packagemainimport("chaors.com/LearnGo/BlockchainCryptography/HashMap")funcmain(){? ? myMap := HashMap.CreateHashMap()? ? myMap.AddKeyValue("001","1")? ? myMap.AddKeyValue("002","2")? ? myMap.AddKeyValue("003","3")? ? myMap.AddKeyValue("004","4")? ? myMap.AddKeyValue("005","5")? ? myMap.AddKeyValue("006","6")? ? myMap.AddKeyValue("007","7")? ? myMap.AddKeyValue("008","8")? ? myMap.AddKeyValue("009","9")? ? myMap.AddKeyValue("010","10")? ? myMap.AddKeyValue("011","11")? ? myMap.AddKeyValue("012","12")? ? myMap.AddKeyValue("013","13")? ? myMap.AddKeyValue("012","14")? ? myMap.AddKeyValue("015","15")}

RUN

main_test.png

一個簡單的HashMap就實(shí)現(xiàn)了，雖然我們的散列算法只是用了一個簡單的轉(zhuǎn)換算法，這對我們理解HashMap原理已經(jīng)足夠了。