Golang 数组、Slice 和 Map

一、数组（Array）

数组是具有固定长度且元素类型相同的序列。

1. 声明

声明格式为 var 变量名 [长度]元素类型，示例如下：

var a [3]int    // 声明长度为 3 的 int 类型数组
var b [2]string // 声明长度为 2 的 string 类型数组

2. 初始化

默认初始化：元素值为对应类型的零值（如 int 为 0，string 为空字符串，bool 为 false）。
初始化列表：直接指定元素值，示例 var a = [3]int{1, 2, 3}。
长度自动推导：用 ... 代替长度，编译器根据元素数量推导，示例 var a = [...]int{1, 2, 3}。
指定索引初始化：可指定部分索引的元素值，未指定的为零值，示例 var a = [...]int{0: 1, 2: 3}（结果为 [1 0 3]）。

3. 访问与遍历

下标访问：通过 数组名[索引] 访问或修改元素，示例 a[0] = 10。

遍历方式：

for 循环：通过索引遍历，示例：

for i := 0; i < len(a); i++ {
    fmt.Printf("%d: %d, ", i, a[i])
}

for range：同时获取索引和值，示例：

for i, v := range a {
    fmt.Printf("%d: %d, ", i, v)
}

4. 示例代码

package main

import "fmt"

func main() {
    // 初始化示例
    var a [3]int
    var b = [2]string{"tom", "jim"}
    var c = [...]int{0: 1, 2: 3}
    fmt.Printf("a: %v\n", a)  // a: [0 0 0]
    fmt.Printf("b: %v\n", b)  // b: [tom jim]
    fmt.Printf("c: %v\n", c)  // c: [1 0 3]

    // 访问与遍历
    a[0] = 10
    a[1] = 20
    fmt.Printf("a[0]: %d, a[1]: %d\n", a[0], a[1])  // a[0]: 10, a[1]: 20

    for i, v := range c {
        fmt.Printf("c[%d]: %d ", i, v)  // c[0]: 1 c[1]: 0 c[2]: 3
    }
}

二、切片（Slice）

切片是可变长度的序列，本质是对底层数组的引用，可自动扩容。

1. 声明

声明格式为 var 变量名 []元素类型，未初始化的切片为 nil，示例：

var s []int  // nil 切片，len=0，cap=0

2. 初始化

字面量初始化：直接指定元素，示例 s1 := []int{1, 2, 3}；也可初始化空切片 s2 := []int{}。

make 初始化：格式为 make([]类型, 长度, 容量)，示例：

s3 := make([]int, 2, 10)  // 长度 2，容量 10，元素为零值 [0 0]

3. nil 切片、空切片和零切片的区别

类型	定义方式	长度	容量	底层地址特点
nil 切片	`var s []int`	0	0	指向空地址（0x0）
空切片	`make([]int, 0)` 或 `[]int{}`	0	0	指向固定非空地址
零切片	`make([]int, 2, 5)`	2	5	元素为零值，指向实际内存地址

示例代码：

package main

import "fmt"

func main() {
    var s1 []int          // nil 切片
    s2 := make([]int, 0)  // 空切片
    s3 := []int{}         // 空切片
    s4 := make([]int, 2, 5) // 零切片

    fmt.Printf("s1: %p, len: %d, cap: %d\n", s1, len(s1), cap(s1))  // s1: 0x0, len: 0, cap: 0
    fmt.Printf("s2: %p, len: %d, cap: %d\n", s2, len(s2), cap(s2))  // s2: 0xxxx, len: 0, cap: 0
    fmt.Printf("s3: %p, len: %d, cap: %d\n", s3, len(s3), cap(s3))  // s3: 0xxxx, len: 0, cap: 0
    fmt.Printf("s4: %p, len: %d, cap: %d\n", s4, len(s4), cap(s4))  // s4: 0xxxx, len: 2, cap: 5
}

4. 操作

（1）长度与容量

长度：len(s)，表示当前元素个数。
容量：cap(s)，表示底层数组可容纳的最大元素个数。

（2）切取

简单表达式：a[low:high]，新切片长度为 high-low，容量为 原容量-low（前闭后开区间），数组越界会触发 panic。
扩展表达式：a[low:high:max]，限制新切片容量为 max-low，避免修改影响原切片。

示例：

a := []int{1, 2, 3, 4, 5}
s1 := a[1:3]    // 长度 2，容量 4（5-1），值 [2,3]
s2 := a[1:3:4]  // 长度 2，容量 3（4-1），值 [2,3]

