首页 文章 Go语言基础 Golang 引用类型 map
0
0
0
3

Golang 引用类型 map

变量类型 map集合 类型 Golang map

1. 概念

1.1 数据结构

map底层是一个散列表,有两部分组成:

  • hmap (header): 包含多个字段,最重要的字段为 buckets 数组指针, 类型unsafe.Pointer
  • bmap (bucket): 存储key和value的数组

Golang 把求得的哈希值按照用途一分为二:高位和低位。低位用于寻找当前key属于哪个hmap的那个bucket,高位用于寻找bucket中哪个key

map中的key和value值都存到同一个数组中,这样做的好处是,在key和value的长度不同时,可以消除padding带来的空间浪费

map扩容:当map的长度增长到大于加载因子所需要的map长度时,将会产生一个新的bucket数组,然后把旧的bucket数组迁移到一个属性字段oldbucket中。注意不会立即迁移,只有当访问到具体某个bucket时,才可能发生转移

map 底层实现:

  • 哈希查找表(Hash table)

哈希查找表用一个哈希函数将key分配到不同的bucket上,开销主要在哈希函数的计算及数组的常数访问时间,多种场景下,哈希查找性能更高。

哈希查找表一般会存在“碰撞”问题,就是说不同的key被哈希到了同一个bucket上。一般有两种应对方法:链表法 和 开发地址法。链表法:将一个bucket实现一个链表,落在同一个bucket中的key都会插入这个链表。开发地址法:碰撞发生后,通过一定的规则,在数组的后面挑选“空位”,用来放置新的key。

  • 搜素树 (Search tree)

搜索数法一般采用自平衡搜索数,包括:AVL树,红黑树。

自平衡搜索树法最差搜索效率是O(logN),而哈希查找表最差是O(N)。

1.2 key 的类型

  • 不可变类型:bool, number, string, ptr, channel, interface, struct, array(必须由不可变类型组成),可hash,支持==, !=操作
  • 可被类型:slice, map, function等。

map的key必须是“不可变类型”,比如math.NaN() == math.NaN() 返回false,无法作为map的key!

浮点数做key值,需要考虑它的bit值是否一致:

func main() {
	a := 3.1
	b := 3.100000000001
	c := 3.1000000000000000000000001

	m := make(map[float64]int)
	m[a] = 10

	fmt.Println(math.Float64bits(a) == math.Float64bits(b)) // false
	fmt.Println(math.Float64bits(a) == math.Float64bits(c)) // true
	fmt.Println(m[a], m[b], m[c])                           // 10, 0, 10
}

1.3 key 的无序性

map扩容后,会发生key的搬迁,原来落在同一个bucket中的key,搬迁后,可能到了其他bucket上(当前bucket序号加上2^B)。

map的遍历,按顺序遍历bucket,同时按顺序遍历bucket中的key。搬迁后,key位置发生变化,map也就不能按原来的顺序了。

go在遍历map时,并不固定从0号bucket开始,每次都从一个随机的bucket开始遍历,并且是从这个bucket的一个随机号的cell开始遍历。这样,即使你写死一个map,每次遍历的结果都会不一致

2. 基本操作

func main() {
	m := map[string]int{
		"a": 1,
		"b": 2,
	}

	m["c"] = 3

	// ok-idiom
	if v, ok := m["d"]; ok {
		fmt.Println(v)
	}

	delete(m, "b")

	for k, v := range m {
		fmt.Printf("%s: %d\n", k, v)
	}
}

2.1 修改成员值

字典被设计成“not addressable”,不能直接修改value成员(结构体或数组)

无法对 map 的 key 或 value 进行取址

即使通过unsafe.Pointer 等获取到了 key 或 value 的地址,也不能长期持有,因为一旦发生扩容,key 和 value 的位置就会改变,之前保存的地址也就失效了

func main() {
	m := map[int]user{
		1: user{"jackson", 21},
		2: user{"sara", 20},
	}

	// cannot assign to struct field in a map
	//m[1].age++

	jackson := m[1]
	jackson.age++
	m[1] = jackson // 值拷贝,必须重新赋值
	for k, v := range m {
		fmt.Printf("%v: %v\n", k, v)
	}

	// 推荐使用指针
	m2 := map[int]*user{
		1: &user{"jackson", 21},
		2: &user{"sara", 20},
	}

	m2[1].age++
	for k, v := range m2 {
		fmt.Printf("%v: %v\n", k, v)
	}
}
func main() {
	m := map[string][2]int{
		"a": {1, 2},
	}

	// 数组必须 addressable
	//s := m["a"][:]

	a := m["a"]
	fmt.Printf("%p, %v\n", &a, a)

	s := a[:]
	fmt.Printf("%p, %v\n", &s, s)
}

2.2 删除成员

底层执行的删除函数:func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

mapdelete函数,它首先会检测h.flags标识,如果发现写标识为1,说明其他协程正在进行写操作,直接panic

