golang——map - Golang教程网

1.map特点

以键值对为元素的数据集合

特点：

1.键不能重复

2.键必须可哈希（int/bool/float/string/array）

3.无序

快：可以直接根据键值找到数据存储的位置，而不用从前到后一一比对

2.map声明和初始化

package main

import "fmt"

func main() {
	userInfo := map[string]string{}
	userInfo1 := map[string]string{"name": "xxx", "age": "18"}
	//新增键值
	userInfo["name"] = "000"
	//修改键值
	userInfo1["name"] = "111"
	fmt.Println(userInfo)
	fmt.Println(userInfo1)

   
}

package main

import "fmt"

func main() {
	userInfo2 := make(map[string]string)
	//初始化容量cap为10
	userInfo3 := make(map[string]string,10)
	userInfo2["name"] = "222"
	fmt.Println(userInfo2)
	fmt.Println(userInfo3)

	v1 := make(map[[2]int]float32)
	v1[[2]int{1, 1}] = 1.4
	v1[[2]int{1, 3}] = 5.3
	fmt.Println(v1)

    v2 := make(map[[2]int][3]float32)
	v2[[2]int{1, 1}] = [3]float32{1.0, 2.1, 3.5}
	v2[[2]int{1, 3}] = [3]float32{1.0, 2.1, 3.5}
	fmt.Println(v2)
}

package main

func main() {
	var userInfo map[string]string
	//只声明，无法添加键值对
	userInfo["name"] = "000"

}

package main

func main() {
	userInfo0 := map[string]string{}
	var userInfo map[string]string
	userInfo=userInfo0
	//只声明，无法添加键值对
	userInfo["name"] = "000"

}

package main

import "fmt"

func main() {
	userInfo := new(map[string]string)
	userInfo1 := map[string]string{}
	//userInfo["name"] = "xxx"  报错
	userInfo = &userInfo1
	fmt.Println(userInfo)
}

变量初始化

变量初始化=变量声明+变量内存分配

make和new主要是用来分配内存的

var是用来声明变量的

var值声明

值类型变量

系统会默认为他分配内存空间，并赋该类型的零值

指针类型/引用类型变量

系统不会为它分配内存，默认为nil,如果直接使用，系统会抛异常，必须进行内存分配才能使用

make和new

make和new是内置函数，不是关键字

二者都是分配空间

但是new返回值类型的指针
而make返回的是类型本身

make只能用于slice、map、chan的初始化
new可以分配任意类型的数据，并且置零

new分配的空间会被清零
make则会初始化

3.map常见操作


m := make(map[string]string, 10)
获取长度，即存储的键值对个数
len:=len(m)

获取容量,cap为根据参数值10计算出的合适容量
cap:=cap(m) 不支持，会报错

delete(userInfo,"name")

4.map的嵌套

package main

func main() {
	v1:=make(map[string][2]map[int]int)
	v2:=make(map[string][]int)
	
	v1["xx"]=[2]map[int]int{map[int]int{1:2,2:3},map[int]int{1:3,4:5}}
	v2["xx"]=[]int{1,2,3}
	

}

package main

func main() {
	v1 := make(map[[2]int]int)
	v1[[2]int{1,2}]=1

}

5.golang中map底层结构

