数据结构

​ 这篇文章带大家一起了解一下 数组、切片、哈希表、字符串四种数据结构。

一、数组

1、概述

​ 数组作为一种基本的数据结构，通过我们会从两个维度去描述它，也就是数组中存储的元素类型和数组最大能存储的元素个数，如下

[10]int
[200]interface

​ Go 语言数组在初始化之后，大小就无法改变，只有存储元素类型相同且大小相同的数组类型才是同一类型的数组。

​ 编译期间的数组类型是由 cmd/compile/internal/types.NewArray 函数生成的，包含了两个字段：元素类型 elem 和 数组大小 bound，这两个字段共同构成了数组类型。

func NewArray(elem *Type, bound int64) *Type {
	// 检查数组的大小是否小于0
	if bound < 0 {
		base.Fatalf("NewArray: invalid bound %v", bound)
	}
	// 创建一个新的数组类型对象
	t := newType(TARRAY)
	// 设置数组类型的额外信息，包括元素类型和大小
	t.extra = &Array{Elem: elem, Bound: bound}
	// 根据元素类型的NotInHeap属性设置数组类型的NotInHeap属性
	t.SetNotInHeap(elem.NotInHeap())
	// 返回新创建的数组类型
	return t
}

2、初始化

​ Go 语言的数组有两种不同的创建方式，一种是显示地指定数组大小，一种是使用 [...]T 声明数组，Go 语言会在编译期间通过源代码推到数组的大小。

arr1 := [3]int{1, 2, 3}
arr2 := [...]int{1, 2, 3}

​ 这两种声明方式在运行期间得到的结果是完全相同的，后一种声明方式会在编译期间转换成前一种，也就是编译器对数组大小的推导。下面介绍编译器推到的过程。

上限推导

​ 两种不同的声明方式，会导致编译器做出完全不同的处理。

1. 使用第一种方式 [10] T，那么变量的类型在编译进行到类型检查阶段就会被提取出来，随后使用 cmd/compile/internal/types.NewArray创建包含数组大小的 cmd/compile/internal/types.Array 结构体。

2. 当我们使用 [...]T 的方式声明数组时，编译器会在的 cmd/compile/internal/gc.typecheckcomplit 函数中对该数组的大小进行推导：

   func typecheckcomplit(n *Node) (res *Node) {
   	// ...
   	// 如果数组的类型是切片和字面量 "..." 则处理
   	if n.Right.Op == OTARRAY && n.Right.Left != nil && n.Right.Left.Op == ODDD {
   		// 对数组中元素的类型进行类型检查
   		n.Right.Right = typecheck(n.Right.Right, ctxType)
   		// 如果元素类型为空，则清除节点类型并返回节点
   		if n.Right.Right.Type == nil {
   			n.Type = nil
   			return n
   		}
   		// 获取元素类型
   		elemType := n.Right.Right.Type
   		// 通过 typecheckarraylit 计算数组中元素的数量
   		length := typecheckarraylit(elemType, -1, n.List.Slice(), "array literal")
   		// 将节点的操作修改为 OARRAYLIT
   		n.Op = OARRAYLIT
   		// 根据元素类型和计算出的长度创建新的数组类型
   		n.Type = types.NewArray(elemType, length)
   		// 清除右子节点
   		n.Right = nil
   		// 返回修改后的节点
   		return n
   	}
   	// ...
   }

   在上面这个函数中，会通过遍历元素的方式来计算数组中元素的数量。

   所以我们可以看出 [...]T{1, 2, 3} 和 [3]T{1, 2, 3} 在运行时是完全等价的

语句转换

​ 对于一个由字面量组成的数组，根据数组元素数量的不同，编译器会在负责初始化字面量的 cmd/compile/internal/gc.anylit 函数中做两种不同的优化：

1. 当元素数量小于或者等于 4 个时，会直接将数组中的元素放置在栈上；
2. 当元素数量大于 4 个时，会将数组中的元素放置到静态区并在运行时取出；

​ 当数组的元素小于或者等于四个时，cmd/compile/internal/gc.fixedlit 会负责在函数编译之前将 [3]{1, 2, 3} 转换成更加原始的语句， cmd/compile/internal/gc.fixedlit 函数接收的 kind 是 initKindLocalCode 时，上述代码会将原有的初始化语句 [3]int{1, 2, 3} 拆分成一个声明变量的表达式和几个赋值表达式，这些表达式会完成对数组的初始化，如下：

var arr [3]int
arr[0] = 1
arr[1] = 2
arr[2] = 3

​ 但是如果当前数组的元素大于四个，cmd/compile/internal/gc.anylit 会先获取一个唯一的 staticname，然后调用 cmd/compile/internal/gc.fixedlit 函数在静态存储区初始化数组中的元素并将临时变量赋值给数组，如下：

var arr [5]int
statictmp_0[0] = 1
statictmp_0[1] = 2
statictmp_0[2] = 3
statictmp_0[3] = 4
statictmp_0[4] = 5
arr = statictmp_0

​ 总结一下就是：在不考虑逃逸分析的情况下，如果数组中的元素个数小于或者等于 4 个，那么所有的变量会直接在栈上初始化；否则，变量就会在静态存储区初始化，然后拷贝到栈上。转换后的代码才会继续进入中间代码生成和机器猫生成两个阶段，最后生成可执行的二进制文件。

3、访问和赋值

​ 无论是在栈上还是静态存储区，数组在内存中都是一连串的内存空间，我们通过指向数组开头的指针、元素的数量以及元素类型占的空间大小表示数组。如果我们不知道数组中元素的数量，访问时可能发生越界；而如果不知道数组中元素类型的大小，就没有办法知道应该一次取出多少字节的数据，无论丢失了哪个信息，我们都无法知道这片连续的内存空间到底存储了什么数据。

​ 数组访问越界是非常严重的错误，Go 语言中可以在编译期间的静态类型检查判断数组越界，cmd/compile/internal/gc.typecheck1 会验证访问数组的索引：