（3）追加（append）

格式：s = append(s, 元素) 或 s = append(s, 其他切片...)。
扩容规则：容量 < 1024 时，按 2 倍扩容；容量 ≥ 1024 时，按 1.25 倍扩容。

示例：

s := []int{1, 2}
s = append(s, 3)       // s: [1,2,3]
s2 := []int{4, 5}
s = append(s, s2...)   // s: [1,2,3,4,5]

（4）删除元素

通过切取和追加实现，示例：

s := []int{1, 2, 3, 4}
index := 2  // 删除索引 2 的元素（值 3）
s = append(s[:index], s[index+1:]...)  // s: [1,2,4]

（5）拷贝（copy）

格式：copy(目标切片, 源切片)，将源切片元素拷贝到目标切片，返回实际拷贝的元素数。

示例：

s1 := []int{1, 2, 3}
s2 := make([]int, 3)
copy(s2, s1)  // s2: [1,2,3]

（6）遍历

与数组相同，支持 for 循环和 for range。

5. 底层原理

数据结构：切片本质是结构体，包含底层数组指针、长度和容量：

// src/runtime/slice.go
type slice struct {
    array unsafe.Pointer  // 底层数组指针
    len   int             // 长度
    cap   int             // 容量
}

共享底层数组：切取或未扩容的追加操作会共享底层数组，修改新切片可能影响原切片。
函数传参：切片是值传递（拷贝结构体），若需修改原切片（如扩容后同步长度），需传递指针。

6. 示例代码

package main

import (
  "fmt"
  "unsafe"
)

func printArray(array []int) {
  for i := 0; i < len(array); i++ {
  	fmt.Printf("[%d, %p] ", array[i], &array[i])
  }
  fmt.Println("")
}

// slice 切片共享底层数组
func test01() {
  array := []int{1, 2, 3, 4, 5, 6}
  printArray(array)

  s1 := array[0:2]
  s2 := array[2:]
  s3 := array[:]
  s4 := array[0:2:2] // 扩展表达式 array[low:high:max]
  s5 := s2[2:]
  fmt.Printf("&s1: %p, len: %d, capacity: %d, print: %v\n", &s1, len(s1), cap(s1), s1)
  printArray(s1)
  fmt.Printf("&s2: %p, len: %d, capacity: %d, print: %v\n", &s2, len(s2), cap(s2), s2)
  printArray(s2)
  fmt.Printf("&s3: %p, len: %d, capacity: %d, print: %v\n", &s3, len(s3), cap(s3), s3)
  printArray(s3)
  fmt.Printf("&s4: %p, len: %d, capacity: %d, print: %v\n", &s4, len(s4), cap(s4), s4)
  printArray(s4)
  fmt.Printf("&s5: %p, len: %d, capacity: %d, print: %v\n", &s5, len(s5), cap(s5), s5)
  printArray(s5)
  /*
  	[1, 0xc00000e300] [2, 0xc00000e308] [3, 0xc00000e310] [4, 0xc00000e318] [5, 0xc00000e320] [6, 0xc00000e328]
  	&s1: 0xc000008030, len: 2, capacity: 6, print: [1 2]
  	[1, 0xc00000e300] [2, 0xc00000e308]
  	&s2: 0xc000008048, len: 4, capacity: 4, print: [3 4 5 6]
  	[3, 0xc00000e310] [4, 0xc00000e318] [5, 0xc00000e320] [6, 0xc00000e328]
  	&s3: 0xc000008060, len: 6, capacity: 6, print: [1 2 3 4 5 6]
  	[1, 0xc00000e300] [2, 0xc00000e308] [3, 0xc00000e310] [4, 0xc00000e318] [5, 0xc00000e320] [6, 0xc00000e328]
  	&s4: 0xc000008078, len: 2, capacity: 2, print: [1 2]
  	[1, 0xc00000e300] [2, 0xc00000e308]
  	&s5: 0xc000008090, len: 2, capacity: 2, print: [5 6]
  	[5, 0xc00000e320] [6, 0xc00000e328]
  */

  // 由于切片共享底层数组, 对新切片的操作也会影响原切片, 原切片 [1 2 3 4 5 6] 变为 [1 2 7 4 5 6]
  fmt.Printf("s1, len: %d, capacity: %d, print: %v\n", len(s1), cap(s1), s1)
  fmt.Printf("array, len: %d, capacity: %d, print: %v\n", len(array), cap(array), array)
  s1 = append(s1, 7)
  fmt.Printf("s1, len: %d, capacity: %d, print: %v\n", len(s1), cap(s1), s1)
  fmt.Printf("array, len: %d, capacity: %d, print: %v\n", len(array), cap(array), array)
  // 解决方法: 使用扩展表达式限制新切片的容量 array[low:high:max]
  fmt.Printf("s4, len: %d, capacity: %d, print: %v\n", len(s4), cap(s4), s4)
  s4 = append(s4, 8)
  fmt.Printf("s4, len: %d, capacity: %d, print: %v\n", len(s4), cap(s4), s4)
  fmt.Printf("array, len: %d, capacity: %d, print: %v\n", len(array), cap(array), array)
  /*
  	s1, len: 2, capacity: 6, print: [1 2]
  	array, len: 6, capacity: 6, print: [1 2 3 4 5 6]
  	s1, len: 3, capacity: 6, print: [1 2 7]
  	array, len: 6, capacity: 6, print: [1 2 7 4 5 6]
  	s4, len: 2, capacity: 2, print: [1 2]
  	s4, len: 3, capacity: 4, print: [1 2 8]
  	array, len: 6, capacity: 6, print: [1 2 7 4 5 6]
  */
}

