在Slice中提到的是内层对数据的修改,在外层不可见。这点和Map有一些区别,如下:
func main() {
m := make(map[int]int)
modifyMap(m)
fmt.Println(m) //map[1:1 2:2]
}
func modifyMap(m map[int]int) {
m[1] = 1
m[2] = 2
}
因为map的底层是一个hmap的结构(在runtime里面可以看到,如下:),在使用make去创建的的时候,创建的不是一个结构体,而是一个指向hmap结构体的一个指针,所以在modifyMap中,传递的是指针,所以可以对外层进行修改。
map结构type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer //记录桶在哪
oldbuckets unsafe.Pointer // 旧桶在哪
nevacuate uintptr // 下一个要迁移的旧桶编号
extra *mapextra // optional fields
}
map详细实现原理:
hash和桶的选择:
在选择桶的过程中用两种方法:
- 1:取模法,将hash(k1)%m;
- 2:与运算,hash(k1)&(m-1);需要注意确保桶选择空间在[0,m-1]区间内,而不出现空桶,就需要将m为2的正整数次幂,这样m的二进制整数只有一位是1。
- go语言中的Map采用的是与运算的方式。这也就是为什么每次扩容后的容量是扩容前的二倍。
hash冲突:go语言中的实现主要是拉链法,如果需要对CPU缓存更有好的话建议采用开放地址法(但是这个是写在了runtime里面了,没办法修改)。
- 开放地址法,如下图:
如果后期查找桶的时候,会先定位到二号桶,对比k的hash值,如果不相同,就向后一次查找。
- 拉链法,如下图:
避免hash冲突(扩容)顺着链表向后查找并依次对比k的hash
- 扩容因子:作为判断是否需要扩容的依据,采用LoadFactor=count/m。
如上图,如果如果旧桶数据量比较大的话,迁移需要花费很多时间,所以采用渐进式扩容。如变量navacuate。
- 如hmap结构体中
buckets unsafe.Pointer //记录桶在哪 oldbuckets unsafe.Pointer // 旧桶在哪 nevacuate uintptr // 下一个要迁移的旧桶编号注意:
错误的用法map实际上的值,是一个指针,传的参数是指针,所以任何修改都会改变map的实际值。
m := make(map[int]int) fmt.Print(&m[1])
- 是因为随着map的扩容,map的Key和Value都会发生改变,并且map保存的是值,会发生copy。
map不会发生缩容
go开发者中有句话为:Yes, maps that shrink permanently currently never get cleaned up after. As usual, the implementation challenge is with iterators.
Maps that shrink and grow repeatedly used to also cause leaks. That was #16070, fixed by CL 25049. I remember hoping when I started on that CL that the same mechanism would be useful for shrinking maps as well, but deciding it wouldn’t. Sadly, I no longer remember why. If anyone wants to investigate this issue, I’d start by looking at that CL and thinking about whether that approach could be extended to shrinking maps.
The only available workaround is to make a new map and copy in elements from the old.大概意思是反复的扩容缩容会导致泄漏。



