在golang中map是經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)趾牧。在這篇中我會從基礎(chǔ)校辩、算法颓鲜、源碼角度去分析map中的設(shè)計思想程腹。
1 基礎(chǔ)部分
1.1 聲明
var m map[string]string
此時 m == nil
1.2 創(chuàng)建
-
make
m := make(map[string]int)
-
字面量
ages := map[string]int{
"xitehip":18
"zuan":2
}
//或者
ages := make(map[string]int)
ages["xitehip"] = 18
1.3 key 類型范圍
- key是引用類型
- key不可以是：slice扰楼、map 刃泌、 func 顾彰。因為這3個類型是不可比較類型缤沦。
1.4 增刪改查
// 新增
m["name"] = "xitehip"
// 刪除塘偎，key不存在則什么也不干疗涉，不會報錯。
delete(m, "xitehip")
// 更新
m["name"] = "zuan"
// 查詢吟秩，key不存在返回value類型的零值
i := m["name"]
i, ok := m["name"]
_, ok := m["name"]
1.5 類型咱扣、長度、比較
- 引用類型
- 長度用len(map)獲取
- 和slice峰尝，func一樣不可以用==來比較
1.6 遍歷
- for range遍歷偏窝。
- 無序。
1.7 函數(shù)傳參
- 引用類型傳參武学，傳遞的是地址的拷貝祭往，擴(kuò)容時也不會改變這個地址。
2 算法
- 哈希算法：將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串火窒。
- 哈希表：其實就是對數(shù)組支持下標(biāo)隨機(jī)訪問的運(yùn)用硼补，結(jié)合哈希算法就能夠得到一張哈希表。
- map中用的是hash table來查找數(shù)據(jù)的熏矿，再根據(jù)鏈表去解決hash沖突問題已骇。
- 沖突解決：有開放尋址法和鏈表法，由于golang是用的鏈表法票编，所以下面解釋一下褪储。
- 鏈表法：每個桶中從存放的具體的值變成了指針，其指向了一個鏈表慧域，主要目的是解決不同key哈希出來的值相同的問題鲤竹，這樣就可以通過hash值找到桶的位置，然后根據(jù)key的值遍歷得到具體的值昔榴。
- 時間復(fù)雜度：由于哈希表具體存在鏈表上辛藻，所以插入的時間復(fù)雜度為o(1),刪除更新需要遍歷鏈表，所以是o(n)互订。
- golang中使用的hash算法根據(jù)硬件選擇吱肌，如果cpu支持aes，那么使用aes hash仰禽，否則使用memhash氮墨。用位運(yùn)算避免mod的時對cpu多次的計算纺蛆。
3 底層源碼
3.1 map查找過程
見下圖1
圖1
按照圖片箭頭上標(biāo)注的數(shù)字順序解釋：
- 將key9=xitehip傳遞給hash函數(shù)。
- hash函數(shù)hash之后生成一個無符號的64位整數(shù)勇边，然后轉(zhuǎn)換成64位二進(jìn)制數(shù)犹撒。
- 取后5位（00011）轉(zhuǎn)換成整數(shù)3然后去hmap中的buckets的指針找到[]bmap，然后根據(jù)下標(biāo)3定位到具體的bmap地址（len([]bmap=32)）粒褒。
- 然后根據(jù)[3]bmp中的地址找到具體bmap數(shù)據(jù)。
- 根據(jù)剛才的hash之后得到的64位二進(jìn)制數(shù)的前8位（1100100）轉(zhuǎn)換得到的整數(shù)200诚镰，然后根據(jù)200去遍歷里面8個tophash奕坟，看是否有等于200的，發(fā)現(xiàn)沒有清笨。
- 根據(jù)bmap1中的overflow指針找到下一個也就是bmap2月杉，然后同操作5進(jìn)行遍歷，發(fā)現(xiàn)tophash中有200表明匹配成功抠艾，因為200是1號位所以去key的1號位查找是否等于xitehip苛萎，確認(rèn)是相等，然后就可以確定val的值在val的1號位就是我們找的val(其中等于18）检号。
3.2 map的插入更新刪除（不包括擴(kuò)容情況）
- 刪除和更新都要縣查找到對應(yīng)的key
- 更新如果沒有找到就在空位置插入數(shù)據(jù)也即是插入腌歉，如果找到了就更新對應(yīng)的val
- 刪除如果沒有找到則什么也不做，如果找到了則將對應(yīng)的key和val清空齐苛，但是不釋放內(nèi)存翘盖。
3.3 擴(kuò)容
參見下邊參考文章
