首页 文章 Go语言基础 golang-map分析
0
0
0
37

golang-map分析

map集合 golang-map golang map

转载自:https://juejin.im/entry/5a1e4bcd6fb9a045090942d8

本文将主要分析一下golang中map的实现原理,并对使用中的常见问题进行讨论。进行分析的golang版本为1.9。

golang中的map是用hashmap作为底层实现的,在github的源码中相关的代码有两处:runtime/hashmap.go定义了map的基本结构和方法,runtime/hashmap_fast.go提供了一些快速操作map的函数。

map基本数据结构

map的底层结构是hmap(即hashmap的缩写),核心元素是一个由若干个桶(bucket,结构为bmap)组成的数组,每个bucket可以存放若干元素(通常是8个),key通过哈希算法被归入不同的bucket中。当超过8个元素需要存入某个bucket时,hmap会使用extra中的overflow来拓展该bucket。下面是hmap的结构体。

type hmap struct {
	count     int // # 元素个数
	flags     uint8
	B         uint8  // 说明包含2^B个bucket
	noverflow uint16 // 溢出的bucket的个数
	hash0     uint32 // hash种子
 
	buckets    unsafe.Pointer // buckets的数组指针
	oldbuckets unsafe.Pointer // 结构扩容的时候用于复制的buckets数组
	nevacuate  uintptr        // 搬迁进度(已经搬迁的buckets数量)
 
	extra *mapextra
}

在extra中不仅有overflow,还有oldoverflow(用于扩容)和nextoverflow(prealloc的地址)。

bucket(bmap)的结构如下

type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt values.
	// NOTE: packing all the keys together and then all the values together makes the
	// code a bit more complicated than alternating key/value/key/value/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

  • tophash用于记录8个key哈希值的高8位,这样在寻找对应key的时候可以更快,不必每次都对key做全等判断。
  • 注意后面几行注释,hmap并非只有一个tophash,而是后面紧跟8组kv对和一个overflow的指针,这样才能使overflow成为一个链表的结构。但是这两个结构体并不是显示定义的,而是直接通过指针运算进行访问的。
  • kv的存储形式为”key0key1key2key3…key7val1val2val3…val7″,这样做的好处是:在key和value的长度不同的时候,节省padding空间。如上面的例子,在map[int64]int8中,4个相邻的int8可以存储在同一个内存单元中。如果使用kv交错存储的话,每个int8都会被padding占用单独的内存单元(为了提高寻址速度)。

hmap的结构差不多如图

map的访问

以mapaccess1为例,部分无关代码被修改。

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// do some race detect things
	// do some memory sanitizer thins
 
	if h == nil || h.count == 0 {
		return unsafe.Pointer(&zeroVal[0])
	}
	if h.flags&hashWriting != 0 {  // 检测是否并发写,map不是gorountine安全的
		throw("concurrent map read and map write")
	}
	alg := t.key.alg  // 哈希算法 alg -> algorithm
	hash := alg.hash(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
        // 如果老的bucket没有被移动完,那么去老的bucket中寻找 (增长部分下一节介绍)
	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
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
        // 寻找过程:不断比对tophash和key
	top := tophash(hash)
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey {
				k = *((*unsafe.Pointer)(k))
			}
			if alg.equal(key, k) {
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				if t.indirectvalue {
					v = *((*unsafe.Pointer)(v))
				}
				return v
			}
		}
	}
        return unsafe.Pointer(&zeroVal[0])
}

map的增长

随着元素的增加,在一个bucket链中寻找特定的key会变得效率低下,所以在插入的元素个数/bucket个数达到某个阈值(当前设置为6.5,实验得来的值)时,map会进行扩容,代码中详见 hashGrow函数。首先创建bucket数组,长度为原长度的两倍 

newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger)
,然后替换原有的bucket,原有的bucket被移动到oldbucket指针下。

扩容完成后,每个hash对应两个bucket(一个新的一个旧的)。oldbucket不会立即被转移到新的bucket下,而是当访问到该bucket时,会调用growWork方法进行迁移,growWork方法会将oldbucket下的元素rehash到新的bucket中。随着访问的进行,所有oldbucket会被逐渐移动到bucket中。

但是这里有个问题:如果需要进行扩容的时候,上一次扩容后的迁移还没结束,怎么办?在代码中我们可以看到很多”again”标记,会不断进行迁移,知道迁移完成后才会进行下一次扩容。

 

使用中常见问题

Q:删除掉map中的元素是否会释放内存?

