Go 核心数据结构#

1.1.1 底层结构#

• string是结构体，包含两个字段：
  • Data uintptr：指向底层字节数组的指针
  • Len int：字符串的字节长度

1.1.2 长度计算#

• 计算字符长度
  • 先转换成rune类型，之后进行计算
• unsafe.Sizeof计算
  • 字符串结构体在64位系统中占16字节（指针8字节 + 长度8字节）
  • unsafe.Sizeof只计算结构体本身大小，不包含底层数据
• len计算长度
  • 字母长度为1，中文长度为3（UTF-8编码）

1
s1 := "abc"
2
s2 := "中文"
3

4
//Len(s1): 3, unsafe.Sizeof(s1): 16
5
//Len(s2): 6, unsafe.Sizeof(s2): 16
6
fmt.Printf("Len(s1): %d, unsafe.Sizeof(s1): %d\n", len(s1), unsafe.Sizeof(s1))
7
fmt.Printf("Len(s2): %d, unsafe.Sizeof(s2): %d\n", len(s2), unsafe.Sizeof(s2))

1.1.3 字符串操作#

• 字符串拼接方式
  • 大量拼接推荐：strings.Builder（预分配、避免重复内存分配）
  • 少量拼接：+ 操作符即可
  • 已有切片：strings.Join
  • 需要缓冲区操作：bytes.Buffer
  • 格式化函数：fmt.Sprintf

1.1.4 内存问题#

• 字符串切片导致内存泄漏

  • 截取的子字符串会持有原字符串的底层数组引用，导致整个原字符串无法被GC回收

• 如何避免字符串截取导致的内存泄漏

  • 转字节切片再转回：string([]byte(s[start]))
  • 截取后在前面拼接一个字符串，然后再截取掉这个字符串
  • strings.Builder 重新构造

1.1.5 字符串转换#

• 字符串和切片相互转换会发生内存拷贝吗？

  • 正常转换会发生内存拷贝，因为string是不可变的，[]byte是可变的

• 如何实现零拷贝（注意：违反Go类型安全，生产环境慎用）

  1
  // Go 1.20+ 推荐方式
  2
  func b2s(b []byte) string {
  3
      return unsafe.String(unsafe.SliceData(b), len(b))
  4
  }
  5
  
  6
  func s2b(s string) []byte {
  7
      return unsafe.Slice(unsafe.StringData(s), len(s))
  8
  }
  9
  
  10
  // Go 1.20之前的方式
  11
  func b2sOld(b []byte) string {
  12
      return *(*string)(unsafe.Pointer(&b))
  13
  }
  14
  
  15
  func s2bOld(s string) []byte {
  16
      sh := (*reflect.StringHeader)(unsafe.Pointer(&s))
  17
      bh := reflect.SliceHeader{
  18
          Data: sh.Data,
  19
          Len:  sh.Len,
  20
          Cap:  sh.Len,
  21
      }
  22
      return *(*[]byte)(unsafe.Pointer(&bh))
  23
  }
  

1.2.1 底层结构#

• slice是结构体，包含三个字段：
  • array unsafe.Pointer：指向底层数组的指针
  • len int：切片的长度
  • cap int：切片的容量

1.2.2 数组vs切片#

• 数组的缺点
  • 长度固定，传值开销大
• 切片的优点
  • 长度可变
  • 值传递但只传递切片头（64位系统24字节：指针8字节 + len 8字节 + cap 8字节）
  • 虽然是值传递，但由于包含指针，修改会影响原数据

1.2.3 共享底层数组#

• 当slice1和slice2共用一片底层空间的时候，改变slice2的长度和cap会影响slice1吗？
  • 独立部分：每个切片的len和cap独立维护
  • 共享部分：底层数组数据共享，修改会相互影响
  • 注意：append可能触发扩容，扩容后不再共享

1.2.4 扩容机制#

• 触发条件
  • append时len超过cap