func typecheck1(n *Node, top int) (res *Node) {
	switch n.Op {
	case OINDEX:
		ok |= ctxExpr
		l := n.Left  
		r := n.Right 
		// 根据左操作数的类型进行不同处理
		switch n.Left.Type.Etype {
		// 对于字符串、数组和切片类型
		case TSTRING, TARRAY, TSLICE:
			// ...
			// 如果索引类型不是整数，报错并中断处理
			if n.Right.Type != nil && !n.Right.Type.IsInteger() {
				yyerror("non-integer array index %v", n.Right)
				break
			}
			// 如果索引没有限制且是整数常量
			if !n.Bounded() && Isconst(n.Right, CTINT) {
				// 获取整数值
				x := n.Right.Int64()
				// 如果索引小于0，报错（索引必须为非负数）
				if x < 0 {
					yyerror("invalid array index %v (index must be non-negative)", n.Right)
				} else if n.Left.Type.IsArray() && x >= n.Left.Type.NumElem() {
					// 如果是数组类型且索引越界，报错
					yyerror("invalid array index %v (out of bounds for %d-element array)", n.Right, n.Left.Type.NumElem())
					// ...
}

1. 访问数组的索引是非整数时，报错 “non-integer array index %v”；
2. 访问数组的索引是负数时，报错 “invalid array index %v (index must be non-negative)”；
3. 访问数组的索引越界时，报错 “invalid array index %v (out of bounds for %d-element array)”；

​ 数组和字符串的一些简单越界错误都会在编译期间发现，如：直接使用证书或者常量访问数组；但是如果使用变量去访问数组或者字符串时，编译器无法提前发现错误，就需要 Go 语言运行时阻止不合法的访问：

arr[4]: invalid array index 4 (out of bounds for 3-element array)
arr[i]: panic: runtime error: index out of range [4] with length 3

​ Go 语言运行时在发现数组、切片和字符串的越界操作会由运行时的 runtime.panicIndex 和 runtime.goPanicIndex 触发程序的运行时错误并导致崩溃退出：

TEXT runtime·panicIndex(SB),NOSPLIT,$0-8
	// runtime·panicIndex是运行时处理数组越界访问的函数。
	MOVL	AX, x+0(FP)      // 将寄存器AX中的x参数存储到栈帧的偏移0(FP)位置。
	MOVL	CX, y+4(FP)      // 将寄存器CX中的y参数存储到栈帧的偏移4(FP)位置。
	JMP	runtime·goPanicIndex(SB)  // 跳转到runtime·goPanicIndex函数进行错误处理。

// goPanicIndex是用于处理数组越界访问的运行时函数。
func goPanicIndex(x int, y int) {
	// 获取调用goPanicIndex函数的调用者的程序计数器（PC）。
	panicCheck1(getcallerpc(), "index out of range")
	// 创建boundsError结构体，其中包含有关数组越界错误的信息。
	// - x: 数组索引
	// - signed: 是否为有符号整数索引
	// - y: 数组的长度
	// - code: 错误代码（在这里是boundsIndex）
	panic(boundsError{x: int64(x), signed: true, y: y, code: boundsIndex})
}

4、小结

1. 数组概述：数组是一种基本的数据结构，它由两个维度描述：存储的元素类型和数组的最大容量（大小）。例如，[10]int 表示一个包含10个整数的数组，而 [200]interface{} 表示一个包含200个任意类型的元素的数组。
2. 数组大小不可改变：在Go语言中，一旦数组被初始化，其大小（容量）无法更改。只有当数组的元素类型和大小完全相同时，它们才被认为是相同类型的数组。
3. 数组类型生成：在编译期间，数组的类型由 cmd/compile/internal/types.NewArray 函数生成，它包含两个关键字段：元素类型 elem 和数组大小 bound。
4. 初始化数组：Go语言支持两种不同的数组初始化方式。一种是显式指定数组大小，另一种是使用 [...]T 声明数组，编译器将在编译时推断数组大小。这两种方式在运行时具有相同的效果。
5. 数组大小推导：数组大小推导是通过编译器进行的。当使用 [10]T 的方式声明数组时，大小在编译期间被提取为类型信息。对于 [...]T 声明，编译器使用 cmd/compile/internal/gc.typecheckcomplit 函数在编译期间计算数组大小。
6. 数组初始化转换：编译器进行数组初始化转换，根据元素数量的不同，将数组初始化放在栈上或静态存储区。这可以优化性能，避免过多的栈内存操作。
7. 数组访问和越界检查：Go编译器在编译期间执行数组访问的静态类型检查，检查索引是否合法。它检查索引是否为整数、非负数以及是否越界。数组访问越界是一个严重的错误，可以在编译期间或运行时被检测到。
8. 数组越界运行时处理：在运行时，Go会使用 runtime.panicIndex 和 runtime.goPanicIndex 处理数组越界访问错误。这会导致程序崩溃，并提供有关越界的信息，如越界索引和数组大小。

二、切片

1、概述

​ 数组在 Go 语言中没有那么常用，更常用的数据结构是切片，即动态数组，其长度并不固定，我们可以向切片中追加元素，它会在容量不足时自动扩容。

​ 声明方式与数组相似，但只需要指定切片的元素类型即可：

[]int
[]interface

​ 切片的类型在编译期间会由 cmd/compile/internal/types.NewSlice 函数生成，只包含切片中的元素类型，即 int 或者 interface等。

func NewSlice(elem *Type) *Type {
	if t := elem.Cache.slice; t != nil {
		if t.Elem() != elem {
			Fatalf("elem mismatch")
		}
		return t
	}

	t := New(TSLICE)
	t.Extra = Slice{Elem: elem}
	elem.Cache.slice = t
	return t
}

​ 该方法会返回一个只包含切片内元素类型的结构，即切片内元素的类型是在编译期间确定的，存储在 Extra 字段中，供程序运行时动态获取。

2、数据结构

​ 切片的底层数据结构是用 reflect.SliceHeader 结构体表示的，如下：

type SliceHeader struct {
	Data uintptr // 指向数组的指针
	Len  int	 // 当前切片的长度
	Cap  int	 // 当前切片的容量
}

​ Data 是一片连续的内存空间，用于存储切片中的全部元素，我们可以将切片理解成一片连续的内存空间加上长度和容量的标识。

​ 从图中我们可以看到，切片较数组来说，相当于是引入了一个抽象层，对数组中部分连续的片段进行了引用，我们在运行期间可以修改它的长度和范围。当切片底层数组的长度不足时，就会触发扩容，切片指向的数组会发生变化，此后再对切片进行修改，原始底层数组就不会发生改变了。

3、初始化

​ Go 中切片的初始化方式由三种：

1. 通过下标的方式获取数组或切片的一部分

   arr[0:3] or slice[0:3]

2. 使用字面量初始化新的切片

   slice := []int{1, 2, 3}

3. 使用关键字 make 创建切片

   slice := make([]int, 10)

使用下标

package opslicemake

func newSlice() []int {
	arr := [3]int{1, 2, 3}
	slice := arr[0:1]
	return slice
}

​ 使用下标创建切片，编译器会通过 SliceMake 操作，接收四个参数 元素类型、数组指针、切片大小和容量 来创建新的切片，这里的容量是继承自原数组的容量。需要注意的是，使用下标初始化并不会拷贝原数组或者原切片的数据，它只会创建一个指向原数组的切片结构体，包含一个指向原数组的指针，所以修改新切片的数据，也会修改原切片。

使用字面量

​ 当我们使用字面量 []int{1, 2, 3} 创建切片的时候，cmd/compile/internal/gc.slicelit 函数会在编译期间将它展开成如下所示的代码片段：

var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice := vauto[:]

1. 根据切片中的元素数量对底层数组的大小进行判断并创建一个数组
2. 将这些字面量存储到初始化的数组中
3. 创建一个同样指向 [3]int 类型的数组指针
4. 将静态存储区的数组 vstat 赋值给 vauto 指针所在的地址
5. 通过 [:] 操作获取一个底层使用vauto的切片

​ 从第 5 步可以看出，使用字面量创建切片的方式本质上也是使用下标进行创建。

关键字

​ 使用 make 关键字 创建切片时，很多工作需要运行时的参与；调用方必须向 make 函数传入切片的大小以及可选的容量，然后类型检查期间会通过 cmd/compile/internal/gc.typecheck1 函数校验参数是否正确：

func typecheck1(n *Node, top int) (res *Node) {
	switch n.Op {
		...
		case OMAKE:
			args := n.List.Slice()
			i := 1
			switch t.Etype {
			case TSLICE:
                // 长度必须包含
				if i >= len(args) {
					yyerror("make(%v)缺少长度参数", t) // 报告编译错误，并返回原始节点 n
					return n
				}
				// 提取长度参数。
				l := args[i]
				i++
				var r *Node
				if i < len(args) {
					// 如果存在，提取容量参数。
					r = args[i]
				}
				...
				// 检查在 make([]T, len, cap) 中长度是否大于容量。
				if Isconst(l, CTINT) && r != nil && Isconst(r, CTINT) && l.Val().U.(*Mpint).Cmp(r.Val().U.(*Mpint)) > 0 {
					yyerror("在make(%v)中，长度大于容量", t)	// 报告编译错误，并返回原始节点 n
					return n
				}
				n.Left = l
				n.Right = r
				n.Op = OMAKESLICE
			}
		...
	}
}

​ 该函数会检查 len 是否传入，且传入的容量 cap 一定要大于等于 长度 len。

​ 在参数校验后，当前函数还会将该节点的操作修改为切片操作，即OMAKESLICE，中间代码生成的 cmd/compile/internal/gc.walkexpr 函数会依据下面两个条件转换 OMAKESLICE 类型的节点：

1. 切片的大小和容量是否足够小
2. 切片是否发生了逃逸，最终在堆上初始化

​ 当切片发生逃逸或者非常大时，运行时需要 runtime.makeslice 在堆上初始化切片，如果当前的切片不会发生逃逸并且切片非常小的时候，make([]int, 3, 4) 会被直接转换成如下所示的代码：

var arr [4]int
n := arr[:3]

​ 可以看到，也是通过下标 [:3] 得到数组对应的切片，这两部分都会在编译阶段完成。

​ 然后再看运行时创建切片的函数 runtime.makeslice，

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // 计算所需内存和溢出检查
    mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    if overflow || mem > maxAlloc || len < 0 || len > cap {
        mem, overflow := math.MulUintptr(et.size, uintptr(len))
        if overflow || mem > maxAlloc || len < 0 {
            // 切片长度异常，触发异常
            panicmakeslicelen()
        }
        // 切片容量异常，触发异常
        panicmakeslicecap()
    }
    // 分配内存并返回指针
    return mallocgc(mem, et, true)
}

​ 上述函数主要会为切片计算出所占用的内存空间，并在校验完成后，于堆上分配一片连续的内存：计算方式内存空间 = 切片中元素大小 × 切片容量，使用 runtime.mallocgc 函数根据对象大小进行内存分配，过程中

​ 分配内存前，会进行如下几方面的校验：

1. 内存空间的大小是否发生了溢出；
2. 申请的内存大于最大可分配的内存；
3. 传入的长度小于 0 或者长度大于容量；

4、访问元素

​ 编译器将 len(slice) 和 cap(slice) 视为特殊操作，分别用 OLEN 和 OCAP 标识，并在 SSA 生成阶段将它们转换为 OpSliceLen 和 OpSliceCap 操作，以获取切片的长度和容量。此优化有助于在编译期间减少运行时的开销。

​ 通过 “decompose builtin” 优化，编译器在某些情况下会直接替换 len(slice) 和 cap(slice) 为切片的实际长度和容量，从而进一步提高程序性能。

​ 编译器对切片元素的访问也有进行优化，将 OINDEX 操作转换为直接访问切片地址的操作，以减少运行时成本。

​ 其实，大部分切片操作都在编译期间完成，包括切片遍历的优化，将包含 range 关键字的切片遍历转换为更简单的循环结构，以提高代码效率。这些优化和转换确保切片操作在运行时具有更高的性能，同时帮助编译器生成更有效的代码。

5、追加和扩容

​ 使用 append 关键字向切片追加元素也是常见操作，中间代码生成阶段的 cmd/compile/internal/gc.state.append 方法会根据返回值是否会覆盖原变量，选择进入两种流程，如果 append 返回的新切片不需要赋值回原有的变量，就会进入如下的处理流程：

// append(slice, 1, 2, 3)
//  解析切片结构体，获取数组指针、长度、容量
ptr, len, cap := slice
// 追加后切片长度
newlen := len + 3
// 追加后长度大于容量，需要扩容
if newlen > cap {
    ptr, len, cap = growslice(slice, newlen)
    newlen = len + 3
}
// 将新的元素依次加入切片中
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)

​ 我们会先解构切片结构体获取它的数组指针、大小和容量，如果在追加元素后切片的大小大于容量，那么就会调用 runtime.growslice 对切片进行扩容并将新的元素依次加入切片。

​ 如果会覆盖原切片，这时 cmd/compile/internal/gc.state.append 方法会使用另一种方式展开关键字：

// slice = append(slice, 1, 2, 3)
//  解析切片结构体，获取数组指针、长度、容量
a := &slice
ptr, len, cap := slice
newlen := len + 3
// 检查是否需要扩容
if uint(newlen) > uint(cap) {
   // 扩容
   newptr, len, newcap = growslice(slice, newlen)
   vardef(a) // 定义 a 为指向切片的指针
   *a.cap = newcap // 更新切片容量
   *a.ptr = newptr // 更新切片指针
}
// 更新长度
newlen = len + 3
*a.len = newlen
// 追加新元素
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3

​ 是否覆盖原变量的逻辑其实差不多，最大的区别在于得到的新切片是否会赋值回原变量。如果我们选择覆盖原有的变量，就不需要担心切片发生拷贝影响性能，因为 Go 语言编译器已经对这种常见的情况做出了优化。

​ 上面是对于切片容量足够时，向切片中追加元素的分析，接下来我们再来分析一下当切片容量不足时，如何处理。

​ 当切片的容量不足时，我们会调用 runtime.growslice 函数为切片扩容，扩容是为切片分配新的内存空间并拷贝原切片中元素的过程，先来看看新切片的容量是如何确定的：

func growslice(et *_type, old slice, cap int) slice {
	newcap := old.cap
	doublecap := newcap + newcap
    // 期望容量大于当前容量的两倍就会使用期望容量
	if cap > doublecap {
		newcap = cap
	} else {
        // 当前切片的长度小于 1024 就会将容量翻倍
		if old.len < 1024 {
			newcap = doublecap
		} else {
            // 当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

​ 新切片容量的确定，运行时会根据切片当前的容量以及当前切片的长度选择不同的策略进行扩容：

1. 如果期望容量大于当前容量的两倍就会使用期望容量
2. 如果当前切片的长度小于 1024 就会将容量翻倍
3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新的容量大于期望容量；

​ 上面只会初步确定切片的大致容量，实际上还需要根据切片中的元素大小进行内存对齐，以此来提高访问效率。当数组中元素所占的字节大小为 1、 8 或者 2 的倍数时，运行时会使用如下的代码进行内存对齐：

var overflow bool    // 检测内存是否溢出
var lenmem, newlenmem, capmem uintptr  // 用于存储长度和容量的内存地址

// 根据元素类型的大小进行不同的计算
switch {
case et.size == 1: // 如果元素大小为1字节
    lenmem = uintptr(old.len)          // 旧切片的长度
    newlenmem = uintptr(cap)            // 新的切片长度
    capmem = roundupsize(uintptr(newcap)) // 新的切片容量，需要对齐
    overflow = uintptr(newcap) > maxAlloc // 检查是否发生内存溢出
    newcap = int(capmem)                // 更新新的切片容量
case et.size == sys.PtrSize:  // 如果元素大小等于指针大小
    lenmem = uintptr(old.len) * sys.PtrSize  // 旧切片的长度
    newlenmem = uintptr(cap) * sys.PtrSize    // 新的切片长度
    capmem = roundupsize(uintptr(newcap) * sys.PtrSize)  // 新的切片容量，需要对齐
    overflow = uintptr(newcap) > maxAlloc/sys.PtrSize  // 检查是否发生内存溢出
    newcap = int(capmem / sys.PtrSize)           // 更新新的切片容量
case isPowerOfTwo(et.size):  // 如果元素大小是2的幂次方
    // 进行其他计算...
default:
    // 处理其他情况...
}

​ 内存对齐就是使用 runtime.roundupsize 函数，它会将带申请的内存向上取整，取整时使用 runtime.class_to_size 数组，使用该数组中的整数可以提高内存的分配效率并减少碎片

var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, ...,}

​ 在默认情况下，我们会将目标容量和元素大小相乘得到占用的内存。如果计算新容量时发生了内存溢出或者请求内存超过上限，就会直接崩溃退出程序。

var overflow bool    // 检测内存是否溢出
var newlenmem, capmem uintptr  // 用于存储长度和容量的内存地址switch {
    // 处理其他情况...
default:
    // 计算新的内存大小，包括长度和容量
    lenmem = uintptr(old.len) * et.size
    newlenmem = uintptr(cap) * et.size
    // 使用 math 包中的函数计算新的容量并对其进行对齐
    capmem, _ = math.MulUintptr(et.size, uintptr(newcap))
    capmem = roundupsize(capmem)
    newcap = int(capmem / et.size)
}
// 初始化 p 变量用于分配内存
var p unsafe.Pointer
// 检查元素类型是否包含指针，以决定是否需要清除内存
if et.kind&kindNoPointers != 0 {
    p = mallocgc(capmem, nil, false)
    memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
    p = mallocgc(capmem, et, true)
    
    // 启用写屏障（write barrier）用于 GC
    if writeBarrier.enabled {
        bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
    }
}
// 复制旧切片的数据到新分配的内存中
memmove(p, old.array, lenmem)
// 返回新的切片，包括新的底层数内存地址、长度和容量
return slice{p, old.len, newcap}

​ 如果切片中元素不是指针类型，那么会调用 runtime.memclrNoHeapPointers 将超出切片当前长度的位置清空并在最后使用 runtime.memmove 将原数组内存中的内容拷贝到新申请的内存中，然后再将超出的部分重新追加到新内存中。

var arr []int64
arr = append(arr, 1, 2, 3, 4, 5)

​ 当我们执行上述代码时，会触发 runtime.growslice 函数扩容 arr 切片并传入期望的新容量 5，这时期望分配的内存大小为 40 字节；不过因为切片中的元素大小等于 sys.PtrSize，所以运行时会调用 runtime.roundupsize 向上取整内存的大小到 48 字节，所以新切片的容量为 48 / 8 = 6。

6、拷贝切片

​ 当我们使用 copy(a, b) 的形式对切片进行拷贝时，编译期间的 cmd/compile/internal/gc.copyany 也会分两种情况进行处理拷贝操作，如果当前 copy 不是在运行时调用的，copy(a, b) 会被直接转换成下面的代码：

n := len(a)
if n > len(b) {
    n = len(b)
}
if a.ptr != b.ptr {
    memmove(a.ptr, b.ptr, n*sizeof(elem(a))) 
}

​ runtime.memmove 会负责拷贝内存。如果拷贝是发生在运行时，例如：go copy(a, b)，编译器会使用 runtime.slicecopy 替换运行期间调用的 copy：

func slicecopy(to, fm slice, width uintptr) int {
	// 如果源切片或目标切片的长度为 0，不进行复制，返回 0
	if fm.len == 0 || to.len == 0 {
		return 0
	}
	n := fm.len
	// 如果目标切片的长度小于源切片的长度，只复制目标切片长度的数据
	if to.len < n {
		n = to.len

	// 如果元素宽度为 0，不执行复制操作，返回长度 n
	if width == 0 {
		return n
	}
	// 计算需要复制的总字节数
	size := uintptr(n) * width
	// 如果复制的字节数为 1，直接复制单个字节数据
	if size == 1 {
		*(*byte)(to.array) = *(*byte)(fm.array)
	} else {
		// 否则，使用 memmove 函数复制数据
		memmove(to.array, fm.array, size)
	}
	// 返回成功复制的元素个数
	return n
}

​ 无论是编译期间拷贝还是运行时拷贝，两种拷贝方式都会通过 runtime.memmove 将整块内存的内容拷贝到目标的内存区域中：

​ 相比于依次拷贝元素，runtime.memmove 能够提供更好的性能。

7、小结

​ 下面是对上面内容的一个小结：

1. 概述： 介绍了 Go 语言中切片的特性，切片是一种动态数组，可以自动扩容，与数组相似但长度可变。切片的类型在编译时确定，但长度和容量可以在运行时变化。

2. 数据结构： 描述了切片的底层数据结构，即 reflect.SliceHeader，包含指向数组的指针、长度和容量信息。

3. 初始化： 介绍了三种初始化切片的方式：通过下标、使用字面量、使用 make 关键字。解释了编译器在背后的工作，包括基于切片元素的大小来选择不同的策略。

4. 访问元素： 提到编译器优化 len(slice) 和 cap(slice)，以及如何将 OINDEX 操作优化为直接访问切片地址。

5. 追加和扩容： 解释了使用 append 进行元素追加的过程，包括扩容策略，内存对齐，以及内存的分配和拷贝。

6. 拷贝切片： 详细说明了编译期和运行时两种不同情况下的切片拷贝操作，使用 copy(a, b) 的编译时优化以及运行时的拷贝函数 slicecopy，还解释了底层内存的拷贝过程。

这些内容详细介绍了 Go 语言中切片的内部工作机制，包括初始化、访问、扩容和拷贝等方面的细节，有助于理解切片的性能和使用。

三、哈希表

1、设计原理

​ 哈希表是计算机科学中的最重要数据结构之一，这不仅因为它 O(1) 的读写性能非常优秀，还因为它提供了键值之间的映射。想要实现一个性能优异的哈希表，需要注意两个关键点 —— 哈希函数和冲突解决方法。

哈希函数

​ 实现哈希表的关键在于哈希函数的选择，哈希函数的选择在很大程度上能够决定哈希表的读写性能。在理想情况下，哈希函数应该能够将不同键映射到不同的索引上，这要求哈希函数的输出范围为大于输入范围，但是由于键的数量会远远大于映射的范围，所以在实际使用时，这个理想的效果是不可能实现的。

​ 比较实际的方式是让哈希函数的结果能够尽可能的均匀分布，然后通过工程上的手段解决哈希碰撞的问题。如果使用结果分布较为均匀的哈希函数，那么哈希的增删改查的时间复杂度为 O(1)�(1)；但是如果哈希函数的结果分布不均匀，那么所有操作的时间复杂度可能会达到 O(n)�(�)，由此看来，使用好的哈希函数是至关重要的。

冲突解决

​ 在通常情况下，哈希函数输入的范围一定会远远大于输出的范围，所以在使用哈希表时一定会遇到冲突，哪怕我们使用了完美的哈希函数，当输入的键足够多也会产生冲突。然而多数的哈希函数都是不够完美的，所以仍然存在发生哈希碰撞的可能，这时就需要一些方法来解决哈希碰撞的问题，常见方法的就是开放寻址法和拉链法。

开放寻址法

​ 开放寻址法2是一种在哈希表中解决哈希碰撞的方法，这种方法的核心思想是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中。如果我们使用开放寻址法来实现哈希表，那么哈希表底层的数据结构就是数组，不过因为数组的长度有限，向哈希表写入这个键值对会从如下的索引开始遍历：

index := hash("author") % array.len

​ 当我们向当前哈希表写入新的数据时，如果发生了冲突，就会将键值对写入到下一个索引不为空的位置：

​ 如上图，哈希表中的两个键值对 key1 和 key2 发生冲突时，key3 会被写入 key2 后面的空闲位置。当我们再去读取 key3 对应的值的时候，就会先获取键的哈希并取模，这个时候会先找到 key1，发现与 key3 不相等，就会继续往后找，直到内存为空或者找到目标元素为止。

​ 开放寻址法中对性能影响最大的是装载因子，它是数组中元素的数量与数组大小的比值。随着装载因子的增加，线性探测的平均用时就会逐渐增加，这会影响哈希表的读写性能。当装载率超过 70% 之后，哈希表的性能就会急剧下降，而一旦装载率达到 100%，整个哈希表就会完全失效，这时查找和插入任意元素的时间复杂度都是 O(n)�(�) 的，这时需要遍历数组中的全部元素，所以在实现哈希表时一定要关注装载因子的变化。

拉链法

​ 拉链法是哈希表最常见的实现方法，大多数的编程语言都用拉链法来实现哈希表，它的实现比开放地址法稍微复杂一些，但是平均查找的长度也比较短，各个用于存储节点的内存都是动态申请的，可以节省比较多的存储空间。

​ 实现拉链法一般会使用数组加上链表，不过有一些编程语言会在拉链法的哈希中引入红黑树以优化性能，拉链法会使用链表数组作为哈希底层的数据结构，我们可以将它看成扩展的二维数组：

​ 如上图，当我们需要将键值对（key6，value6）写入哈希表时，键值对中的键 key6 都会经过一个哈希函数，哈希函数会帮助我们选择一个桶，方式就是直接对哈希的结果取模：

index := hash("key6") % array.len

​ 选择了 2 号桶后，就可以遍历当前桶中的链表了，在遍历链表的过程中会遇到以下两种情况：

1. 找到键相同的键值对 — 更新键对应的值
2. 没有找到键相同的键值对 – 在链表末尾追加新的键值对

如果要在哈希表中获取某个键对应的值，会经历如下的过程：

​ 上图是寻找 key11 的例子，当哈希表发现命中 4 号桶后，它会依次遍历桶中的键值对，遍历完整个链表也没有找到期望的键，说明哈希表中不存在该键对应的值。

​ 一个性能比较好的哈希表中，每个桶中的元素应该有 0 ~ 3 个，很少会超过这个范围。计算哈希、定位桶、遍历桶这三个过程是哈希表读写操作的主要开销，拉链法中也有转载因子的概念： 装载因子 = 元素数量 ÷ 桶数量

​ 同样的，拉链法的装载因子越大，哈希表的读写性能越差。一般情况下，拉链法的哈希表装载因子都不会超过 1 ，当哈希表装载因子较大时，会触发哈希表的扩容，通过创建更多的桶来重新划分键值对的分布，保证性能不会出现严重的下降。

2、数据结构

​ Go 运行时同时使用了多个数据结构组合表示哈希表，其中 runtime.hmap 是最核心的结构体

type hmap struct {
	count     int
	flags     uint8
	B         uint8
	noverflow uint16
	hash0     uint32

	buckets    unsafe.Pointer
	oldbuckets unsafe.Pointer
	nevacuate  uintptr

	extra *mapextra
}

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}

1. count 表示当前哈希表中的元素数量
2. B 表示当前哈希表持有的 buckets 数量，该字段存储的是桶的对数，即 len(buckets) = 2 ^ B
3. hash0 是哈希种子，在创建哈希函数时作为参数传入，它能为哈希函数的结果引入随机性
4. oldverflow 是哈希表在扩容时用来保存之前的 buckets 的字段，它的大小是当前 buckets 的一半

​ 如图所示，哈希表 runtime.hamp 的桶是runtime.bmap。每一个 runtime.bmp 都能存储 8 个键值对，当哈希表中存储的数据过多，单个桶已经装满时，会使用 extra.nextOverflow 中的桶存储溢出的数据。

​ 上述的两种桶被称为 正常桶 和溢出桶。黄色的 runtime.bmap 是正常桶，绿色的 runtime.bmap 是溢出桶。

​ 桶的结构体 runtime.bmap 在 Go 语言源码中的定义只包含一个简单的 tophash 字段，tophash 存储了键的哈希值高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能：

type bmap struct {
	tophash [bucketCnt]uint8s
}

​ 在运行期间，runtime.bmap 还包含其他字段，

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

​ 随着哈希表存储的数据逐渐增多，我们会扩容哈希表或者使用额外的桶存储溢出的数据，不会让单个桶中的数据超过 8 个，不过溢出桶只是临时的解决方案，创建过多的溢出桶最终也会导致哈希的扩容。

3、初始化

​ Go 语言初始化哈希表的两种方法 ——字面量和运行时。

字面量

​ Go 语言中一般使用 ke : value 的语法来表示键值对：

hash := map[string]int {
	"1": 2,
	"3": 4,
	"5": 6,
}

​ 在初始化哈希时，需要声明键值对的类型，这种使用字面量初始化的方式会通过 cmd/compile/internal/gc.maplit 初始化

func maplit(n *Node, m *Node, init *Nodes) {
	a := nod(OMAKE, nil, nil)
	a.Esc = n.Esc
	a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len())))
	litas(m, a, init)

	entries := n.List.Slice()
	if len(entries) > 25 {
		...
		return
	}
	...
}

