go语言底层基础

Go语言相关 #

GMP模型 #

G goroutine协程

P processor处理器

M thread线程

Processor 它包含了运行goroutine的资源，如果线程想运行goroutine,必须先获取P，P中还包含了可运行的G队列。

在Go中，线程是运行goroutine的实体，调度器的功能是把可运行的goroutine分配到工作线程上。

  • 全局队列：存放等待运行的G
  • P的本地队列：同全局队列类似，存放的也是等待运行的G，存的数量有限，不超过256个。新建 G’时，G’优先加入到 P 的本地队列，如果队列满了，则会把本地队列中一半的 G 移动到全局队列。
  • P列表：所有的P都在程序启动时创建，并保存在数组中，最多有 GOMAXPROCS(可配置) 个。
  • M：线程想运行任务就得获取P，从P的本地队列获取G，P队列为空时，M 也会尝试从全局队列拿一批 G 放到 P 的本地队列，或从其他 P 的本地队列偷一半放到自己 P 的本地队列。M 运行 G，G 执行之后，M 会从 P 获取下一个 G，不断重复下去。

Goroutine 调度器和 OS 调度器是通过 M 结合起来的，每个 M 都代表了 1 个内核线程，OS 调度器负责把内核线程分配到 CPU 的核上执行。

P 处理器的作用 #

负责调度G

P和M的个数问题 #

1、P的数量：

  • 由启动时环境变量 $GOMAXPROCS 或者是由 runtime 的方法 GOMAXPROCS() 决定。这意味着在程序执行的任意时刻都只有 $GOMAXPROCS 个 goroutine 在同时运行。

2、M的数量：

  • go 语言本身的限制：go 程序启动时，会设置 M 的最大数量，默认 10000. 但是内核很难支持这么多的线程数，所以这个限制可以忽略。
  • runtime/debug 中的 SetMaxThreads 函数，设置 M 的最大数量
  • 一个 M 阻塞了，会创建新的 M。

M与P的数量没有绝对关系，一个M阻塞，P就会去创建或者切换另一个M，所以即使P的数量是1，也有可能会创建很多个M出来。

P和M何时会被创建 #

1、P 何时创建：在确定了 P 的最大数量 n 后，运行时系统会根据这个数量创建 n 个 P。

2、M 何时创建：没有足够的 M 来关联 P 并运行其中的可运行的 G。比如所有的 M 此时都阻塞住了，而 P 中还有很多就绪任务，就会去寻找空闲的 M，而没有空闲的，就会去创建新的 M。

调度器的设计策略 #

复用线程：避免频繁的创建、销毁线程，而是对线程的复用。

1）work stealing 机制

当本线程无可运行的 G 时，尝试从其他线程绑定的 P 偷取 G，而不是销毁线程。

2）hand off 机制

当本线程因为 G 进行系统调用阻塞时，线程释放绑定的 P，把 P 转移给其他空闲的线程执行。

利用并行：GOMAXPROCS 设置 P 的数量，最多有 GOMAXPROCS 个线程分布在多个 CPU 上同时运行。GOMAXPROCS 也限制了并发的程度，比如 GOMAXPROCS = 核数/2，则最多利用了一半的 CPU 核进行并行。

抢占：在 coroutine 中要等待一个协程主动让出 CPU 才执行下一个协程，在 Go 中，一个 goroutine 最多占用 CPU 10ms，防止其他 goroutine 被饿死，这就是 goroutine 不同于 coroutine 的一个地方。

全局 G 队列：在新的调度器中依然有全局 G 队列，但功能已经被弱化了，当 M 执行 work stealing 从其他 P 偷不到 G 时，它可以从全局 G 队列获取 G。

go func () 调度流程 #

从上图我们可以分析出几个结论：

1、我们通过 go func () 来创建一个 goroutine；

2、有两个存储 G 的队列，一个是局部调度器 P 的本地队列、一个是全局 G 队列。新创建的 G 会先保存在 P 的本地队列中，如果 P 的本地队列已经满了就会保存在全局的队列中；

3、G 只能运行在 M 中，一个 M 必须持有一个 P，M 与 P 是 1：1 的关系。M 会从 P 的本地队列弹出一个可执行状态的 G 来执行，如果 P 的本地队列为空，就会想其他的 MP 组合偷取一个可执行的 G 来执行；

4、一个 M 调度 G 执行的过程是一个循环机制；