A:不会,删除操作仅仅将对应的tophash[i]设置为empty,并非释放内存。若要释放内存只能等待指针无引用后被系统gc

 

Q:如何并发地使用map?

A:map不是goroutine安全的,所以在有多个gorountine对map进行写操作是会panic。多gorountine读写map是应加锁(RWMutex),或使用sync.Map(1.9新增,在下篇文章中会介绍这个东西,总之是不太推荐使用)。

 

Q:map的iterator是否安全?

A:map的delete并非真的delete,所以对迭代器是没有影响的,是安全的。

内存布局:

转载自:https://ninokop.github.io/2017/10/24/Go-Hashmap%E5%86%85%E5%AD%98%E5%B8%83%E5%B1%80%E5%92%8C%E5%AE%9E%E7%8E%B0/

Go Hashmap内存布局和实现

想了解Go内置类型的内存布局的契机,是一次在调试“不同类型的小对象频繁创建对gc性能的影响”时发现map的gc性能不佳,而作为对比的包含slice的struct却很好。这里总结Go runtime里map的实现,可以解释这个问题。

hash table内部结构

Go的map就是hashmap,源码在src/runtime/hashmap.go。对比C++用红黑树实现的map,Go的map是unordered map,即无法对key值排序遍历。跟传统的hashmap的实现方法一样,它通过一个buckets数组实现,所有元素被hash到数组的bucket中,buckets就是指向了这个内存连续分配的数组。B字段说明hash表大小是2的指数,即2^B。每次扩容会增加到上次大小的两倍,即2^(B+1)。当bucket填满后,将通过overflow指针来mallocgc一个bucket出来形成链表,也就是为哈希表解决冲突问题。

     
1
2
3
4
5
6
7
8
9
10
11
12
13
     
// A header for a Go map.
type hmap struct {
count int // len()返回的map的大小 即有多少kv对
flags uint8
B uint8 // 表示hash table总共有2^B个buckets
hash0 uint32 // hash seed
buckets unsafe.Pointer // 按照low hash值可查找的连续分配的数组,初始时为16个Buckets.
oldbuckets unsafe.Pointer
nevacuate uintptr
overflow *[ 2]*[]*bmap //溢出链 当初始buckets都满了之后会使用overflow
}
     
1
2
3
4
5
6
7
8
9
     