hmap(哈希表，含指向桶数组的指针）
bmap(桶）
mapextra（溢出桶）

type hmap struct{
    //哈希表中元素个数，调用len(map)时，返回的就是该字段
    count int
    //状态标志(是否处于正在写入的状态等，如果有线程正在写入，就不能读写）
    flags uint8
    //buckets(桶)的对数
    //如果B=5,buckets桶的长度=2^B=32,有32个桶
    B uint8
    //溢出桶的数量
    noverflow uint16
    //生成哈希的随机种子
    hash0 uint32
    //指向buckets数组的指针，数组大小为2^B,如果元素个数为0，指向nil
    buckets unsafe.Pointer
    //如果发生扩容，oldbuckets指向老的buckets数组，老的buckets数组大小是新的的1/2，非扩容状态下为nil
    oldbuckets unsafe.Pointer
    //表示扩容进度，小于此地址的buckets代表已经搬迁完成
    nevacuate uintptr
    //存储溢出桶，为了优化GC扫描而设计
    extra *mapextra
}

type bmap struct{
    tophash [bucketCnt]uint8
    //len为8的数组
    //用来快速定位key是否在这个bmap中
    //一个桶最多8个槽位，如果key所在的tophash值在tophash中，则代表该key在这个桶中
}

type bmap struct{
    tophash [8]uint8
    //keytype由编译器编译时确定
    keys [8]keytype
    //elemtype由编译器编译时确定
    values [8]elemtype
    //overflow指向下一个bmap，overflow是uintptr而不是*bmap类型，是为了减少gc，溢出桶存储到extra字段中
    overflow uintptr
}

info := make(map[string]string,10)

info["name"]="xxx"

value := info["name"]

扩容过程

向map中添加数据时，当达到某个条件，则会引发字典扩容。

扩容条件：

map中 数据总个数/桶个数（负载因子） >6.5，引发翻倍扩容
使用了太多的溢出桶时（溢出桶使用的太多会导致map处理速度降低）

B≤15，已使用的溢出桶个数≥时，引发等量扩容

B＞15，已使用的溢出桶个数≥时，引发等量扩容

扩容后oldbuckets指向旧桶

迁移

即将旧桶中数据迁移到新桶中

翻倍扩容：将旧桶中的数据分流至新的两个桶中（比例不定），并且桶编号位置为：同编号位置和翻倍后对应编号位置

等量扩容（溢出桶太多引发的扩容）：将旧桶（含溢出桶）的值迁移到新桶中

意义：当溢出桶比较多而每个桶中数据不多，可以通过等量扩容和迁移让数据更加紧凑，从而减少溢出桶

6.map遍历为什么是无序的

package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println("first range:")
	m := map[int]string{1: "a", 2: "b", 3: "c"}
	for i, v := range m {
		fmt.Printf("m[%v]=%v\n", i, v)
	}
	fmt.Println("second range:")

	var sl []int
	for i := range m {
		sl = append(sl, i)
	}
	sort.Ints(sl)
	for _, v := range sl {
		fmt.Printf("m[%v]=%v\n", v, m[v])
	}

}

7.map为什么是非线程安全的

package main

import "fmt"

func main() {
	s := make(map[int]int)
	for i := 0; i < 100; i++ {
		go func(i int) {
			s[i] = i
		}(i)
	}
	for i := 0; i < 100; i++ {
		go func(i int) {
			fmt.Printf("map第%d个元素值是%d", i, s[i])
		}(i)
	}

}

8.实现map线程安全

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	var lock sync.RWMutex
	s := make(map[int]int)
	for i := 0; i < 100; i++ {
		go func(i int) {
			lock.Lock()
			s[i] = i
			lock.Unlock()
		}(i)
	}
	for i := 0; i < 100; i++ {
		go func(i int) {
			lock.RLock()
			fmt.Printf("map第%d个元素值是%d\n", i, s[i])
			lock.RUnlock()
		}(i)
	}
	//防止没执行完就退出了
	time.Sleep(time.Second * 1)

}

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {

	var s sync.Map
	for i := 0; i < 100; i++ {
		go func(i int) {
			s.Store(i, i)
		}(i)
	}
	for i := 0; i < 100; i++ {
		go func(i int) {
			load, _ := s.Load(i)
			fmt.Printf("map第%d个元素值是%d\n", i, load)
		}(i)
	}
	//防止没执行完就退出了
	time.Sleep(time.Second * 1)

}

9.map如何查找

m := map[int]string{1: "a", 2: "b", 3: "c"}

v := m[1]
fmt.Println(v)

v, ok := m[2]
fmt.Println(v, ok)

10.map的key可以使用那些类型

必须是可比较类型，数组、chan、指针等

不可比较slice、func、map

11.map冲突的解决方式

常见解决方法：

链地址法（尾插）
开放寻址法

从发生冲突的那个单元起，按照一定的次序，从哈希表中寻找一个空闲的单元，然后把发生冲突的元素存入到该单元。开放寻址法需要的表长度要大于等于所需要存放的元素数量

线性探测法
平方探测法
随机探测法
双重哈希法

Go——链地址法，插入key

12.go map的负载因子为什么是6.5

负载因子=哈希表存储元素个数/桶个数

扩容

当程序运行时，出现负载因子过大，需要扩容，解决bucket过大的问题

迁移

当程序运行时，会不断地进行插入、删除等，会导致bucket不均，内存利用率低，需要迁移

参考各负载因子下的

溢出率
平均每对key/value的开销字节数
查找一个存在的key时，要查找的平均个数
查找一个不存在的key时，要查找的平均个数

当装载因子越大，填入元素越多，空间利用率就越高，发生哈希冲突的几率就越大

当负载因子越小，填入元素越少，冲突发生的几率减小，但空间浪费更多，还会提高扩容操作的次数

go选择了一个相对适中的值

13.go map如何扩容

if !h.growing() && (overLoadFactor(h.count+1,h.8)|| tooManyOverflowBuckets(h.noverflow,h.8){

}
//判断是否在扩容                    
func(h *heap)growing()bool{
   return h.oldbuckets!=nil 
}

func overLoadFactor(count int,B uint8)bool{
    return count > bucketCnt && uintptr(count)>loadFactor*bucketShift(8)
}
bucketCnt = 8 一个桶可以装的最大元素个数
loadFactor =6.5 负载因子，平均每个桶的元素个数
bucketShift(8) 桶的个数

14.sync.map和map对比

type Map struct{
    mu Mutex
    read atomic.Value
    dirty map[interface{}]*entry
    misses int
}