实际上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.
查找元素也是大同小异。