​ 当哈希表中的元素数量少于或者等于 25 个时，编译器会将字面量初始化的结构体转换成以下的代码，将所有的键值对一次加入到哈希表中：

hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

​ 旦哈希表中元素的数量超过了 25 个，编译器会创建两个数组分别存储键和值，这些键值对会通过如下所示的 for 循环加入哈希：

hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
    hash[vstatk[i]] = vstatv[i]
}

​ 这里展开的两个切片 vstatk 和 vstatv 还会被编辑器继续展开。无论使用哪种方法，使用字面量初始化的过程都会使用 Go 语言中的关键字 make 来创建新的哈希并通过最原始的 [] 语法向哈希追加元素。

运行时

​ 当创建的哈希被分配到栈上并且其容量小于 BUCKETSIZE = 8 时，Go 语言在编译阶段会使用如下方式快速初始化哈希，这也是编译器对小容量的哈希做的优化：

var h *hmap
var hv hmap
var bv bmap
h := &hv
b := &bv
h.buckets = b
h.hash0 = fashtrand0()

除了上述特定的优化之外，无论 make 是从哪里来的，只要我们使用 make 创建哈希，Go 语言编译器都会在类型检查期间将它们转换成 runtime.makemap，使用字面量初始化哈希也只是语言提供的辅助工具，最后调用的都是 runtime.makemap：