5、当 M 执行某一个 G 时候如果发生了 syscall 或则其余阻塞操作，M 会阻塞，如果当前有一些 G 在执行，runtime 会把这个线程 M 从 P 中摘除 (detach)，然后再创建一个新的操作系统的线程 (如果有空闲的线程可用就复用空闲线程) 来服务于这个 P；

6、当 M 系统调用结束时候，这个 G 会尝试获取一个空闲的 P 执行，并放入到这个 P 的本地队列。如果获取不到 P，那么这个线程 M 变成休眠状态， 加入到空闲线程中，然后这个 G 会被放入全局队列中。

channel #

底层原理 #

背景

  • Go语言提供了一种不同的并发模型-通信顺序进程（communicating sequential processes,CSP)
  • 设计模式：通过通信的方式共享内存
  • channel收发操作遵循先进先出(FIFO)的设计

底层结构:

type hchan struct {
    qcount   uint           // channel中的元素个数
    dataqsiz uint           // channel中循环队列的长度
    buf      unsafe.Pointer // channel缓冲区数据指针
    elemsize uint16            // buffer中每个元素的大小
    closed   uint32            // channel是否已经关闭，0未关闭
    elemtype *_type // channel中的元素的类型
    sendx    uint   // channel发送操作处理到的位置
    recvx    uint   // channel接收操作处理到的位置
    recvq    waitq  // 等待接收的sudog（sudog为封装了goroutine和数据的结构）队列由于缓冲区空间不足而阻塞的Goroutine列表
    sendq    waitq  // 等待发送的sudogo队列，由于缓冲区空间不足而阻塞的Goroutine列表
    lock mutex   // 一个轻量级锁
}

我们通过make创建一个缓冲区大小为5，元素类型为int的channel。ch是存在于函数栈帧上的一个指针，指向堆上的hchan数据结构。

因为channel免不了支持协程间并发访问，所以要有一个锁（lock）来保护整个channel数据结构。

对于有缓冲区channel来讲，需要知道缓冲区在哪里（buf），已经存储量多少个元素（qcount），最多存储多少个元素（dataqsize），每个元素占多大空间（elemsize)，所以实际上缓冲区就是一个数组。因为Golang运行时中，内存复制，垃圾回收等机制，依赖数据的类型信息，所以hchan这里还要有一个指针，指向元素类型的类型元数据。此外，channel支持交替的读(接收)，写(发送)。需要分别记录读，写 下标的位置，当读和写不能立即完成时，需要能够让当前协程在channel上等待，待到条件满足时，要能够立即唤醒等待的协程，所以要有两个等待队列，分别针对读和写。此外，channel能够close，所以还要记录它的关闭状态，综上所述，channel底层就长这样。

channel创建

ch := make(chan int,3)
  • 创建channel实际上就是在内存中实例化了一个hchan结构体，并返回一个chan指针
  • channel在函数间传递都是使用的这个指针，这就是为什么函数传递中无需使用channel的指针，直接使用channel就可以了，因为channel本身就是一个指针

channel发送数据：

ch <- 1
ch <- 2
  • 检查sendq是否为空，如果不为空，且没有缓冲区，则从sendq头部取一个goroutine，将数据读取出来，并唤醒对应的goroutine，结束读取过程。
  • 如果sendq不为空，且有缓冲区，则说明缓冲区已满，则从缓冲区中首部读取数据，把sendq头部的goroutine数据写入缓冲区尾部，并将goroutine唤醒，结束读取过程。
  • 如果sendq为空，缓冲区有数据，则直接从缓冲区读取数据，结束读取过程。
  • 如果sendq为空，且缓冲区没有数据，则只能将当前的goroutine加入到recvq，并进入waiting状态，等待被写goroutine唤醒。

channel规则：

操作 空channel 已关闭channel 活跃中的channel
close(ch) panic panic 成功关闭
ch<- v 永远阻塞 panic 成功发送或阻塞
v,ok = <-ch 永远阻塞 不阻塞 成功接收或阻塞

channel阻塞、非阻塞操作、多路select #

接下来，我们继续使用ch，初始状态下，ch的缓冲区为空，读、写下标都指向下标0的位置，等待队列也都为空。

然后一个协程g1向ch中发送数据，因为没有协程在等待接收数据，所以元素都被存到缓冲区中，sendx从0开始向后挪，

