深入理解golang map_飞道的博客

深入理解golang map

2021-05-13 08:25 195人阅读评论(0)

golang map

版本

go1.14

正确使用

func main() {
	var m map[int]string
	// 初始化map
	// [问题1] make初始化map时指定size和不指定size有什么区别
	m = make(map[int]string)
	m[0] = "hello"
	m0, ok := m[0]
	if ok {
		fmt.Println("get m0:", m0)
	}
	m1, ok := m[1]
	if ok {
		fmt.Println("get m1:", m1)
	}
	for k, v := range m {
		fmt.Printf("k:%d,v:%s\n", k, v)
	}
}

输出结果：

get m0: hello
k:0,v:hello

错误使用

map没有进行初始化进行赋值，会引发panic

func main() {
	var m map[int]string
	m[0] = "hello"
}

输出结果：

panic: assignment to entry in nil map

在不加锁的情况下，对map进行并发读写

func main() {
	m := make(map[int]int)
	// 开启一个协程对map进行写操作
	go func() {
		for i := 0; i < 1000; i++ {
			m[i] = i
		}
	}()
	// 开启一个协程对map进行读操作
	go func() {
		for i := 0; i < 1000; i++ {
			fmt.Println(m[i])
		}
	}()
	time.Sleep(10 * time.Second)
}

输出结果：

fatal error: concurrent map read and map write

编程实践

map在使用前必须初始化，即使用make构建map对象。
确保用key读取到map的元素有效。
map是并发不安全的，在并发情况下，使用锁或者sync.Map确保并发安全。
make申请map时，根据预估大小来申请合适内存

map的数据结构

【hmap】

src/runtime/map.go

// map结构体
type hmap struct {
   count     int 	// 元素个数
   flags     uint8
   B         uint8  // 表示桶的个数，桶的个数等于2^B个
   noverflow uint16 // 溢出桶的数量
   hash0     uint32 // 32位的hash值

   buckets    unsafe.Pointer // 桶
   oldbuckets unsafe.Pointer // 旧桶的数组，在扩容的时候会用到
   nevacuate  uintptr        // 标识的是搬迁的位置(也可以考虑为搬迁的进度）

   extra *mapextra	// 额外信息
}

【bmap】

// 桶
type bmap struct {
   tophash [8]uint8	//tophash表示这个桶所存放的key的hash值的top部分，每个桶最多可以表示8个tophash，可以存放8组key-vale。用hash的前8位表示tophash。
}

【mapextra】

// mapextra holds fields that are not present on all maps.
// 如果map的key和elem都不是指针类型，就把这个桶标记为不含指针的，从而避免扫描这个此类map。然而，bmap.overflow是一个指针，为了保持overflow存活，将指向所有overflow桶的指针存储在在hmap.extra.overflow和hmap.extra.oldoverflow中。
overflow和oldoverflow只有在map的key和elem都不是指针的时候才会使用。
type mapextra struct {
   // 包含hmap.Buckets的指针
   overflow    *[]*bmap
   // 包含hmap.OldBuckets的指针
   oldoverflow *[]*bmap

   // 指向下一个空闲的桶
   nextOverflow *bmap
}

初始化

【makemap_small && makemap】

src/runtime/map.go

// 当使用make不指定size或size<=8时，使用makemap_small
// 初始化一个hmap的结构体，map会分配到堆上
func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}

