基本語法
定義hashmap變量
由于go語言是一個強類型的語言姑食，因此hashmap也是有類型的褥紫，具體體現(xiàn)在key和value都必須指定類型，比如聲明一個key為string，value也是string的map，
需要這樣做
var m map[string]string // 聲明一個hashmap蒋腮，還不能直接使用，必須使用make來初始化
m = make(map[string]string) // 初始化一個map
m = make(map[string]string, 3) // 初始化一個map并附帶一個可選的初始bucket（非準(zhǔn)確值藕各，只是有提示意義）
m := map[string]string{} // 聲明并初始化
m := make(map[string]string) // 使用make來初始化
大部分類型都能做key池摧，某些類型是不能的，共同的特點是：不能使用==來比較激况，包括: slice, map, function
get,set,delete
m := map[string]int
m["a"] = 1
fmt.Println(m["a"]) // 輸出 1
// 如果訪問一個不存在的key作彤，返回類型默認(rèn)值
fmt.Println(m["b"]) // 輸出0
// 測試key是否存在
v, ok := m["b"]
if ok {
...
}
// 刪除一個key
delete(m, "a")
迭代器
// 只迭代key
for k := range m {
...
}
// 同時迭代key-value
for k, v := range m {
...
}
在迭代的過程中是可以對map進(jìn)行刪除和更新操作的，規(guī)則如下：
- 迭代是無序的誉碴，跟插入是的順序無關(guān)
- 迭代的過程中刪除一個key宦棺，無論遍歷還是沒有遍歷過都不會再遍歷到
- 迭代的過程中添加一個key，不確定是否能遍歷到
- 未初始化的map也可以迭代
其他
- map的value是不可取地址的黔帕，意味著 &m["a"]這樣的語法是非法的
- len和cap分別可以獲取當(dāng)前map的kv個數(shù)和總?cè)萘?/li>
內(nèi)部結(jié)構(gòu)
hashmap結(jié)構(gòu)
golang的map是hash結(jié)構(gòu)的，意味著平均訪問時間是O(1)的蹈丸。同傳統(tǒng)的hashmap一樣成黄，由一個個bucket組成:
// A header for a Go map.
type hmap struct {
// Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and
// ../reflect/type.go. Don't change this structure without also changing that code!
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
// If both key and value do not contain pointers and are inline, then we mark bucket
// type as containing no pointers. This avoids scanning such maps.
// However, bmap.overflow is a pointer. In order to keep overflow buckets
// alive, we store pointers to all overflow buckets in hmap.overflow.
// Overflow is used only if key and value do not contain pointers.
// overflow[0] contains overflow buckets for hmap.buckets.
// overflow[1] contains overflow buckets for hmap.oldbuckets.
// The first indirection allows us to reduce static size of hmap.
// The second indirection allows to store a pointer to the slice in hiter.
overflow *[2]*[]*bmap
}
bucket內(nèi)部
// A bucket for a Go map.
type bmap struct {
tophash [bucketCnt]uint8 // Followed by bucketCnt keys and then bucketCnt values.
// NOTE: packing all the keys together and then all the values together makes the
// code a bit more complicated than alternating key/value/key/value/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
根據(jù)一個key得到value
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
maptype為map的類型信息，是編譯器在編譯期靜態(tài)生成的逻杖，里面包含了map的一些元信息奋岁，比如 key和value的類型信息等等
- *hmap為map的header，即map的引用
- key是一個通用的指針荸百，代表了key的引用
- 返回值為一個指針闻伶，指向?qū)?yīng)的value引用
hash計算找到bucket
那我們怎么訪問到對應(yīng)的bucket呢，我們需要得到對應(yīng)key的hash值
alg := t.key.alghash := alg.
hash(key, uintptr(h.hash0))
m := uintptr(1)<<h.B - 1
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
根據(jù) tophash 和 key 定位到具體的 bucket
- tophash 可以快速試錯够话，如果 tophash 不相等直接跳過
- tophash 相等的話蓝翰，根據(jù) key 的比較來判斷是否相等，如果相等則找到
- 如果當(dāng)前 bucket 都試玩還沒有找到女嘲，則調(diào)到下一個 bucket
擴(kuò)容
各個參數(shù)的意思：
- %overflow 溢出率畜份，平均一個 bucket 有多少個 kv 的時候會溢出
- bytes/entry 平均存一個 kv 需要額外存儲多少字節(jié)的數(shù)據(jù)
- hitprobe 找到一個存在的 key 平均需要找?guī)紫?/li>
- missprobe 找到一個不存在的 key 平均需要找?guī)紫?/li>
目前采用的是這一行:
作者丨icexin
鏈接丨http://t.cn/RCXgEjr