第5个元素会放到下标为4的位置，然后sendx重新回到0，此时缓冲区已经没有空闲位置了。

所以接下来发送的第6个元素无处可放，g1会进到ch的发送等待队列中。这是一个sudog类型的链表，里面会记录哪个协程在等待，等待哪个channel，等待发送的数据在哪里，等等消息。

接下来协程g2从ch接收一个元素，recv指向下个位置，第0个位置就空出来了，

所以会唤醒sendq中的g1，将elem指向的数据发送给ch，然后缓冲区再次满了，sendq队列为空。

在这一过程中，可以看到sendx和recvx，都会从0到4再到0，所以channel的缓冲区，被称为"环形"缓冲区。

如果像这样给channel发送数据，只有在缓冲区还有空闲位置，或者有协程在等着接收数据的时候，才不会发送阻塞。

碰到ch为nil，或者ch没有缓冲区，而且也没有协程等着接收数据，又或者，ch有缓冲区但缓冲区已用尽的情况，都会发生阻塞

解决发送阻塞

那如果不想阻塞的话，就可以使用select，使用select这种写法时，如果检测到ch可以发送数据，就会执行case分支；如果会阻塞，就会执行default分支了。

接收阻塞

这是发送数据的写法，接收数据的写法要更多一点。第一种写法会将结果丢弃，第二种写法将结果赋给变量v，第三种是comma ok风格的写法，ok为false时表示ch已关闭，此时v是channel元素类型的零值。这几种写法都允许发生阻塞，只有在缓冲区中有数据，或者有协程等待发送数据时 ，才不会阻塞。如果ch为nil，或者ch无缓冲而且没有协程等着发送数据，又或者ch有缓冲但缓冲区无数据时，都会发生阻塞。

解决接收阻塞

如果无论如何都不想阻塞，同样可以采用非阻塞式写法，这样在检测到ch的recv操作不会阻塞时，就会执行case分支，如果会阻塞，就会执行default分支。

多路select

上面的selec只是针对的单个channel的操作； 多路select指的是存在两个或者更多的case分支，每个分支可以是一个channel的send或recv操作。例如一个协程通过多路select等待ch1和ch2。这里的default分支是可选的。

我们暂且把这个协程记为g1，多路select会被编译器转换为runtime.selectgo函数调用。 第一个参数cas0指向一个数组，数组里装的是select中所有的case分支，顺序是send在前，recv在后。 第二个参数order0指向一个uint16类型的数组，数组大小等于case分支的两倍。实际上被用作两个数组，第一个数组用来对所有channel的轮询进行乱序，第二个数组用来对所有channel的加锁操作进行排序。轮询需要乱序才能保障公平性，而按照固定算法确定加锁顺序才能避免死锁。

第三个参数pc0和race检测相关，我们暂时不关心。 第四、五个参数nsends和nrecvs分别表示所有case中执行send和recv操作的分支分别有多少个。 第六个参数block表示多路select是否要阻塞等待，对应到代码中，就是有default分支的不会阻塞，没有的会阻塞。

再来看第一个返回值，它代表最终哪个case分支被执行了，对应到参数cas0数组的下标。但是如果进到default分支则对应-1。第二个返回值用于在执行recv操作的case分支时，表明是实际接收到了一个值，还是因channel关闭而得到了零值。

多路select需要进行轮询来确定哪个case分支可操作了，但是轮询前要先加锁，所以selectgo函数执行时，会先按照有序的加锁顺序，对所有channel加锁，然后按照乱序的轮询顺序检查所有channel的等待队列和缓冲区。

假如检查到ch1时，发现有数据可读，那就直接拷贝数据，进入对应分支。

假如所有channel都不可操作，就把当前协程添加到所有channel的sendq或recvq中。对应到本例中，g1会被添加到ch1的recvq，以及ch2的sendq中。之后g1会挂起，并解锁所有的channel的锁。

假如接下来ch1有数据可读了，g1就会被唤醒，完成对应分支的操作。

完成对应分支的操作后，会再次按照加锁顺序对所有channel加锁，然后从所有sendq或recvq中将自己移除，最后全部解锁，然后返回。

Golang协程间如何通信 #

GO协程通过通道来通信而协程通过让出和恢复操作来通信。

goroutine是一个与其他goroutine并发运行在同一地址空间的Go函数或方法。一个运行的程序由一个或更多个goroutine组成。它与线程、协程、进程等不同。它是一个goroutine。

