基础语法

切片的实现原理

1. 切片的创建：

// 字面量创建
s := []int{1, 2, 3}  // 创建切片和底层数组

// make 创建
s := make([]int, 3, 5)  // len=3, cap=5

// 从数组/切片创建
arr := [5]int{1, 2, 3, 4, 5}
s := arr[1:4]  // 共享 arr 的底层数组

2. 切片的扩容机制：

当使用 append 添加元素且容量不足时，Go 会自动扩容。扩容策略如下：

package main

import "fmt"

func main() {
    s := []int{1}
    fmt.Printf("len=%d, cap=%d
", len(s), cap(s))  // len=1, cap=1

    s = append(s, 2)
    fmt.Printf("len=%d, cap=%d
", len(s), cap(s))  // len=2, cap=2

    s = append(s, 3)
    fmt.Printf("len=%d, cap=%d
", len(s), cap(s))  // len=3, cap=4 (扩容)

    s = append(s, 4, 5)
    fmt.Printf("len=%d, cap=%d
", len(s), cap(s))  // len=5, cap=8 (扩容)
}

扩容规则（Go 1.20+）：

• 新容量 ≥ 2×旧容量
• 新容量 ≥ 旧容量 + 新元素数量
• 对于大切片，扩容因子约为 1.25

3. 切片的共享问题：

package main

import "fmt"

func main() {
    slice1 := []int{1, 2, 3, 4, 5}
    slice2 := slice1[1:3]  // [2, 3]

    // 修改 slice2 会影响 slice1
    slice2[0] = 99
    fmt.Println("slice1:", slice1)  // [1, 99, 3, 4, 5]
    fmt.Println("slice2:", slice2)  // [99, 3]
}

Map 的实现原理

1. 哈希计算：

Go 使用哈希函数计算 key 的哈希值，然后根据哈希值确定元素在桶数组中的位置。

// 哈希计算示例
// 1. 计算 key 的哈希值
hash := hashFunction(key, hmap.hash0)

// 2. 取哈希值的低 B 位确定桶索引
// 例如：B=3 时，bucket 数组大小为 8
bucketIndex := hash & (uintptr(1)<1)

// 3. 取哈希值的高 8 位作为 tophash
top := uint8(hash >> (unsafe.Sizeof(hash)*8 - 8))

不同类型的 key 使用不同的哈希算法：

• 整数：直接使用整数值作为哈希
• 字符串：使用 FNV-1a 算法
• 指针：使用指针地址
• 结构体：递归计算各字段的哈希

2. 桶（Bucket）结构详解：

每个桶可以存储最多 8 个键值对（bucketSize = 8）。桶的内存布局经过优化：

type bmap struct {
    // tophash 数组：存储每个键的哈希值高 8 位
    // 用于快速判断键是否可能存在于桶中
    tophash [bucketSize]uint8
    
    // keys 和 values 数组交错存储，减少填充
    // 实际内存布局：[tophash0][tophash1]...[key0][key1]...[val0][val1]...
    keys   [bucketSize]keyType
    values [bucketSize]valueType
    
    // overflow 指向溢出桶链表
    // 当桶满时，新元素存储在溢出桶中
    overflow *bmap
}

3. 查找过程详解：

package main

import "fmt"

func main() {
    m := make(map[string]int)
    m["apple"] = 5
    m["banana"] = 3
    m["cherry"] = 7

    // 查找 "banana" 的详细过程：
    
    // 步骤 1：计算 "banana" 的哈希值
    hash := hashFunction("banana", hash0)
    fmt.Printf("哈希值: %d
", hash)
    
    // 步骤 2：计算桶索引
    bucketIndex := hash & (bucketMask)
    fmt.Printf("桶索引: %d
", bucketIndex)
    
    // 步骤 3：在桶中查找
    bucket := buckets[bucketIndex]
    for i := 0; i < bucketSize; i++ {
        // 先检查 tophash 快速过滤
        if bucket.tophash[i] != top {
            continue
        }
        
        // 再比较完整的 key
        if bucket.keys[i] == "banana" {
            // 找到匹配，返回值
            return bucket.values[i]
        }
    }
    
    // 步骤 4：检查溢出桶链表
    for bucket = bucket.overflow; bucket != nil; bucket = bucket.overflow {
        // 在溢出桶中重复步骤 3
        // ...
    }
    
    // 步骤 5：未找到，返回零值
    return zeroValue
}

4. 插入过程详解：

package main

import "fmt"

func main() {
    m := make(map[string]int)
    
    // 插入 "orange" 的过程：
    
    // 步骤 1：计算哈希和桶索引
    hash := hashFunction("orange", hash0)
    bucketIndex := hash & bucketMask
    top := uint8(hash >> (unsafe.Sizeof(hash)*8 - 8))
    
    // 步骤 2：在桶中查找空位
    bucket := buckets[bucketIndex]
    var insertPos int = -1
    
    for i := 0; i < bucketSize; i++ {
        if bucket.tophash[i] == empty {
            // 找到空位
            insertPos = i
            break
        }
    }
    
    if insertPos != -1 {
        // 桶中有空位，直接插入
        bucket.tophash[insertPos] = top
        bucket.keys[insertPos] = "orange"
        bucket.values[insertPos] = 10
    } else {
        // 桶已满，创建溢出桶
        if bucket.overflow == nil {
            bucket.overflow = newbmap()
        }
        // 在溢出桶中插入
        insertIntoOverflow(bucket.overflow, "orange", 10)
    }
    
    // 步骤 3：检查是否需要扩容
    if hmap.noverflow >= float64(hmap.count)/loadFactor {
        grow(hmap)
    }
}

5. 删除过程详解：

package main

import "fmt"

func main() {
    m := make(map[string]int)
    m["apple"] = 5
    
    // 删除 "apple" 的过程：
    
    // 步骤 1：定位 key 的位置
    hash := hashFunction("apple", hash0)
    bucketIndex := hash & bucketMask
    bucket := buckets[bucketIndex]
    
    for i := 0; i < bucketSize; i++ {
        if bucket.tophash[i] != top {
            continue
        }
        if bucket.keys[i] == "apple" {
            // 找到 key，标记为已删除
            bucket.tophash[i] = emptyOne  // 特殊标记：已删除
            bucket.keys[i] = zeroKey
            bucket.values[i] = zeroValue
            hmap.count--
            break
        }
    }
    
    // 注意：删除操作不会立即回收空间
    // 已删除的位置会被 emptyOne 标记
    // 后续插入时可以复用这些位置
}

6. 扩容机制详解：

Go 的 map 有两种扩容方式：

等量扩容（rehash）：

• 触发条件：溢出桶过多（noverflow >= 1 << (B & 15))
• 目的：减少溢出桶，提高查找效率
• 过程：重新分配相同大小的桶数组，重新哈希所有元素

增量扩容（grow）：

• 触发条件：元素数量超过负载因子（count / bucketSize > loadFactor）
• 负载因子通常为 6.5
• 目的：增加桶数量，减少哈希冲突
• 过程：桶数组大小翻倍（B++），渐进式搬迁元素

package main

import "fmt"

func main() {
    m := make(map[int]int)

    // 观察扩容过程
    for i := 0; i < 100; i++ {
        beforeB := m.B
        m[i] = i * i
        afterB := m.B
        
        if beforeB != afterB {
            fmt.Printf("扩容: B 从 %d 变为 %d
", beforeB, afterB)
        }
    }
}

7. 渐进式扩容详解：

增量扩容时，Go 采用渐进式搬迁策略：

type hmap struct {
    // ... 其他字段
    
    oldbuckets unsafe.Pointer  // 旧桶数组
    nevacuate  uintptr       // 搬迁进度：已搬迁的桶数量
    noldbuckets uintptr     // 旧桶数组大小
}

// 搬迁过程
func evacuate(hmap *hmap) {
    // 每次操作最多搬迁 2 个桶
    for i := 0; i < 2; i++ {
        // 搬迁旧桶数组的第 nevacuate 个桶
        oldbucket := (*bmap)(add(hmap.oldbuckets, 
            uintptr(hmap.nevacuate)*bucketSize))
        
        // 将桶中的所有元素重新哈希到新桶数组
        evacuateOne(oldbucket, hmap)
        
        hmap.nevacuate++
        
        // 搬迁完成，释放旧桶数组
        if hmap.nevacuate == hmap.noldbuckets {
            hmap.oldbuckets = nil
        }
    }
}

渐进式扩容的优势：

• 避免单次操作的性能抖动
• 分散扩容开销到多次操作
• 提高系统的响应性

8. 溢出桶链表：

当桶满时，新元素存储在溢出桶中，形成链表：

// 桶结构
Bucket {
    tophash: [uint8]  // [top1, top2, top3, top4, top5, top6, top7, top8]
    keys:    [KeyType]  // [key1, key2, key3, key4, key5, key6, key7, key8]
    values:  [ValueType] // [val1, val2, val3, val4, val5, val6, val7, val8]
    overflow: *Bucket    // -> 溢出桶1 -> 溢出桶2 -> ...
}

// 查找时的遍历顺序：
// 1. 主桶
// 2. 溢出桶1
// 3. 溢出桶2
// ...

9. 空位标记：

Go 使用特殊的 tophash 值标记空位：

const (
    emptyRest = 0      // 空位，后面没有元素
    emptyOne  = 1      // 已删除的位置
    minTopHash = 4     // 最小有效的 tophash
)

// 查找时：
for i := 0; i < bucketSize; i++ {
    if tophash[i] == emptyRest {
        break  // 后面没有元素了
    }
    if tophash[i] == emptyOne {
        continue  // 跳过已删除的位置
    }
    // 检查实际的键
}

10. 内存布局优化：

Go 对 map 的内存布局进行了优化：

• 减少填充：keys 和 values 数组交错存储
• 缓存友好：tophash 数组在前面，便于快速过滤
• 内存对齐：根据类型大小自动对齐

// 实际内存布局（64位系统）
// [8]byte tophash
// [8]KeyType keys
// [8]ValueType values
// 指针 overflow

// 假设 KeyType=int, ValueType=int
// tophash: 8 bytes
// keys: 8 * 8 = 64 bytes
// values: 8 * 8 = 64 bytes
// 总计: 8 + 64 + 64 = 136 bytes