目录
- 一、查找
- 1、初始条件
- 2、读写判断
- 3、找到bucket
- 4、在bucket中查找key
- 二、赋值
- 1、初始条件
- 2、读写判断
- 3、设置写标识
- 4、找到bucket
- 5、找到可以放置的位置
- 6、搬迁和扩容
- 7、重置读写标识
- 三、删除
- 四、扩容
- 五、总结
之前已经介绍过了map的原理，简单了解一下map里存储的数据结构。本文主要介绍如果在map中进行操作。
本篇减少了在代码中直接注释，用流程的方式摘选了部分精要的代码来解释。
一、查找
元素的查找有三种方式：
- v := m[k]：对应的mapaccess1方法
- v,ok := m[k]：对应的mapaccess2方法
- for k,v := range m：对应的是mapaccessK方法
这几种方法的逻辑基本相同，mapaccessK的逻辑更简单一些。我们主要说一下mapaccess1过程。
1、初始条件
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}判断map是否为空，或者元素个数是否为0，如果是，返回零值。
2、读写判断
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}如果flags是hashWriting，那么表示map是正在写，会报错。不能进行并发写操作。
3、找到bucket
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
top := tophash(hash)先对key进行hash，然后根据这个hash值获取对应bucket号，和tophash值。
如果此时oldbuckets不为空，说明发生了扩容。
如果有扩容发生，oldbuckets中的数据还没有搬迁到newbuckets中，所以要先在oldbuckets中查找。
4、在bucket中查找key
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}在这个bucket及其溢出桶中查找，bucketCnt=8。
遍历桶元素，因为桶中的key是使用连续的存储空间存储，因此可以直接使用bucket+数据偏移量+keysize的大小得到k的位置，如果找到的这个位置和key相同，那么就能以相同的方法得到value。
二、赋值
如果key不存在，那么就需要在bucket对key进行赋值。
1、初始条件
if h == nil {
panic(plainError("assignment to entry in nil map"))
}肯定不能对没有初始化过的map进行赋值
2、读写判断
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}不能进行并发写
3、设置写标识
hash := t.hasher(key, uintptr(h.hash0))
h.flags ^= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}这步标记map进入写状态，不允许进行读操作
4、找到bucket
bucket := hash & bucketMask(h.B)
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)5、找到可以放置的位置
这里分成两种情况
- cell的tophash值和当前tophash值不等，可能会存在一个空槽位
[h0][h1][h2][h3][h4][e][e][e]
after delete
[h0][h1][e ][e ][h5][e][e][e]在执行删除后，可能会在前面留有空位，这里把这个空位记录下来，如果后面没有找到相同的key，就在这里插入
- cell的tophash值和当前tophash值相等，更新它
如果在这个bucket没有找到，就去它的溢出桶中查找
6、搬迁和扩容
这个在下面详细介绍
7、重置读写标识
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}三、删除
删除map中的key ：delete(m, key)
主要流程和查找流程差不多，找到key的位置，清除bucket槽位的key和value
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.ptrdata != 0 {
memclrHasPointers(k, t.key.size)
}如果是指针的话，置nil，如果是值的话，清空内存
四、扩容
为了保证访问效率，在添加、修改或删除key时，都会检查是否扩容。
扩容其实就是空间换时间的过程。
map的扩容条件有两种情况：
1、判断已经达到装载因子，即元素个数 >= 桶总数 * 6.5
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}2、判断溢出桶是否太多。
当桶总数<2^15时，如果溢出桶>=桶总数，则认为溢出桶过多。
当桶总数>215时，当溢出桶>=215，则认为溢出桶过多。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}在某些场景下，比如不断的增删，这样会造成溢出桶增多，但是负载因子不高，没有到达装载因子的临界值，这样就会导致桶的使用率不高，值存得稀疏，查找插入效率低。因此有了第二种情况的判断。
- 增量扩容：针对第一种情况，新建一个bucket，新的bucket大小是原来的2倍，然后oldbuckets搬迁数据到newbuckets。
- 等量扩容：针对第二种情况，不扩大容量，buckets数量不变，重新做一次搬迁数据的操作，把松散的键值对重新排列一次。
在源码中，和扩容相关的主要是hashGrow和growWork函数。
hashGrow函数并没有真正"搬迁"，只是分配好新的buckets，并将老的buckets挂到oldbuckets下。
growWork函数才是真正进行“搬迁”操作，而调用growWork函数的是mapassign和mapdelete中。也就是说在插入、修改、删除key的时候，才会真正尝试进行buckets的“搬迁”工作。它们都会先检查oldbuckets是否“搬迁”完成(oldbuckets == nil)，再决定是否进行搬迁工作。
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 为了确认搬迁的bucket是我们正在使用的bucket
// 即如果当前key映射到老的bucket，那么就搬迁该bucket
evacuate(t, h, bucket&h.oldbucketmask())
// 如果还未完成扩容
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}在搬迁过程中，我们会发现如下问题：
- 如果是等量扩容，那么原key所在的桶和扩容后所在的桶不变，因此可以按照桶号进行搬迁。
- 如果是增量扩容，桶号就有可能发生变化。
所以在evacuate中，有bucket x和bucket y的区别，其实就是增量扩容到原来的2倍，桶的数量是原来的2倍，前半桶为bucket x，后半桶为bucket y。
五、总结
1、map是哈希表实现，通过链地址法解决哈希冲突，核心数据结构是数组加链表。
2、map中定义了2B个桶，每个桶中能容纳8个key。根据key的不同哈希值，将其散落到不同的桶中。哈希值的低位（哈希值的后B个bit位）决定桶号，高位（哈希值的前8位）标识同一个桶中的不同key。桶中8个key是连续存储的，8个value也是连续存储的，是为了内存对齐。
3、当向桶中添加很多key，造成元素过多，超过装载因子所设定的程度，或频繁增删操作，造成溢出桶过多，会触发扩容机制。
扩容分为增量扩容和等量扩容。
- 增量扩容，会增加桶的个数（增加一倍），把原来一个桶中的 keys 被重新分配到两个桶中。
- 等量扩容，不会更改桶的个数，只是会将桶中的数据变得紧凑。 不管是增量扩容还是等量扩容，都需要创建新的桶数组，并不是原地操作的。
4、扩容过程是渐进性的，每次最多搬迁2个bucket，主要是防止扩容需要搬迁的 key 数量过多，引发性能问题。触发扩容的时机是增加了新元素， 桶搬迁的时机则发生在赋值、删除期间。
5、遍历map无序是因为map在扩容后，会发生key的搬迁，这就造成原来在一个bucket中的key，可能搬迁到其他bucket中，所以遍历map肯定不可能按原来的顺序。所以map在遍历的时候，并不是从0号bucket开始，每次都是随机值序号的bucket，再从其中随机的cell开始遍历，然后再按照桶序继续，直到遍历完成。