defer函数 #

原理 #

defer数据结构：

type _defer struct {
    sp      uintptr   //函数栈指针
    pc      uintptr   //程序计数器
    fn      *funcval  //函数地址
    link    *_defer   //指向自身结构的指针，用于链接多个defer
}

defer后面一定要接一个函数，所以defer的数据结构跟一般函数类似，也有栈指针、程序计数器、函数地址等等。与函数不同的是它含有一个指针，可用于指向另一个defer，每个goroutine数据结构中实际上也有一个defer指针，该指针指向一个defer的链表，每次声明一个defer时就将defer插入到单链表表头，每次执行defer就从单链表表头取出一个defer执行。

如图所示，新声明的defer（B()）总是添加到链表头部，函数返回前执行defer则是从链表首部依次取出执行，形成一个栈结构。

defer的功能

defer用来声明一个延迟函数，可以定义多个延时函数，这些函数会放到一个栈中，当函数执行到最后时，这些defer语句会按照逆序执行，最后该函数返回。

通常用defer来做一些资源释放，比如关闭io操作。i input o output 输入输出

1、defer 的执行顺序

一个函数中使用多个defer时，它们是一个 “栈” 的关系，也就是先进后出，先在后面的defer先执行。

func main() {
   defer func1()
   defer func2()
   defer func3()
}
func func1() {
   fmt.Print("A")
}
func func2() {
   fmt.Print("B")
}
func func3() {
   fmt.Print("C")
}

执行输出为：C B A

2、defer 与 return 谁先谁后

根据代码运行情况可以理解为：return 之后的语句先执行，defer 后的语句后执行。不过，defer执行时是可以改变return中的返回值的。

3、当defer被声明时，其参数就会被实时解析

func a() {
	i := 0
	defer fmt.Println(i)
	i++
	return
}

运行结果是0 这是因为defer后面定义的是一个带变量的函数: fmt.Println(i). 但这个变量(i)在defer被声明的时候，就已经确定值了，这里的变量为整型为值传递，个人理解是为defer后的函数拷贝了一个i变量且=0。

但若defer后的函数不带变量呢：

func a() {
	i := 0
	defer func() {//defer1
		i++//2+1
		fmt.Println("a defer1:", i)//i=3
	}()
	defer func() {//defer2
		i++//1+1
		fmt.Println("a defer2:", i)//i=2
	}()
	i++//i=1
}
func main() {
	a()
}

运行结果：

a defer2: 2

a defer1: 3

无变量传入，即使defer的函数内部有外部定义的变量也不会在defer声明的时候确定值，将在外部函数执行完返回的时候依次执行相应操作（i++）。

4、有名函数返回值遇见 defer 情况

先 return，再 defer，所以在执行完 return 之后，还要再执行 defer 里的语句，依然可以修改本应该返回的结果。

a.已定义返回值：

func DeferFunc1(i int) (t int) {
	t = i
	defer func() {
		t += 3
	}()
	return t
}
func main()  {
	fmt.Println(DeferFunc1(1))
}

运行结果：4

  • 将返回值 t 赋值为传入的 i，此时 t 为 1

  • 执行 return 语句将 t 赋值给 t（等于啥也没做）

  • 执行 defer 方法，将 t + 3 = 4

  • 函数返回 4

    因为 t 的作用域为整个函数所以修改有效。

b.未定义返回值：

func DeferFunc2(i int) int {
	t := i
	defer func() {
		t += 3
	}()
	return t
}
func main()  {
	fmt.Println(DeferFunc2(1))
}

运行结果：1

  • 创建变量 t 并赋值为 1
  • 执行 return 语句，注意这里是将 t 赋值给返回值，此时返回值为 1（这个返回值并不是 t）
  • 执行 defer 方法，将 t + 3 = 4
  • 函数返回返回值 1

5、defer 遇见 panic a.第一种情况：遇到panic不捕获

func main() {
	defer fmt.Println("defer1")
	defer fmt.Println("defer2")
	panic("发生异常")
	defer fmt.Println("defer3")
}

运行结果：

defer2 defer1 panic: 发生异常

panic后的defer不会入栈（后面的代码运行不到）。

b.第二种情况：defer 遇见 panic，并捕获异常