func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}
	return h
}

这个函数会按照下面的步骤执行：

1. 计算哈希占用的内存是否溢出或者超出能分配的最大值；
2. 调用 runtime.fastrand 获取一个随机的哈希种子；
3. 根据传入的 hint 计算出需要的最小需要的桶的数量；
4. 使用 runtime.makeBucketArray 创建用于保存桶的数组；

runtime.makeBucketArray 会根据传入的 B 计算出的需要创建的桶数量并在内存中分配一片连续的空间用于存储数据：

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base
	if b >= 4 {
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	buckets = newarray(t.bucket, int(nbuckets))
	if base != nbuckets {
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

• 当桶的数量小于 2424 时，由于数据较少、使用溢出桶的可能性较低，会省略创建的过程以减少额外开销；
• 当桶的数量多于 2424 时，会额外创建 2B−42�−4 个溢出桶；

根据上述代码，我们能确定在正常情况下，正常桶和溢出桶在内存中的存储空间是连续的，只是被 runtime.hmap 中的不同字段引用，当溢出桶数量较多时会通过 runtime.newobject 创建新的溢出桶。

4、读写操作

​ 哈希表的访问一般都是通过下标或者遍历进行的：

_ = hash[key]

for k, v := range hash {
    // k, v
}

​ 这两种方式虽然都能读取哈希表的数据，但是使用的函数和底层原理完全不同。前者需要知道哈希的键并且一次只能获取单个键对应的值，而后者可以遍历哈希中的全部键值对，访问数据时也不需要预先知道哈希的键。在这里我们会介绍前一种访问方式。

​ 数据结构的写一般指的都是增加、删除和修改，增加和修改字段都使用索引和赋值语句，而删除字典中的数据需要使用关键字 delete：

hash[key] = value
hash[key] = newValue
delete(hash, key)

访问

​ 在编译的类型检查期间，hash[key] 以及类似的操作都会被转换成哈希的 OINDEXMAP 操作，中间代码生成阶段会在 cmd/compile/internal/gc.walkexpr 函数中将这些 OINDEXMAP 操作转换成如下的代码：

v     := hash[key] // => v     := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)

​ 赋值语句左侧接受参数的个数会决定使用的运行时方法：

• 当接受一个参数时，会使用 runtime.mapaccess1，该函数仅会返回一个指向目标值的指针；
• 当接受两个参数时，会使用 runtime.mapaccess2，除了返回目标值之外，它还会返回一个用于表示当前键对应的值是否存在的 bool 值：

​ runtime.mapaccess1 会先通过哈希表设置的哈希函数、种子获取当前键对应的哈希，再通过 runtime.bucketMask 和 runtime.add 拿到该键值对所在的桶序号和哈希高位的 8 位数字。

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if alg.equal(key, k) {
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				return v
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

​ 在 bucketloop 循环中，哈希会依次遍历正常桶和溢出桶中的数据，它会先比较哈希的高 8 位和桶中存储的 tophash，后比较传入的和桶中的值以加速数据的读写。用于选择桶序号的是哈希的最低几位，而用于加速访问的是哈希的高 8 位，这种设计能够减少同一个桶中有大量相等 tophash 的概率影响性能。

​ 如上图所示，每一个桶都是一整片的内存空间，当发现桶中的 tophash 与传入键的 tophash 匹配之后，我们会通过指针和偏移量获取哈希中存储的键 keys[0] 并与 key 比较，如果两者相同就会获取目标值的指针 values[0] 并返回。

​ 另一个同样用于访问哈希表中数据的 runtime.mapaccess2 只是在 runtime.mapaccess1 的基础上多返回了一个标识键值对是否存在的 bool 值：

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
	...
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if alg.equal(key, k) {
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				return v, true
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0]), false
}

​ 使用 v, ok := hash[k] 的形式访问哈希表中元素时，我们能够通过这个布尔值更准确地知道当 v == nil 时，v 到底是哈希中存储的元素还是表示该键对应的元素不存在，所以在访问哈希时，更推荐使用这种方式判断元素是否存在。

写入

​ 当形如 hash[k] 的表达式出现在赋值符号左侧时，该表达式也会在编译期间转换成 runtime.mapassign 函数的调用，该函数与 runtime.mapaccess1 比较相似，我们将其分成几个部分依次分析，首先是函数会根据传入的键拿到对应的哈希和桶：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0))

	h.flags ^= hashWriting