• 扩容策略（Go 1.18+）
  • 预检查
    • 新长度不能溢出（变负数会panic）
    • 元素大小为0直接返回
  • 容量计算
    • 如果 newCap > oldCap * 2，则使用 newCap
    • 否则：
      • oldCap < 256：翻倍扩容
      • oldCap >= 256：按照 newcap = oldcap + (oldcap+3*256)/4 公式扩容
      • 扩容因子从2.0逐渐下降到1.25
  • 内存对齐
    • 根据元素大小和数量，向上对齐到内存分配器的size class
    • 最终容量可能大于计算值

1.3.1 对齐边界#

每个类型都有自己的对齐边界（alignment）

• int8/byte/bool: 1字节对齐
• int16/uint16: 2字节对齐
• int32/uint32/float32: 4字节对齐
• int64/uint64/float64/pointer: 8字节对齐
• string: 8字节对齐（64位系统）
• slice: 8字节对齐（64位系统）

1.3.2 字段对齐规则#

• 字段地址要求：字段的起始地址必须是其对齐边界的倍数

1.3.3 空结构体特殊处理#

• 大小为0：struct{}占用0字节
• 在结构体开头或中间：不占用空间
• 在结构体末尾：需要padding，结构体整体大小必须是最大字段对齐倍数

2.1.1 链表法#

• 将相同的哈希地址链接在一个链表中称为同义词表，哈希表存储同义词表的头指针
• 简单，没有堆积现象，当负载因子比较大的时候比较消耗时间

2.1.2 开放地址法#

• 碰撞的时候在散列表中形成一个探测序列，沿着序列查找，直到碰到开放地址为止
• 不需要额外的指针空间，当负载因子比较小的时候效率高，过程复杂，有可能失败，会出现堆叠现象，删除也比较困难

2.1.3 搜索树#

• 平衡搜索树 ⇒ 红黑树等

2.3.1 写入数据#

1. 计算哈希 => 调用哈希函数得到 hash(key)。
   • 低位 bits：确定 key 属于哪个 bucket（hash & (2^B - 1)，其中 B 是 bucket 数量的指数）。
   • 高位 bits：存储在 bucket 的 tophash 中，用于桶内快速筛选。
2. 定位 bucket
   • 通过低位哈希找到目标 bucket。
   • 遍历 bucket 的 8 个槽位：
     • 先比较 tophash（高 8 位），不匹配就直接跳过。
     • 如果 tophash 匹配，再做完整 key 比较。
3. 更新或继续查找
   • 找到相同 key：直接更新 value。
   • 未找到 key：
     • 如果当前 bucket 有空位，直接插入。
     • 如果 bucket 已满，沿着 overflow bucket 链表继续查找。
4. 插入新 key
   • 在找到的空位写入 key 和 value，并记录对应的 tophash。
   • 如果溢出桶也满了，则新建 overflow bucket 并挂到链表上。
5. 扩容检查
   • 触发扩容的条件：
     • 负载因子超过 6.5（count / bucket_count > 6.5）。
     • overflow bucket 过多（避免过长链表）。
   • 扩容时：
     • 如果是等量扩容（overflow 太多）：bucket 数量不变，只是重新整理数据。
     • 如果是加倍扩容（负载因子太高）：bucket 数量翻倍，重新分布数据（rehash）。

2.3.2 读取数据#

1. 计算哈希 => 调用哈希函数得到 hash(key)
   • 低位 bits：确定 key 属于哪个 bucket（hash & (2^B - 1)，其中 B 是 bucket 数量的指数）
   • 高位 bits：存储在 bucket 的 tophash 中，用于桶内快速筛选
2. 定位 bucket
   • 通过低位哈希找到目标 bucket
   • 遍历 bucket 的 8 个槽位：
     • 先比较 tophash（高 8 位），不匹配就直接跳过
     • 如果 tophash 匹配，再做完整 key 比较
     • 如果找到了匹配的 key，直接返回对应的 value
3. overflow 桶查找
   • 如果当前 bucket 未找到，沿着 overflow 链表继续查找
   • 每个 overflow bucket 内同样先比 tophash，再比 key