func change(tmp []int) {
  fmt.Printf("&tmp: %p\n", &tmp)
  tmp = append(tmp, 9)
  fmt.Printf("&tmp: %p, len: %d, capacity: %d, print: %v\n", &tmp, len(tmp), cap(tmp), tmp)
}

func changeByPoint(tmp *[]int) {
  fmt.Printf("&tmp: %p\n", tmp)
  *tmp = append(*tmp, 9)
  fmt.Printf("&tmp: %p, len: %d, capacity: %d, print: %v\n", tmp, len(*tmp), cap(*tmp), *tmp)
}

// slice 的参数传递的问题
func test02() {
  // len 和 cap 值传递, 形参的变化未影响到实参, 所以 array1 的长度和容量未改变
  array1 := make([]int, 0)
  fmt.Printf("&array1: %p, len: %d, capacity: %d, print: %v\n", &array1, len(array1), cap(array1), array1)
  change(array1)
  fmt.Printf("&array1: %p, len: %d, capacity: %d, print: %v\n", &array1, len(array1), cap(array1), array1)
  /*
  	&array1: 0xc00009a018, len: 0, capacity: 0, print: []
  	&tmp: 0xc00009a048
  	&tmp: 0xc00009a048, len: 1, capacity: 1, print: [9]
  	&array1: 0xc00009a018, len: 0, capacity: 0, print: []
  */

  // 函数内部 slice 扩容, 由 3 扩容到 6
  array2 := make([]int, 0, 3)
  array2 = append(array2, 1, 2, 3)
  fmt.Printf("&array2: %p, len: %d, capacity: %d, print: %v\n", &array2, len(array2), cap(array2), array2)
  change(array2)
  fmt.Printf("&array2: %p, len: %d, capacity: %d, print: %v\n", &array2, len(array2), cap(array2), array2)
  /*
  	&array2: 0xc00009a090, len: 3, capacity: 3, print: [1 2 3]
  	&tmp: 0xc00009a0c0
  	&tmp: 0xc00009a0c0, len: 4, capacity: 6, print: [1 2 3 9]
  	&array2: 0xc00009a090, len: 3, capacity: 3, print: [1 2 3]
  */

  // 那个底层数组的指针是值传递进去的, 函数内部修改了底层数组的指针, 所以这个值已经发生了改变, 只是由于 len 和 cap 未变, 没有显示出来
  // array3[2] 已经由 3 变成了 9
  array3 := make([]int, 0, 3)
  array3 = append(array3, 1, 2, 3)
  fmt.Printf("&array3: %p, len: %d, capacity: %d, print: %v\n", &array3, len(array3), cap(array3), array3)
  change(array3[:2])
  fmt.Printf("&array3: %p, len: %d, capacity: %d, print: %v\n", &array3, len(array3), cap(array3), array3)
  /*
  	&array3: 0xc00009a108, len: 3, capacity: 3, print: [1 2 3]
  	&tmp: 0xc00009a138
  	&tmp: 0xc00009a138, len: 3, capacity: 3, print: [1 2 9]
  	&array3: 0xc00009a108, len: 3, capacity: 3, print: [1 2 9]
  */

  // 更直观的观察方式: 把指针偏移到 array4[2] 后面一个元素, 看这个元素是否被改变了
  array4 := make([]int, 0, 5)
  array4 = append(array4, 1, 2, 3)
  fmt.Printf("&array4: %p, len: %d, capacity: %d, print: %v\n", &array4, len(array4), cap(array4), array4)
  change(array4)
  p := unsafe.Pointer(&array4[2])
  q := uintptr(p) + 8
  t := (*int)(unsafe.Pointer(q))
  fmt.Printf("array4[3]: %d\n", *t)
  fmt.Printf("&array4: %p, len: %d, capacity: %d, print: %v\n", &array4, len(array4), cap(array4), array4)
  /*
  	&array4: 0xc000008198, len: 3, capacity: 5, print: [1 2 3]
  	&tmp: 0xc0000081c8
  	&tmp: 0xc0000081c8, len: 4, capacity: 5, print: [1 2 3 9]
  	array4[3]: 9
  	&array4: 0xc000008198, len: 3, capacity: 5, print: [1 2 3]
  */

  // 函数参数传递指针时, 传递的是 slice 的地址, 所以函数内部形参的修改会同步到外部实参中
  array5 := make([]int, 0, 5)
  array5 = append(array5, 1, 2, 3)
  fmt.Printf("&array5: %p, len: %d, capacity: %d, print: %v\n", &array5, len(array5), cap(array5), array5)
  changeByPoint(&array5)
  fmt.Printf("&array5: %p, len: %d, capacity: %d, print: %v\n", &array5, len(array5), cap(array5), array5)
  /*
  	&array5: 0xc00009a1f8, len: 3, capacity: 5, print: [1 2 3]
  	&tmp: 0xc00009a1f8
  	&tmp: 0xc00009a1f8, len: 4, capacity: 5, print: [1 2 3 9]
  	&array5: 0xc00009a1f8, len: 4, capacity: 5, print: [1 2 3 9]
  */
}