again:
	bucket := hash & bucketMask(h.B)
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
	top := tophash(hash)

​ 然后通过遍历比较桶中存储的 tophash 和键的哈希，如果找到了相同结果就会返回目标位置的地址。其中 inserti 表示目标元素的在桶中的索引，insertk 和 val 分别表示键值对的地址，获得目标地址之后会通过算术计算寻址获得键值对 k 和 val：

	var inserti *uint8
	var insertk unsafe.Pointer
	var val unsafe.Pointer
bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && inserti == nil {
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				}
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if !alg.equal(key, k) {
				continue
			}
			val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
			goto done
		}
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}

​ 上述的 for 循环会依次遍历正常桶和溢出桶中存储的数据，整个过程会分别判断 tophash 是否相等、key 是否相等，遍历结束后会从循环中跳出。

如果当前桶已经满了，哈希会调用 runtime.hmap.newoverflow 创建新桶或者使用 runtime.hmap 预先在 noverflow 中创建好的桶来保存数据，新创建的桶不仅会被追加到已有桶的末尾，还会增加哈希表的 noverflow 计数器。

	if inserti == nil {
		newb := h.newoverflow(t, b)
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		val = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	typedmemmove(t.key, insertk, key)
	*inserti = top
	h.count++

done:
	return val
}