4. 返回结果
   • 找到 key → 返回 value
   • 未找到 key → 返回 zero value

2.4.1 扩容触发条件#

• 负载因子超过6.5（count/2^B > 6.5）
• overflow bucket过多（B <= 15时，overflow bucket数量 >= 2^B；B > 15时，overflow bucket数量 >= 2^15）

2.4.2 扩容规则#

• 负载因子超载，双倍重建 ⇒ 加倍扩容
• 溢出桶的数量过多，等量重建 ⇒ 等量扩容

2.4.3 扩容过程#

• 加倍扩容
  • 新的桶会存储到buckets字段，旧的桶会存储到oldbuckets字段
  • 数据转移遵循渐进式迁移规则 ⇒ 并不是一次性转移，减少扩容的开销
  • 迁移的过程中，新的哈希表会被标记正在扩容的状态 ⇒ 查找值的时候会在新旧两个哈希表查找
  • 迁移完成后，旧的哈希表会被丢弃，释放其占用的内存空间
  • 哈希表的大小是2的幂次方
• 等量扩容
  • 在当前bucket里整理overflow链表，将数据重新整理到新bucket中，减少碎片

2.5.1 key为什么是无序的#

• 插入键值对的顺序并不能决定在哈希表中的位置
• map会进行渐进式迁移
• Go故意在遍历时随机化起始位置，防止程序依赖遍历顺序

2.5.2 如何有序输出#

• 将key拷贝到slice中，对slice中的Key排序
• 之后根据key取出对应的value

2.5.3 为什么不能对map的元素取地址#

• map扩容和重整会导致键值的分布重新分布
• map中的元素会因为各种原因改变位置

2.5.4 nil map和空map的区别#

• nil map
  • 变量被声明但未初始化，也就是未分配内存的map
  • 写入nil map会panic，读取返回零值
• 空map
  • 已经初始化的map但是还没有写入数据
  • 空map是合法的，可以读写

2.6.1 删除key内存释放问题#

• map不会因为删除key value直接释放内存
• map使用的是渐进式迁移，即使删除了key也不会立马回收

2.6.2 内存泄漏原因#

• map使用的是渐进式迁移，即使删除了key也不会立马回收
• 值为指针类型时，删除key后指针仍占用bucket空间

2.6.3 如何释放map内存#

• 方法一：将map设置为nil，等待GC回收
• 方法二：创建新的空map替换旧map
• 方法三：对于长期存在的map，定期重建（创建新map，复制需要的数据，替换旧map）

2.7.1 无锁更新map#

• 使用sync.Map实现并发安全
• Copy-On-Write模式：创建map副本，修改后通过atomic.Value原子替换

2.7.2 sync.Map实现原理#

• 与普通map的区别
  • 可以在多个goroutine之间并发读写，不需要加锁
  • 键值类型都是interface{}
  • 无须初始化，声明即可使用
  • 对底层数据进行了优化，性能比普通map加锁要好
• 实现机制
  • read和dirty分离，实现了不需要锁的操作，适用于读多写少

3.1.1 底层数据结构#

• 本质上一个有锁的队列
• 环形缓冲区（buf）：存储数据的循环队列，大小固定
• 发送等待队列（sendq）：阻塞的发送者goroutine链表
• 接收等待队列（recvq）：阻塞的接收者goroutine链表

3.1.2 同步机制#

• 互斥锁：保护channel的并发访问
• 阻塞/唤醒：使用runtime的gopark/goready机制
• 协作调度：与Go调度器紧密集成

3.1.3 缓冲与阻塞#

• 无缓冲时候需要接收和发送同时准备好，不然就阻塞 ⇒ 同步模式
• 有缓冲的时候，队列为空，接收阻塞，队列满，发送阻塞 ⇒ 异步模式

3.1.4 数据传递#

• channel传递数据的时候数据通常发生复制，确保数据并发安全

3.1.5 关闭channel#