func defer_call() {
	defer func() {
		fmt.Println("defer: panic 之前1, 捕获异常")
		if err := recover(); err != nil {
			fmt.Println(err)
		}
	}()
	defer func() { fmt.Println("defer: panic 之前2, 不捕获") }()

	panic("异常内容")  //触发defer出栈

	defer func() { fmt.Println("defer: panic 之后, 永远执行不到") }()
}
func main() {
	defer_call()

	fmt.Println("main 正常结束")
}

运行结果：

defer: panic 之前2, 不捕获 defer: panic 之前1, 捕获异常 异常内容 main 正常结束

defer 最大的功能是 panic 后依然有效，main函数正常运行，所以 defer 可以保证你的一些资源一定会被关闭，从而避免一些异常出现的问题。

c.第三种情况：defer中含panic

func main()  {
	defer func() {
		if err := recover(); err != nil{
			fmt.Println(err)
		}else {
			fmt.Println("fatal")
		}
	}()
	defer func() {
		panic("defer panic1")
	}()
	defer func() {
		panic("defer panic2")
	}()
	panic("panic")
}

运行结果：defer panic1

触发 panic(“panic”) 后 defer 顺序出栈执行，第一个被执行的 defer 中有 panic(“defer panic”) 异常语句，这个异常将会覆盖掉 main 中的异常 panic(“panic”)，“defer panic1"又会覆盖掉"defer panic2”，最后这个异常被栈底的defer捕获到。

6、 defer 下的函数参数包含子函数

func function(index int, value int) int {
	fmt.Print(index)
	return index
}

func main() {
	defer function(1, function(3, 0))
	defer function(2, function(4, 0))
}

运行结果：3 4 2 1

这里，有 4 个函数，他们的 index 序号分别为 1，2，3，4。那么这 4 个函数的先后执行顺序是什么呢？这里面有两个 defer， 所以 defer 一共会压栈两次，先进栈 1，后进栈 2。 那么在压栈 function1 的时候，需要连同函数地址、函数形参一同进栈，那么为了得到 function1 的第二个参数的结果，所以就需要先执行 function3 将第二个参数算出，那么 function3 就被第一个执行。同理压栈 function2，就需要执行 function4 算出 function2 第二个参数的值。然后函数结束，先出栈 fuction2、再出栈 function1.

defer函数的使用场景 #

延迟Close、recover panic

垃圾回收(GC) #

标记清除 #

此算法主要有两个主要的步骤：

标记(Mark phase)

清除(Sweep phase)

第一步，找出不可达的对象，然后做上标记。 第二步，回收标记好的对象。

操作非常简单，但是有一点需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即 stop the world。 也就是说，这段时间程序会卡在哪儿。故中文翻译成卡顿.

标记-清扫(Mark And Sweep)算法存在什么问题？ 标记-清扫(Mark And Sweep)算法这种算法虽然非常的简单，但是还存在一些问题：

STW，stop the world；让程序暂停，程序出现卡顿。

标记需要扫描整个heap

清除数据会产生heap碎片 这里面最重要的问题就是：mark-and-sweep 算法会暂停整个程序。

三色并发标记法 #

首先：程序创建的对象都标记为白色。

gc开始：扫描所有可到达的对象，标记为灰色

从灰色对象中找到其引用对象标记为灰色，把灰色对象本身标记为黑色

监视对象中的内存修改，并持续上一步的操作，直到灰色标记的对象不存在

此时，gc回收白色对象

最后，将所有黑色对象变为白色，并重复以上所有过程。

插入写屏障 #

当一个对象引用另外一个对象时，将另外一个对象标记为灰色。

插入屏障仅会在堆内存中生效，不对栈内存空间生效，这是因为go在并发运行时，大部分的操作都发生在栈上，函数调用会非常频繁。数十万goroutine的栈都进行屏障保护自然会有性能问题。

如果一个栈对象 黑色引用白色对象，白色对象依然会被当作垃圾回收。

因此，最后还需要对栈内存进行STW，重新rescan，确保所有引用的被引用的栈对象都不会被回收。

删除写屏障 #

当一个白色对象被另外一个对象解除引用时，将该被引用对象标记为灰色（白色对象被保护）

缺点：产生内存冗余，如果上述该白色对象没有被别的对象引用，相当于还是垃圾，但是这一轮垃圾回收并没有处理掉他。

混写屏障 #

当gc进行中时，创建一个对象，按照三色标记法的步骤，对象会被标记为白色，这样新生成的对象最后会被清除掉，这样会影响程序逻辑。