如果当前键值对在哈希中不存在，哈希会为新键值对规划存储的内存地址，通过 runtime.typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址 val。如果当前键值对在哈希中存在，那么就会直接返回目标区域的内存地址，哈希并不会在 runtime.mapassign 这个运行时函数中将值拷贝到桶中，该函数只会返回内存地址，

扩容

​ 在写入的过程中，其实还会涉及到一个过程：扩容操作。随着哈希表中元素的逐渐增加，哈希的性能会逐渐恶化，所以我们需要更多的桶和更大的内存保证哈希的读写性能：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	...
	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again
	}
	...
}

​ 该函数会在以下两种情况触发哈希的扩容：

1. 装载因子已经超过 6.5
2. 哈希使用了太多溢出桶

​ 根据触发的条件不同，扩容的方式也不同：如果扩容的原因是溢出桶太多，那么这次扩容就是等量扩容 sameSizeGrow，这是一种特殊的扩容，当我们持续向哈希表中插入数据并将它们全部删除时，如果哈希表中的数据量没有超过阈值，就会不断累积溢出桶造成缓慢的内存泄漏。sameSizeGrow 通过复用已有的哈希扩容机制解决该问题，一旦出现了过多的溢出桶，它会创建新的桶保存数据，垃圾回收会清理旧的溢出桶并释放内存。

func hashGrow(t *maptype, h *hmap) {
	bigger := uint8(1)
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0
		h.flags |= sameSizeGrow
	}
	oldbuckets := h.buckets
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

	h.extra.oldoverflow = h.extra.overflow
	h.extra.overflow = nil
	h.extra.nextOverflow = nextOverflow
}

哈希在扩容的过程中会通过 runtime.makeBucketArray 创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新，下图展示了触发扩容后的哈希：

我们在 runtime.hashGrow 中还看不出来等量扩容和翻倍扩容的太多区别，等量扩容创建的新桶数量只是和旧桶一样，该函数中只是创建了新的桶，并没有对数据进行拷贝和转移。哈希表的数据迁移的过程在是 runtime.evacuate 中完成的，它会对传入桶中的元素进行再分配。

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	newbit := h.noldbuckets()
	if !evacuated(b) {
		var xy [2]evacDst
		x := &xy[0]
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.v = add(x.k, bucketCnt*uintptr(t.keysize))

		y := &xy[1]
		y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
		y.k = add(unsafe.Pointer(y.b), dataOffset)
		y.v = add(y.k, bucketCnt*uintptr(t.keysize))

​ 而当哈希表的容量翻倍时，每个旧桶的元素会都分流到新创建的两个桶中，这里仔细分析一下分流元素的逻辑：

		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			v := add(k, bucketCnt*uintptr(t.keysize))
			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
				top := b.tophash[i]
				k2 := k
				var useY uint8
				hash := t.key.alg.hash(k2, uintptr(h.hash0))
				if hash&newbit != 0 {
					useY = 1
				}
				b.tophash[i] = evacuatedX + useY
				dst := &xy[useY]

				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
				dst.b.tophash[dst.i&(bucketCnt-1)] = top
				typedmemmove(t.key, dst.k, k)
				typedmemmove(t.elem, dst.v, v)
				dst.i++
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.v = add(dst.v, uintptr(t.valuesize))
			}
		}
		...
}