// 初始化map，根据hint
func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// initialize Hmap
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	// 根据hint确定B的值，桶的数量为2^B个，如果元素的个数除以桶的个数>6.5，那么B会+1
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// B>0时，分配buckets和nextOverflow
	if h.B != 0 {
		var nextOverflow *bmap
		// todo...
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

使用make初始化map时，编译器会根据指定的size决定是调用makemap_small还是makemap.

创建一个hmap
根据指定的元素数量，计算出B的值
当B>0时，调用makeBucketArray去创建桶，并指定下一个桶的位置。

通过key获取map的值

【mapaccess1】

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   if raceenabled && h != nil {
      callerpc := getcallerpc()
      pc := funcPC(mapaccess1)
      racereadpc(unsafe.Pointer(h), callerpc, pc)
      raceReadObjectPC(t.key, key, callerpc, pc)
   }
   if msanenabled && h != nil {
      msanread(key, t.key.size)
   }
   // 如果map为nil或者map的元素数量为0，返回零值
   if h == nil || h.count == 0 {
      if t.hashMightPanic() {
         t.hasher(key, 0) // see issue 23734
      }
      return unsafe.Pointer(&zeroVal[0])
   }
   // 不能同时读写
   if h.flags&hashWriting != 0 {
      throw("concurrent map read and map write")
   }
   // 计算出key的hash值
   hash := t.hasher(key, uintptr(h.hash0))
   // bucketMask返回桶的数量-1，比如B=4,m=15 (1111)
   m := bucketMask(h.B)
   // hash&m，将key的hash值跟m按位与计算，得出key所在桶的编号，再乘以每个桶的大小加上初始桶的位置，获取到桶的地址
   b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   // 旧桶不为空，说明桶正在扩容
   if c := h.oldbuckets; c != nil {
   		// 判断是否是同体积扩容
      if !h.sameSizeGrow() {
         // There used to be half as many buckets; mask down one more power of two.
         m >>= 1
      }
      // 计算出key在oldBuckets中桶的地址
      oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
      // 判断旧桶是否已经被搬运了
      if !evacuated(oldb) {
         b = oldb
      }
   }
   // 获取hash的高8位，为top值
   top := tophash(hash)
bucketloop:
	// 遍历桶的链表
   for ; b != nil; b = b.overflow(t) {
   		// 遍历桶中的格子，先比较tophash的值是否一致，如果不一致就跳过
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
            if b.tophash[i] == emptyRest {
               break bucketloop
            }
            continue
         }
         // 如果tophash一致，则计算出这个格子的key的地址
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
         }
         // 比较两个key是否一致，如果一致，则找到对应的值的地址，返回值，否则就继续查找
         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
         }
      }
   }
   return unsafe.Pointer(&zeroVal[0])
}

先做一些基础校验
计算出key的hash值m
获取key所在的桶的地址b
计算出key hash值的高8位 top
遍历桶链表，比较桶中的每个格子是否与top一致，如果一致再获取到格子对应的key值是否与要查找的key一致，一致则返回对应的值

向map插入值

【maoassign】

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   if h == nil {
      panic(plainError("assignment to entry in nil map"))
   }
   if raceenabled {
      callerpc := getcallerpc()
      pc := funcPC(mapassign)
      racewritepc(unsafe.Pointer(h), callerpc, pc)
      raceReadObjectPC(t.key, key, callerpc, pc)
   }
   if msanenabled {
      msanread(key, t.key.size)
   }
   // 检验当前map是否正在进行写操作
   if h.flags&hashWriting != 0 {
      throw("concurrent map writes")
   }
   hash := t.hasher(key, uintptr(h.hash0))

   // 将flags设置为写
   h.flags ^= hashWriting

   if h.buckets == nil {
      h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   }

again:
	// 确定key所在的桶，如果map正在扩容，需要确保我们正在使用的旧桶已经被搬运到新桶
   bucket := hash & bucketMask(h.B)
   if h.growing() {
      growWork(t, h, bucket)
   }
   b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   top := tophash(hash)

   var inserti *uint8
   var insertk unsafe.Pointer
   var elem unsafe.Pointer