• 向已关闭的channel发送数据会panic
• 从已关闭的channel接收数据：
  • 如果缓冲区有数据，正常接收
  • 如果缓冲区为空，立即返回零值和false
• 重复关闭channel会panic
• 关闭nil channel会panic

3.1.6 收发操作流程#

• 发送流程

  1. 加锁
  2. 检查channel是否关闭（关闭则panic）
  3. 优先级判断：
     • recvq有等待者 → 直接传递数据，唤醒接收者
     • 缓冲区有空间 → 写入缓冲区
     • 否则 → 发送者加入sendq并阻塞
  4. 解锁

• 接收流程

  1. 加锁
  2. 优先级判断：
     • sendq有等待者且缓冲区满 → 从缓冲区取数据，发送者数据入缓冲区，唤醒发送者
     • 缓冲区有数据 → 直接从缓冲区读取
     • sendq有等待者（无缓冲） → 直接从发送者接收
     • 否则 → 接收者加入recvq并阻塞
  3. 解锁

3.2.1 作用#

• 多路复用：同时监听多个channel的IO操作
• 同步：协调多个goroutine的通信
• 非阻塞通信：配合default实现非阻塞channel操作

3.2.2 select{}的作用#

• 阻塞等待，让goroutine挂起，常用于main函数保持程序运行

3.2.3 基础特性#

• 每个case必须是channel操作（send/receive）
• 同一时刻只执行一个case
• case中的channel表达式仅评估一次

3.2.4 执行顺序#

• 随机性：多个case就绪时随机选择（避免饥饿）
• 公平性：每个case有相等的执行机会
• 非确定性：相同输入可能产生不同执行路径

3.3.1 底层结构（Go 1.19+）#

• noCopy：用于go vet检测，防止复制
• state atomic.Uint64：存储状态信息
  • 高32位：counter计数器
  • 低32位：waiter等待者数量
• sema uint32：信号量，用于阻塞和唤醒

3.4.1 锁的类型#

• 互斥锁（Mutex）：独占锁，同时只能有一个goroutine持有
• 读写锁（RWMutex）：允许多个读锁或一个写锁

3.4.2 通用规则#

• 不可重入性：同一goroutine获取锁后不能再次获取同一把锁（会死锁，不是抛出err）
• 解锁规则：未加锁时解锁 → panic，可以跨goroutine（A加锁，B解锁）→ 允许但不推荐

3.4.3 互斥锁#

• 规则：同一时刻只能有一个goroutine持有锁，其他goroutine必须等待
• 底层实现
  • state int32：当前互斥锁的状态，转成二进制位，包含状态信息
  • sema uint32：控制锁的信号量

3.4.4 读写锁#

• 规则
  • 读锁之间不互斥 → 多个读可以同时进行
  • 写锁与任何锁都互斥 → 写时独占，不能有任何其他锁
  • 读锁与写锁互斥 → 读时不能写，写时不能读
• 底层实现
  • w Mutex：内部的互斥锁，用于写锁
  • writerSem uint32：信号量，写锁等待所有读锁释放
  • readerSem uint32：信号量，读锁等待写锁释放
  • readerCount int32：当前持有读锁的goroutine数量（负数表示有写锁等待）
  • readerWait int32：写锁等待的读锁数量

4.1.1 进程#

• 进程是操作系统中独立运行的程序实例，拥有独立的内存空间
• 操作系统以进程为单位分配系统资源，是系统分配资源的基本单位

4.1.2 线程#

• 进程中的执行单元，共享进程的内存空间，CPU调度的基本单位

4.1.3 切换开销#

• 硬件的上下文切换开销
• 内核栈的切换开销
• 切换前需要保存执行流程的状态到寄存器
• 导致CPU高速缓存失效(TLB)，虚拟地址转物理地址变慢

4.1.4 协程（Goroutine）#

• 本质上是一种比线程更轻量级的并发执行单元，是一种用户态的线程
• 特点
  • 完全在用户态管理和调度
  • 初始栈极小（2KB），可动态增长
  • 由Go运行时调度器管理