go-数据结构-map

map的结构

hmap

• count 当前保存的元素个数
• B 2^B表示桶的数量
• hash0 hash种子，计算hash值用
• buckets 桶，存储map数据
• oldbuckets 旧桶，扩容时使用
• extra 用来管理溢出桶，方便分配和回收复用

溢出桶

• overflow 正在使用的溢出桶
• oldoverflow 扩容时使用
• nextOverflow 指向下一个空闲的溢出桶

bmap

• tophash 存储hash的高8位，（在同一个桶上的hash值高8位相同的概率较低，且不全部存储hash，节约内存，同理低8位来计算bucket的位置）

map的hash冲突

map的哈希冲突是通过在bucket后加溢出桶的方法来解决，当前bucket没有多余位置存储键值时，则从extra里面取一个溢出桶，然后将bucket的尾部地址指向溢出桶的地址，类似链表，再将键值存入

map的新增

• 先生成hash值，然后找到对应的bucket以及生成对应的tophash
• 在对应桶上寻找，若已存在，则直接更新value
• 若未找到，则寻找一个空位置，插入k,v
• 若bucket已满，则从extra处获取一个新的溢出桶链在bucket后边，并将k,v插入