bucketloop:
	// 遍历查找桶中key是否存在，并将找到的第一个空格子记录下来（inserti）
   for {
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
            if isEmpty(b.tophash[i]) && inserti == nil {
               inserti = &b.tophash[i]
               insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
               elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            }
            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) {
            continue
         }
         // already have a mapping for key. Update it.
         // key存在的时候删除
         if t.needkeyupdate() {
            typedmemmove(t.key, k, key)
         }
         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
         goto done
      }
      // 遍历溢出桶
      ovf := b.overflow(t)
      if ovf == nil {
         break
      }
      b = ovf
   }
   
	// 如果key不存在，判断是否需要扩容
   if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
      hashGrow(t, h)
      goto again // Growing the table invalidates everything, so try again
   }
   
	// 没有可插入的空位时，需要新增一个溢出桶
   if inserti == nil {
      // all current buckets are full, allocate a new one.
      newb := h.newoverflow(t, b)
      inserti = &newb.tophash[0]
      insertk = add(unsafe.Pointer(newb), dataOffset)
      elem = add(insertk, bucketCnt*uintptr(t.keysize))
   }

   // store new key/elem at insert position
   if t.indirectkey() {
      kmem := newobject(t.key)
      *(*unsafe.Pointer)(insertk) = kmem
      insertk = kmem
   }
   if t.indirectelem() {
      vmem := newobject(t.elem)
      *(*unsafe.Pointer)(elem) = vmem
   }
   typedmemmove(t.key, insertk, key)
   *inserti = top
   h.count++

done:
   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   h.flags &^= hashWriting
   if t.indirectelem() {
      elem = *((*unsafe.Pointer)(elem))
   }
   return elem
}

计算出要写入key的hash值
计算出key所在的桶，如果map正在扩容，需要保证要使用的旧桶已经被搬运，因为新增的值需要放到新桶中去
遍历桶及其链表，根据tophash查找key是否可能存在，并记录找到的第一个空格子的位置（如果遍历完桶未找到这个key，就会把这个k-v存储在这个空格子）
如果tophash存在，判断完整的key是否一致。
如果key存在，则更新值
如果key不存在，先判断是否需要扩容，如需扩容，先扩容，再重新遍历获取空格子的位置
如果所有格子都满了，那么需要新增溢出桶
保存key对应的值

map桶的扩容

map在make进行初始化的时候会根据元素的数量，分配桶的数量。

在向map中存入key-value时，如果满足以下条件，会对map进行扩容：

桶的装载因子>6.5，装载因子=count/桶的数量
overflow桶太多，当溢出桶的数量>=普通桶的数量，参考tooManyOverflowBuckets。溢出桶太多会导致扫描时间变长
当前状态不是正在扩容的状态

扩容方式：

相同容量扩容，当装载因子<=6.5时，说明是溢出桶太多了，容量不变，仅对桶进行整理。
2倍容量扩容，当装载因子>6.5时，将桶的数量乘以2进行扩容。

map遍历

【runtime.mapiterinit】

【runtime.mapiternext】

map遍历主要调用了这两个方法，需要注意的是在mapiterinit方法中有一行代码r := uintptr(fastrand())用来指定从哪个桶开始遍历，这个桶是随机的。

map遍历时是无序的，因为map扩容时会重新整理桶，这样会改变原有的顺序。

map并发安全

map在并发时是不安全的，在mapaccess1和mapassign方法中，也对并发读写的情况进行了判断，如果发生并发读写的情况，就会引发panic。

解决方法有：

加读写锁，sync.WRMutex
使用sync.Map，sync.Map采用空间换时间的方式，将读写分离，适用于大量读，少量写的场景

使用场景：

只读场景：sync.Map > rwmutex >> mutex
读写场景（边读边写）：rwmutex > mutex >> sync.Map
读写场景（80%读20%写）：sync.Map > rwmutex > mutex
读写场景（98%读2%写）：sync.Map > rwmutex >> mutex
只写场景：sync.Map >> mutex >rwmutex

选择：

对性能要求不高的情况，尽量使用RWmutex
在高并发时，RWmutex性能下降很快尽量使用sync.Map
读多写少时使用sync.Map
读写都多时使用RWmutex
遍历较多时使用RWmutex

资料

大话图解golang map

好未来Golang源码系列一：Map实现原理分析

转载：https://blog.csdn.net/weixin_43513459/article/details/116565467

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章