​ 只使用哈希函数是不能定位到具体某一个桶的，哈希函数只会返回很长的哈希，例如：b72bfae3f3285244c4732ce457cca823bc189e0b，我们还需一些方法将哈希映射到具体的桶上。我们一般都会使用取模或者位操作来获取桶的编号，假如当前哈希中包含 4 个桶，那么它的桶掩码就是 0b11(3)，使用位操作就会得到 3， 我们就会在 3 号桶中存储该数据.

​ runtime.evacuate 最后会调用 runtime.advanceEvacuationMark 增加哈希的 nevacuate 计数器并在所有的旧桶都被分流后清空哈希的 oldbuckets 和 oldoverflow.

​ 除了写入操作之外，删除操作也会在哈希表扩容期间触发 runtime.growWork，触发的方式和代码与这里的逻辑几乎完全相同，都是计算当前值所在的桶，然后拷贝桶中的元素。

​ 简单总结一下哈希表扩容的设计和原理，哈希在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，扩容过程不是原子的，而是通过 runtime.growWork 增量触发的，在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流。除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会整理哈希的内存减少空间的占用。

删除

​ 想要删除哈希中的元素，就需要使用delete 关键字，这个关键字的唯一作用就是将某一个键对应的元素从哈希表中删除，无论是该键对应的值是否存在，这个内建的函数都不会返回任何的结果。

​ 哈希表的删除逻辑与写入逻辑很相似，只是触发哈希的删除需要使用关键字，如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素，分流结束之后会找到桶中的目标元素完成键值对的删除工作。

5、小结

​ Go 语言使用拉链法解决哈希碰撞问题，实现哈希表，对哈希表的访问、写入和删除等操作都在编译期间转换成运行时的函数或方法。每个哈希桶存储键对应哈希的前 8 位，这些前 8 位哈希值成为能够快速遍历桶中元素的缓存。

​ 每个哈希桶最多存储 8 个键值对。一旦某个桶内的键值对数量超过 8 个，新的键值对将存储在哈希的溢出桶中。随着键值对数量的增加，溢出桶的数量和哈希表的装载因子也逐渐升高。当装载因子超过一定范围时，会触发哈希表的扩容操作。扩容将哈希表的桶数量翻倍，这个元素重新分配的过程是在调用写操作时逐步完成的，不会导致性能的急剧波动。这种机制有助于维护哈希表的高效性和均衡性。

四、字符串

​ 字符串是由字符组成的数组，C 语言中的字符串使用字符数组 char[] 表示。数组会占用一片连续的内存空间，而内存空间存储的字节共同组成了字符串，Go 语言中的字符串只是一个只读的字节数组，如下图所示：

​ 只读只意味着字符串会分配到只读的内存空间，但是 Go 语言只是不支持直接修改 string 类型变量的内存空间，我们仍然可以通过在 string 和 []byte 类型之间反复转换实现修改这一目的：

1. 先将这段内存拷贝到堆或者栈上；
2. 将变量的类型转换成 []byte 后并修改字节数据；
3. 将修改后的字节数组转换回 string；

1、数据结构

​ 字符串在 Go 语言中的实现很简单，每一个字符串在运行时都会使用 reflect.StringHeader 表示，其中包含指向字符数组的指针和数组的大小：

type StringHeader struct {
	Data uintptr
	Len int
}

​ 会发现与切片的结构体非常相似，至少了一个表示容量的 Cap 字段，因此字符串经常被说是一个只读的切片类型：

type SliceHeader struct {
	Data uintptr
	Len int
}

2、解析过程

​ 解析器会在词法分析阶段解析字符串，将原有无意义的字符流转换成 Token 序列。在 Go 语言中有两种声明字符串的方式，即双引号和反引号：

str1 := "this is a string"
str2 := `this is s another
string `

​ 对于双引号声明字符串没有啥好说的，它只能用于单行字符串的初始化，其内部如果需要使用双引号，要用 \ 转义；而反引号可以摆脱单行的限制。当使用反引号时，双引号不再表示字符串的开始和结尾，因此在字符串内部可以直接使用 "。反引号在需要手写 JSON 或者其他复杂数据格式的场景下非常方便：：

json := `{"author": "draven", "tags": ["golang"]}`

​ 两种不同的声明方式，也就意味着编辑器需要不同的解析方式。对于双引号格式的字符串，编译器使用扫描器 cmd/compile/internal/syntax.scanner 会将输入的字符串转换成 Token 流，cmd/compile/internal/syntax.scanner.stdString 方法是它用来解析使用双引号的标准字符串：

func (s *scanner) stdString() {
	s.startLit()  // 初始化字符串字面量扫描

	for {
		r := s.getr()  // 从输入中获取一个字符
		if r == '"' {
			break  // 如果字符是双引号，表示字符串结束，退出循环
		}
		if r == '\\' {
			s.escape('"')  // 处理转义字符
			continue
		}
		if r == '\n' {
			s.ungetr()  // 回退字符
			s.error("newline in string")  // 产生错误消息，因为字符串中不应包含换行符
			break
		}
		if r < 0 {
			s.errh(s.line, s.col, "string not terminated")  // 产生错误消息，字符串没有正常终止
			break
		}
	}

	s.nlsemi = true  // 标记字符串中允许包含换行符
	s.lit = string(s.stopLit())  // 存储已扫描的字符串字面量的内容
	s.kind = StringLit  // 标记标记的种类为字符串字面量
	s.tok = _Literal  // 标记标记的类型为字面量
}

​ 从这个方法的实现我们能分析出 Go 语言处理标准字符串的逻辑：

1. 标准字符串使用双引号表示开头和结尾；
2. 标准字符串需要使用反斜杠 \ 来逃逸双引号；
3. 标准字符串不能出现如下所示的隐式换行 \n；

​ 使用反引号声明的解析就很简单了，cmd/compile/internal/syntax.scanner.rawString 会将非反引号的所有字符都划分到当前字符串的范围中，所以我们可以使用它支持复杂的多行字符串：

func (s *scanner) rawString() {
	s.startLit()  // 初始化原始字符串字面量扫描

	for {
		r := s.getr()  // 从输入中获取一个字符
		if r == '`' {
			break  // 如果字符是反引号，表示原始字符串结束，退出循环
		}
		if r < 0 {
			s.errh(s.line, s.col, "string not terminated")  // 产生错误消息，原始字符串没有正常终止
			break
		}
	}

	s.nlsemi = true  // 标记原始字符串中允许包含换行符
	s.lit = string(s.stopLit())  // 存储已扫描的原始字符串字面量的内容
	s.kind = StringLit  // 标记标记的种类为原始字符串字面量
	s.tok = _Literal  // 标记标记的类型为字面量
}

​ 无论是标准字符串还是原始字符串都会被标记成 StringLit 并传递到语法分析阶段。在语法分析阶段，与字符串相关的表达式都会由 cmd/compile/internal/gc.noder.basicLit 方法处理：

func (p *noder) basicLit(lit *syntax.BasicLit) Val {
	switch s := lit.Value; lit.Kind {
	case syntax.StringLit:
		if len(s) > 0 && s[0] == '`' {
			s = strings.Replace(s, "\r", "", -1)  // 如果是原始字符串字面量，去除其中的回车符
		}
		u, _ := strconv.Unquote(s)  // 解析字符串字面量并移除转义字符
		return Val{U: u}  // 返回解析后的字符串字面量作为 Val 结构
	}
}