计算key的hash值,找到落入的bucket,检查此map如果正进行扩容,直接触发一次迁移操作

删除操作同样两层循环,核心还是找到key的具体位置。寻找过程是类似的,在bucket中挨个cell寻找

// 对 key 清零
if t.indirectkey {
  *(*unsafe.Pointer)(k) = nil
} else {
  typedmemclr(t.key, k)
}

// 对 value 清零
if t.indirectvalue {
  *(*unsafe.Pointer)(v) = nil
} else {
  typedmemclr(t.elem, v)
}

最后,将count的值减1,将对应位置的tophash值换成Empty

可以边遍历边删除吗?

map 并不是一个线程安全的数据结构。同时读写一个 map 是未定义的行为,如果被检测到,会直接 panic。

一般而言,这可以通过读写锁来解决:sync.RWMutex

读之前调用 RLock() 函数,读完之后调用 RUnlock() 函数解锁;写之前调用 Lock() 函数,写完之后,调用 Unlock() 解锁。

另外,sync.Map 是线程安全的 map,也可以使用。

2.4 比较操作

map 只允许与nil比较

map深度相等(reflect.DeepEqual()的条件:

  • 都为nil
  • 非空、长度相等,指向同一个map实体对象 (赋值拷贝)
  • 相应的key指向的value “深度“相等
func main() {
	var m1 map[int]string
	m2 := map[int]string{1: "a"}
	m3 := m1

	fmt.Println(m1 == nil) // true
	fmt.Println(m2 == nil) // false
	fmt.Println(m3 == nil) // true
	//fmt.Println(m1 == m2)  // 编译失败 map can only be compared to nil
	//fmt.Println(m1 == m3) // same above

	fmt.Println(reflect.DeepEqual(m1, m2)) // false
	fmt.Println(reflect.DeepEqual(m1, m3)) // true
}

2.5 排序

func main() {
	m := map[int]string{2: "b", 5: "e", 1: "a", 3: "c", 4: "d"}
	s := make([]int, 0)

	for k := range m {
		s = append(s, k)
	}
	fmt.Println(s)

	// 索引排序
	sort.Ints(s)

	for _, k := range s {
		fmt.Printf("%v: %v\n", k, m[k])
	}
}

3. 线程安全

map线程不安全

在查找、赋值、遍历、删除的过程中,都会检测写标志,一旦发现写标识位(等于1),则直接panic。赋值和删除函数载检测写标识复位后,先将写标识复位,才会进行之后的操作。

// 检测写标识:
if h.flags&hashWriting == 0 {
  throw("concurrent map writes")
}

// 设置写标识:
h.flags |= hashWriting
func main() {
	var lock sync.RWMutex
	m := make(map[string]int)

	go func() {
		rand.Seed(time.Now().UnixNano())
		for {
			lock.Lock()
			m["a"] = rand.Intn(100)
			lock.Unlock()
			time.Sleep(time.Second)
		}
	}()

	go func() {
		for {
			lock.Lock()
			if v, ok := m["a"]; ok {
				fmt.Printf("%v ", v)
			}
			lock.Unlock()
			time.Sleep(time.Second)
		}
	}()

	select {
	case <-time.After(5 * time.Second):
		return
	}
}

4. 使用总结

4.1 初始化赋值问题

值为复杂类型时,推荐使用指针

// 不推荐, 值拷贝,无法直接修改Student的值
m := map[string]Student

// 推荐,地址拷贝
m := map[string]*Student

4.2 遍历问题

// 不推荐:采用range方式赋值
for _, stu := range stus {
  m[stu.Name] = &stu
}
// why?
// for-range 创建每个元素的副本,而不直接返回每个元素的引用

// 推荐:采用索引方式赋值
for i := 0; i < len(stus); i++ {
  m[stu.Name] = &stus[i]
}
func main() {
	stus := []Student{
		{"Sam", 23},
		{"Jack", 41},
		{"Daniel", 34},
	}

	m := make(map[string]*Student)

	/*	for _, stu := range stus {
		// stu所占的地址,将指向最后一个元素的副本地址
		fmt.Printf("%p\n", &stu)
		m[stu.Name] = &stu
	}*/

	// 正确
	for i := 0; i < len(stus); i++ {
		m[stus[i].Name] = &stus[i]
	}

	for k, v := range m {
    fmt.Println(k, "=>", v)
	}
}
到此这篇关于“Golang 引用类型 map”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持Go语言编程网!

相关文章

创建博客

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

在线教程

查看更多
  • Go入门指南

    Go入门指南

  • Go语言高级编程

    Go语言高级编程

  • Go Web 编程

    Go Web 编程

  • GO专家编程

    GO专家编程

  • Go语言四十二章经

    Go语言四十二章经

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

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

Go语言编程网

微信扫码关注订阅号


博客 资讯 教程 我的