func sliceRise(s []int) {
  s = append(s, 9)
  for i := range s {
  	s[i]++
  }
}

// 练习
func test03() {
  s1 := []int{1, 2}
  s2 := append(s1, 3)
  sliceRise(s1)
  sliceRise(s2)
  fmt.Println(s1, s2)
  /*
  	[1 2] [2 3 4]
  */
}

func main() {
  test01()
  //test02()
  //test03()
}

哈希表（Map）

Map 是键值对（key:value）数据结构，底层为哈希表，支持快速检索，是引用类型。

1. 声明

声明格式为 var 变量名 map[key类型]value类型，未初始化的 map 为 nil，对 nil map 操作会触发 panic。

var m map[string]int  // nil map

Note：key 类型必须可比较（如 int、string 等），slice、map、function 不能作为 key。

2. 初始化

make 初始化：make(map[key类型]value类型, 容量)，指定容量可减少内存分配，示例：
```
m1 := make(map[string]int, 10)  // 容量 10 的 map
```

字面量初始化：直接指定键值对，示例：

m2 := map[string]string{
    "name": "tom",
    "age":  "20",
}

3. 操作

（1）增、改、查

增/改：m[key] = value，若 key 存在则修改，不存在则新增。

查：value := m[key]，若 key 不存在，返回 value 类型的零值；可通过第二个返回值判断存在性：

if value, exist := m["name"]; exist {
    fmt.Println("存在，值为", value)
} else {
    fmt.Println("不存在")
}

（2）遍历

遍历 key：for key := range m { ... }
遍历 key 和 value：for key, value := range m { ... }

Note：遍历顺序不确定（因哈希表扩容可能重排）。

（3）删除

格式：delete(m, key)，若 key 不存在或 map 为 nil，无报错（空操作）。
删除一个键值对后，该键值对占用的内存不会立即释放，而是由 Go 的垃圾回收（GC）机制在后续适当的时候回收。

（4）清空

Go 1.21+ 可使用 clear(m)，高效清空所有键值对（保留底层内存）。
与传统的 for-range + delete 循环删除相比，clear() 在编译阶段直接转换为高效的内置操作，更加高效。
其他方式：m = make(...)（重新创建，旧 map 由 GC 回收）。

4. 底层原理

（1）数据结构

hmap：map 的核心结构，包含桶数组指针、桶数量指数（B）、元素数量等。元素经过 Hash 运算后，会落到某个 bucket 中进行存储。bucket 就是桶。。

bmap：桶结构，每个桶可存 8 个键值对，通过 tophash 存储哈希高位，overflow 指针链接溢出桶（解决哈希冲突）。