// A bucket for a Go map.
type bmap struct {
tophash [bucketCnt] uint8
// Followed by bucketCnt keys and then bucketCnt values.
// NOTE: packing all the keys together and then all the values together makes the
// code a bit more complicated than alternating key/value/key/value/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}

上图是一个bucket的数据结构,tophash是个大小为8(bucketCnt)的数组,存储了8个key的hash值的高八位值,在对key/value对增删查的时候,先比较key的hash值高八位是否相等,然后再比较具体的key值。根据官方注释在tophash数组之后跟着8个key/value对,每一对都对应tophash当中的一条记录。最后bucket中还包含指向链表下一个bucket的指针。内存布局如下图。

之所以把所有k1k2放一起而不是k1v1是因为key和value的数据类型内存大小可能差距很大,比如map[int64]int8,考虑到字节对齐,kv存在一起会浪费很多空间。

map相关操作

map初始化

B的初始大小是0,若指定了map的大小hint且hint大于8,那么buckets会在make时就通过newarray分配好,否则buckets会在第一次put的时候分配。随着hashmap中key/value对的增多,buckets需要重新分配,每一次都要重新hash并进行元素拷贝。所以最好在初始化时就给map指定一个合适的大小。

makemap有h和bucket这两个参数,是留给编译器的。如果编译器决定hmap结构体和第一个bucket可以在栈上创建,这两个入参可能不是nil的。

     
1
2
3
4
5
6
7
8
9
10
11
12
13
     
// makemap implemments a Go map creation make(map[k]v, hint)
func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap{
B := uint8( 0)
for ; hint > bucketCnt && float32(hint) > loadFactor* float32( uintptr( 1)<<B); B++ {
}
// 确定初始B的初始值 这里hint是指kv对的数目 而每个buckets中可以保存8个kv对
// 因此上式是要找到满足不等式 hint > loadFactor*(2^B) 最小的B
if B != 0 {
buckets = newarray(t.bucket, uintptr( 1)<<B)
}
h = (*hmap)(newobject(t.hmap))
return h
}

map存值

存储的步骤和第一部分的分析一致。首先用key的hash值低8位找到bucket,然后在bucket内部比对tophash和高8位与其对应的key值与入参key是否相等,若找到则更新这个值。若key不存在,则key优先存入在查找的过程中遇到的空的tophash数组位置。若当前的bucket已满则需要另外分配空间给这个key,新分配的bucket将挂在overflow链表后。

     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
     
func mapassign1(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {
hash := alg.hash(key, uintptr(h.hash0))
if h.buckets == nil {
h.buckets = newarray(t.bucket, 1)
}
again:
//根据低8位hash值找到对应的buckets
bucket := hash & ( uintptr( 1)<<h.B - 1)
b := (bmap)(unsafe.Pointer( uintptr(h.buckets) + bucketuintptr(t.bucketsize)))
//计算hash值的高8位
top := uint8(hash >> (sys.PtrSize* 8 - 8))
for {
//遍历每一个bucket 对比所有tophash是否与top相等
//若找到空tophash位置则标记为可插入位置
for i := uintptr( 0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == empty && inserti == nil {
inserti = &b.tophash[i]
}
continue
}
//当前tophash对应的key位置可以根据bucket的偏移量找到
k2 := add(unsafe.Pointer(b), dataOffset+i* uintptr(t.keysize))
if !alg.equal(key, k2) {
continue
}
//找到符合tophash对应的key位置
typedmemmove(t.elem, v2, val)
goto done
}
//若overflow为空则break
ovf := b.overflow(t)
}
// did not find mapping for key. Allocate new cell & add entry.
if float32(h.count) >= loadFactor* float32(( uintptr( 1)<<h.B)) && h.count >= bucketCnt {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
// all current buckets are full, allocate a new one.
if inserti == nil {
newb := (*bmap)(newobject(t.bucket))
h.setoverflow(t, b, newb)
inserti = &newb.tophash[ 0]
}
// store new key/value at insert position
kmem := newobject(t.key)
vmem := newobject(t.elem)
typedmemmove(t.key, insertk, key)
typedmemmove(t.elem, insertv, val)
*inserti = top
h.count++
}

hash Grow扩容和迁移

在往map中存值时若所有的bucket已满,需要在堆中new新的空间时需要计算是否需要扩容。扩容的时机是count > loadFactor(2^B)。这里的loadfactor选择为6.5。扩容时机的物理意义的理解 在没有溢出时hashmap总共可以存储8(2^B)个KV对,当hashmap已经存储到6.5(2^B)个KV对时表示hashmap已经趋于溢出,即很有可能在存值时用到overflow链表,这样会增加hitprobe和missprobe。为了使hashmap保持读取和超找的高性能,在hashmap快满时需要在新分配的bucket中重新hash元素并拷贝,源码中称之为evacuate。

overflow溢出率是指平均一个bucket有多少个kv的时候会溢出。bytes/entry是指平均存一个kv需要额外存储多少字节的数据。hitprobe是指找到一个存在的key平均需要找多少次。missprobe是指找到一个不存在的key平均需要找多少次。选取6.5是为了平衡这组数据。

loadFactor%overflowbytes/entryhitprobemissprobe
4.002.1320.773.004.00
4.504.0517.303.254.50
5.006.8514.773.505.00
5.5010.5512.943.755.50
6.0015.2711.674.006.00
6.5020.9010.794.256.50
7.0027.1410.154.507.00
7.5034.039.734.757.50
8.0041.109.405.008.00

但这个迁移并没有在扩容之后一次性完成,而是逐步完成的,每一次insert或remove时迁移1到2个pair,即增量扩容。增量扩容的原因 主要是缩短map容器的响应时间。若hashmap很大扩容时很容易导致系统停顿无响应。增量扩容本质上就是将总的扩容时间分摊到了每一次hash操作上。由于这个工作是逐渐完成的,导致数据一部分在old table中一部分在new table中。old的bucket不会删除,只是加上一个已删除的标记。只有当所有的bucket都从old table里迁移后才会将其释放掉。



到此这篇关于“golang-map分析”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持Go语言编程网!

相关文章

创建博客

开始创作
写作能提升自己能力,也能为他人分享知识。

在线教程

查看更多
  • Go入门指南

    Go入门指南

  • Go语言高级编程

    Go语言高级编程

  • Go Web 编程

    Go Web 编程

  • GO专家编程

    GO专家编程

  • Go语言四十二章经

    Go语言四十二章经

  • 数据结构和算法(Golang实现)

    数据结构和算法(Golang实现)

Go语言编程网

微信扫码关注订阅号


博客 资讯 教程 我的