无论是 import 语句中包的路径、结构体中的字段标签还是表达式中的字符串都会使用这个方法将原生字符串中最后的换行符删除并对字符串 Token 进行 Unquote，也就是去掉字符串两边的引号等无关干扰，还原其本来的面目。

strconv.Unquote 处理了很多边界条件导致实现非常复杂，其中不仅包括引号，还包括 UTF-8 等编码的处理逻辑，这里也就不展开介绍了。

3、拼接

​ 项目中我们拼接字符串会使用 +，编译器会将该符号对应的 OADD 节点转换成 OADDSTR 类型的节点，随后在 cmd/compile/internal/gc.walkexpr 中调用 cmd/compile/internal/gc.addstr 函数生成用于拼接字符串的代码：

func walkexpr(n *Node, init *Nodes) *Node {
	switch n.Op {
		// 其他操作的处理...
	case OADDSTR:
		n = addstr(n, init)  // 如果操作为字符串拼接，调用 addstr 函数处理
	}
}

​ cmd/compile/internal/gc.addstr 能帮助我们在编译期间选择合适的函数对字符串进行拼接，该函数会根据带拼接的字符串数量选择不同的逻辑：

• 如果小于或者等于 5 个，那么会调用 concatstring{2,3,4,5} 等一系列函数；

• 如果超过 5 个，那么会选择 runtime.concatstrings 传入一个数组切片；

  func addstr(n *Node, init *Nodes) *Node {
  	c := n.List.Len()  // 获取字符串拼接表达式中操作数的数量
  
  	buf := nodnil()  // 创建一个 nil 的节点，用于存储字符串拼接结果
  	args := []*Node{buf}  // 创建一个节点切片，初始包含 buf 节点
  	for _, n2 := range n.List.Slice() {
  		args = append(args, conv(n2, types.Types[TSTRING]))  // 将表达式节点 n2 转换为字符串类型，然后添加到 args 中
  	}
  
  	var fn string
  	if c <= 5 {
  		fn = fmt.Sprintf("concatstring%d", c)  // 根据操作数数量选择合适的字符串拼接函数名
  	} else {
  		fn = "concatstrings"
  
  		t := types.NewSlice(types.Types[TSTRING])
  		slice := nod(OCOMPLIT, nil, typenod(t))  // 创建一个字符串切片的复合字面量
  		slice.List.Set(args[1:])  // 设置切片的元素列表为 args 中的参数
  		args = []*Node{buf, slice}
  	}
  
  	cat := syslook(fn)  // 查找字符串拼接函数
  	r := nod(OCALL, cat, nil)  // 创建一个函数调用节点
  	r.List.Set(args)
  	// 其他处理逻辑...
  	return r  // 返回处理后的字符串拼接表达式节点
  }

  ​ 其实无论使用 concatstring{2,3,4,5} 中的哪一个，最终都会调用 runtime.concatstrings，它会先对遍历传入的切片参数，再过滤空字符串并计算拼接后字符串的长度。

func concatstrings(buf *tmpBuf, a []string) string {
	idx := 0
	l := 0
	count := 0
	for i, x := range a {
		n := len(x)
		if n == 0 {
			continue
		}
		l += n
		count++
		idx = i
	}
	if count == 0 {
		return ""  // 如果没有非空字符串可拼接，返回空字符串
	}
	if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
		return a[idx]  // 如果只有一个非空字符串且无需缓冲区拼接，直接返回该字符串
	}
	s, b := rawstringtmp(buf, l)  // 分配用于拼接的字符串内存
	for _, x := range a {
		copy(b, x)  // 将每个字符串拷贝到拼接结果中
		b = b[len(x):]  // 更新拼接位置
	}
	return s  // 返回拼接后的字符串
}

​ 如果非空字符串的数量为 1 并且当前的字符串不在栈上，就可以直接返回该字符串，不需要做出额外操作。

​ 但是在正常情况下，运行时会调用 copy 将输入的多个字符串拷贝到目标字符串所在的内存空间。新的字符串是一片新的内存空间，与原来的字符串也没有任何关联，一旦需要拼接的字符串非常大，拷贝带来的性能损失是无法忽略的。

4、类型转换

​ 当我们使用 Go 语言解析和序列化 JSON 等数据格式时，经常需要将数据在 string 和 []byte 之间来回转换，类型转换的开销其实是蛮大的，经常成为程序性能热点。

​ 从字节数组到字符串的转换需要使用 runtime.slicebytetostring 函数，例如：string(bytes)，该函数在函数体中会先处理两种比较常见的情况，也就是长度为 0 或者 1 的字节数组，这两种情况处理起来都非常简单：

func slicebytetostring(buf *tmpBuf, b []byte) (str string) {
	l := len(b)
	if l == 0 {
		return ""  // 如果输入字节数组为空，返回空字符串
	}
	if l == 1 {
		stringStructOf(&str).str = unsafe.Pointer(&staticbytes[b[0]])
		stringStructOf(&str).len = 1
		return  // 如果字节数组长度为1，直接使用静态字节数组构建字符串
	}
	var p unsafe.Pointer
	if buf != nil && len(b) <= len(buf) {
		p = unsafe.Pointer(buf)
	} else {
		p = mallocgc(uintptr(len(b)), nil, false)  // 分配足够的内存用于存储字节数组数据
	}
	stringStructOf(&str).str = p
	stringStructOf(&str).len = len(b)
	memmove(p, (*(*slice)(unsafe.Pointer(&b))).array, uintptr(len(b))  // 将字节数组内容拷贝到新分配的内存中
	return  // 返回构建的字符串
}

​ 处理过后会根据传入的缓冲区大小决定是否需要为新字符串分配一片内存空间，runtime.stringStructOf 会将传入的字符串指针转换成 runtime.stringStruct 结构体指针，然后设置结构体持有的字符串指针 str 和长度 len，最后通过 runtime.memmove 将原 []byte 中的字节全部复制到新的内存空间中。

​ 当我们想要将字符串转换成 []byte 类型时，需要使用 runtime.stringtoslicebyte 函数，该函数的实现非常容易理解：

func stringtoslicebyte(buf *tmpBuf, s string) []byte {
	var b []byte
	if buf != nil && len(s) <= len(buf) {
		*buf = tmpBuf{}
		b = buf[:len(s)]  // 如果提供了足够的缓冲区并且缓冲区足够大，使用缓冲区
	} else {
		b = rawbyteslice(len(s))  // 否则分配一个新的字节数组切片
	}
	copy(b, s)  // 将字符串内容拷贝到字节数组切片中
	return b  // 返回字节数组切片
}

上述函数会根据是否传入缓冲区做出不同的处理：

• 当传入缓冲区时，它会使用传入的缓冲区存储 []byte；
• 当没有传入缓冲区时，运行时会调用 runtime.rawbyteslice 创建新的字节切片并将字符串中的内容拷贝过去；

​ 字符串和 []byte 中的内容虽然一样，但是字符串的内容是只读的，我们不能通过下标或者其他形式改变其中的数据，而 []byte 中的内容是可以读写的。不过无论从哪种类型转换到另一种都需要拷贝数据，而内存拷贝的性能损耗会随着字符串和 []byte 长度的增长而增长。

5、小结

​ 字符串是 Go 语言中相对来说比较简单的一种数据结构，我们在这一节中详细分析了字符串与 []byte 类型的关系，从词法分析阶段理解字符串是如何被解析的，作为只读的数据类型，我们无法改变其本身的结构，但是在做拼接和类型转换等操作时一定要注意性能的损耗，遇到需要极致性能的场景一定要尽量减少类型转换的次数。