tophash 是一个长度为 8 的整形数组，Hash 值相同的键存入当前 bucket 时会将 Hash 值的高位存储在该数组中，以便后续匹配。
data 和 overflow 并没有显式地在结构体中声明，访问 bucket 时通过指针偏移来访问这些虚拟成员。
data 区域存放 key-value 数据，存放顺序是 key/key/key…value/value/value，如此存放是为了节省字节对齐带来的空间浪费
overflow 指针指向下一个 bucket，形成了一个链表

// src/runtime/map_noswiss.go
// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
	clearSeq   uint64

	extra *mapextra // optional fields
}

// mapextra holds fields that are not present on all maps.
// map 的额外元数据信息
type mapextra struct {
	// If both key and elem do not contain pointers and are inline, then we mark bucket
	// type as containing no pointers. This avoids scanning such maps.
	// However, bmap.overflow is a pointer. In order to keep overflow buckets
	// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
	// overflow and oldoverflow are only used if key and elem do not contain pointers.
	// overflow contains overflow buckets for hmap.buckets.
	// oldoverflow contains overflow buckets for hmap.oldbuckets.
	// The indirection allows to store a pointer to the slice in hiter.
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [abi.OldMapBucketCount]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
        data []byte
        overflow *bmap
}

示意图：

（2）哈希冲突

采用链地址法：当哈希值相同的键超过 8 个时，通过 overflow 指针链接新桶，形成链表。

（3）负载因子与扩容

负载因子 = 元素数量 / 桶数量，阈值为 6.5，超过则触发扩容。
- 负载因子的影响
  - 负载因子过小，说明空间利用率低
  - 负载因子过大，说明冲突严重，存取效率低
- rehash：当 Hash 表的负载因子过大时，需要申请更多的 bucket，并对所有的键值对重新组织，使其均匀的分布到这些 bucket 中，这个过程叫做 rehash。
  - Go 的负载因子在达到 6.5 时会触发 rehash。
  - 6.5 是一个经验值，每个桶的平均元素个数小于 6.5 时，达到最佳性能。
扩容方式：
- 增量扩容（负载因子过高）：桶数量翻倍（2^B → 2^(B+1)），降低负载因子。
- 等量扩容（溢出桶过多）：桶数量不变，重新整理键值对（rehash，解决溢出桶过多问题）。
渐进式迁移
- 迁移时机
  - 每次访问 map（插入、修改或删除）都会触发一次迁移，每次迁移 1-2 个旧桶到新桶
- 具体处理
  - 先让 hmap 数据结构中的 oldbuckets 成员指向原 buckets 数组，然后申请新的 buckets 数组，并将数组指针保存到 hmap 数据结构的 buckets 成员中。
  - 后续将 oldbuckets 中的键值对逐步搬迁到新的 buckets 数组中
  - 搬迁完毕后，释放 oldbuckets

（4）查找过程

- 计算 key 的 Hash 值
	- 根据 key 计算 Hash 值
- 定位目标桶（bucket）
	- 根据 Hash 值的低位计算桶索引：桶索引 = hash & (2^B - 1)，其中 B 是当前桶数量的指数
	- 若 map 正在扩容（oldbuckets 非空），需同时检查新旧两套桶。
- 在桶链中搜索目标 key
	- 遍历当前桶的 tophash 数组，比对 Hash 值的高 8 位
		- 若 tophash[i] 不匹配，跳过该槽位
		- 若匹配，进一步比对完整的 key（内存逐字节比较）
	- 若当前桶未找到，且存在溢出桶（overflow 指针非空），则沿溢出桶链表进行搜索
	- 遍历所有相关桶后未匹配到 key，返回零值，不会报错

5. 示例代码

package main

import "fmt"

func main() {
    // 初始化
    m := map[string]int{
        "tom": 20,
        "jim": 25,
    }

    // 增/改
    m["mike"] = 30  // 新增
    m["tom"] = 21   // 修改

    // 查
    if age, exist := m["jim"]; exist {
        fmt.Println("jim 的年龄：", age)  // jim 的年龄：25
    }

    // 遍历
    fmt.Println("所有键值对：")
    for name, age := range m {
        fmt.Printf("%s: %d ", name, age)  // 顺序不确定，如 tom:21 jim:25 mike:30
    }
    fmt.Println()

    // 删除
    delete(m, "jim")
    fmt.Println("删除 jim 后：", m)  // 删除 jim 后：map[mike:30 tom:21]

    // 清空（Go 1.21+）
    clear(m)
    fmt.Println("清空后：", m)  // 清空后：map[]
}

红炉点雪