golang引入写屏障机制，可以监控对象的内存修改，并对对象进行重新标记。

gc一旦开始，无论是创建对象还是对象的引用改变，都会先变为灰色。

GC触发机制 #

GC 的触发情况主要分为两大类，分别是：

  1. 系统触发：运行时自行根据内置的条件，检查、发现到，则进行 GC 处理，维护整个应用程序的可用性。

    • a. 使用系统监控，当超过两分钟没有产生任何GC时，强制触发 GC；

    • b.使用步调（Pacing）算法，其核心思想是控制内存增长的比例,当前内存分配达到一定比例则触发

  2. 手动触发：开发者在业务代码中自行调用 runtime.GC 方法来触发 GC 行为。

Map #

底层原理 #

这种类型最大的特点就是查找速度非常快，因为它的底层存储是基于哈希表存储的。

Go中的map是一个指针，占用8个字节，指向hmap结构体。

hmap包含若干结构为bmap的数组，每个bmap底层都采用链表结构，bmap通常叫bucket。

hmap结构体

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

bmap结构体

bmap 就是我们常说的“桶”，一个桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果的低B位是相同的，关于key的定位我们在map的查询中详细说明。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置)。

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

上面bmap结构是静态结构，在编译过程中runtime.bmap会拓展成以下结构体：

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

tophash就是用于实现快速定位key的位置，在实现过程中会使用key的hash值的高8位作为tophash值，存放在bmap的tophash字段中

tophash字段不仅存储key哈希值的高8位，还会存储一些状态值，用来表明当前桶单元状态，这些状态值都是小于minTopHash的

为了避免key哈希值的高8位值和这些状态值相等，产生混淆情况，所以当key哈希值高8位若小于minTopHash时候，自动将其值加上minTopHash作为该key的tophash。桶单元的状态值如下：

emptyRest      = 0 // 表明此桶单元为空，且更高索引的单元也是空
emptyOne       = 1 // 表明此桶单元为空
evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
evacuatedEmpty = 4 // 用于表示此单元已迁移
minTopHash     = 5 // key的tophash值与桶状态值分割线值，小于此值的一定代表着桶单元的状态，大于此值的一定是key对应的tophash值
func tophash(hash uintptr) uint8 {
  top := uint8(hash >> (goarch.PtrSize*8 - 8))
  if top < minTopHash {
    top += minTopHash
  }
  return top
}

mapextra结构体

当map的key和value都不是指针类型时候，bmap将完全不包含指针，那么gc时候就不用扫描bmap。bmap指向溢出桶的字段overflow是uintptr类型，为了防止这些overflow桶被gc掉，所以需要mapextra.overflow将它保存起来。如果bmap的overflow是*bmap类型，那么gc扫描的是一个个拉链表，效率明显不如直接扫描一段内存(hmap.mapextra.overflow)

type mapextra struct {
overflow    *[]*bmap // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
oldoverflow *[]*bma // oldoverflow 包含扩容时 hmap.oldbuckets 的 overflow 的 bucket
nextOverflow *bmap  // 指向空闲的 overflow bucket 的指针
}

总结

bmap（bucket）内存数据结构可视化如下:

注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式，当key和value类型不一样的时候，key和value占用字节大小不一样，使用key/value这种形式可能会因为内存对齐导致内存空间浪费，所以Go采用key和value分开存储的设计，更节省内存空间

实现Map的并发安全 #

sync.Map，底层实际上用了一个Map缓存

go 的map并不是协程安全的，

不要以共享内存的方式来通讯，相反，要经过通讯来共享内存

实现Map的有序查找 #

利用一个辅助slice

Map可以用数组作为Key吗 #

Golang中的map的key必须是可以比较的，可以使用==运算符进行比较。

因slice，map，function不可以比较，所以不能作为key

int、string、bool、array数组、channel、指针可以，以及包含前面类型的struct。

因为切片是引用类型，并且不可比较.

  • 引用类型，比较地址没有意义。
  • 切片有len，cap，比较的维度不好衡量，因此go设计的时候就不允许切片可以比较。

由于map中的value可以是slice，这就使得包含slice的结构体包括函数，结构体等也是不可比较的。这里的不可比较结构体是包含slice的结构体！

因此map是不可比较的，自然不能作为map的key，而value是任意类型。