Golang 引用类型 map - Golang教程网

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等。

math.NaN() == math.NaN()

浮点数做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

2.4 比较操作

map 只允许与nil比较

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)
	}
}