栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Go语言map

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Go语言map

Map介绍

在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采用的是与运算的方式。这也就是为什么每次扩容后的容量是扩容前的二倍。

go语言中的实现主要是拉链法,如果需要对CPU缓存更有好的话建议采用开放地址法(但是这个是写在了runtime里面了,没办法修改)。

hash冲突:
  • 开放地址法,如下图:

如果后期查找桶的时候,会先定位到二号桶,对比k的hash值,如果不相同,就向后一次查找。

  • 拉链法,如下图:

顺着链表向后查找并依次对比k的hash

避免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.大概意思是反复的扩容缩容会导致泄漏。


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970803.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号