實際上Go的map和Java7之前的HashMap, 非常相似。都是Array + LinkedTable的結構。
結構
map數據結構由runtime/map.go/hmap定義:
1
2type hmap struct {
3 count int // 當前保存的元素個數
4 ...
5 B uint8 // 指示bucket數組的大小
6 ...
7 buckets unsafe.Pointer // bucket數組指針，數組的大小為2^B
8 ...
9}
bucket數據結構由runtime/map.go/bmap定義：
1
2type bmap struct {
3 tophash [8]uint8 //存儲哈希值的高8位
4 data byte[1] //key value數據:key/key/key/.../value/value/value...
5 overflow *bmap //溢出bucket的地址
6}
這裡使用的數組對齊方式來存放數據。overflow指向下一個bucket.
工作流程
首先通過key計算Hash值，通過Hash的低位，計算出該元素需要存放在buckets中的哪一個bucket.
如果Hash衝突，也就是當前bucket已經有人進去了。那麼就使用該bucket的overflow指向自己的bucket.
查找元素也是大同小異。