Posted ingo 编程语言

golang的核心数据结构介绍

No Comments
golang的核心数据结构介绍
https://open.spotify.com/playlist/6zCID88oNjNv9zx6puDHKj?si=2697caec55594412&nd=1&dlsi=1ac4dd1566274a75

现在让我们设好番茄钟放一首好听的音乐开始学习吧 🌈 😋

1. 数组（Array）

基本特性

  • 固定长度：数组长度在编译期确定，是类型的一部分
  • 值类型：数组赋值和传参会发生完整拷贝
  • 连续内存：元素在内存中连续存储，访问效率 O(1)

代码示例

package main

import "fmt"

func main() {
    // 声明并初始化
    var arr1 [5]int  // 零值初始化：[0 0 0 0 0]
    arr2 := [3]int{1, 2, 3}
    arr3 := [...]int{1, 2, 3, 4}  // 编译器推导长度
    
    // 数组是值类型
    arr4 := arr2
    arr4[0] = 100
    fmt.Println(arr2)  // [1 2 3] - 原数组不变
    fmt.Println(arr4)  // [100 2 3]
    
    // 多维数组
    matrix := [2][3]int{
        {1, 2, 3},
        {4, 5, 6},
    }
    fmt.Println(matrix[1][2])  // 6
}

 

使用场景

  • 长度固定且已知的小型数据集
  • 需要栈上分配避免堆内存开销
  • 作为切片的底层存储

2. 切片（Slice）

底层结构

切片是对数组的抽象，其底层结构为：

type slice struct {
    array unsafe.Pointer  // 指向底层数组的指针
    len   int              // 当前长度
    cap   int              // 容量
}

 

核心操作

package main

import "fmt"

func main() {
    // 创建切片的三种方式
    var s1 []int              // nil 切片
    s2 := []int{}             // 空切片，len=0, cap=0
    s3 := make([]int, 5, 10)  // len=5, cap=10
    
    // append 操作
    s := []int{1, 2, 3}
    s = append(s, 4, 5)       // [1 2 3 4 5]
    s = append(s, []int{6, 7}...)  // 展开切片追加
    
    // 切片操作（左闭右开）
    sub := s[1:4]  // [2 3 4] - 共享底层数组
    sub[0] = 100
    fmt.Println(s)  // [1 100 3 4 5 6 7] - 原切片被修改
    
    // 扩容机制演示
    demonstrateGrowth()
}

func demonstrateGrowth() {
    s := make([]int, 0, 4)
    for i := 0; i < 10; i++ {
        s = append(s, i)
        fmt.Printf("len=%d cap=%dn", len(s), cap(s))
    }
    // 扩容规则：
    // - cap < 256: 按 2 倍扩容
    // - cap >= 256: 按 (cap + 3*256) / 4 增长
}

 

深拷贝 vs 浅拷贝

// 浅拷贝（共享底层数组）
s1 := []int{1, 2, 3}
s2 := s1
s2[0] = 100  // s1 也会变化

// 深拷贝
s3 := make([]int, len(s1))
copy(s3, s1)
s3[0] = 200  // s1 不受影响

 

陷阱与最佳实践

⚠️ 内存泄漏风险

3. 映射（Map）

底层实现

Go 的 map 采用哈希表 + 拉链法解决冲突：

// 简化的底层结构
type hmap struct {
    count     int            // 元素个数
    B         uint8          // 桶数量 = 2^B
    buckets   unsafe.Pointer // 桶数组指针
    oldbuckets unsafe.Pointer // 扩容时的旧桶
}

type bmap struct {  // 每个桶
    tophash [8]uint8  // 键哈希值的高 8 位
    keys    [8]keytype
    values  [8]valuetype
    overflow *bmap    // 溢出桶
}

 

基本用法

package main

import "fmt"

func main() {
    // 创建 map
    var m1 map[string]int           // nil map，不能写入
    m2 := map[string]int{}          // 空 map
    m3 := make(map[string]int, 10)  // 预分配容量
    
    // 增删改查
    m := map[string]int{
        "Alice": 25,
        "Bob":   30,
    }
    
    m["Charlie"] = 35          // 新增
    m["Alice"] = 26            // 修改
    delete(m, "Bob")           // 删除
    
    // 安全访问（检查键是否存在）
    if age, ok := m["David"]; ok {
        fmt.Println(age)
    } else {
        fmt.Println("Key not found")
    }
    
    // 遍历（无序）
    for k, v := range m {
        fmt.Printf("%s: %dn", k, v)
    }
}

 

并发安全

🔒 map 不是并发安全的

扩容机制

  • 负载因子：count / (2^B * 8) > 6.5 时触发扩容
  • 增量扩容：不是一次性重建，而是渐进式迁移（避免 STW）
  • 等量扩容：溢出桶过多时，重新整理内存布局

4. 通道（Channel）

⚠️需要结合并发与协程

核心概念

通道是 Go 并发编程的核心，实现了 CSP（Communicating Sequential Processes）模型。

底层结构

type hchan struct {
    qcount   uint           // 当前队列中的元素数
    dataqsiz uint           // 环形队列大小
    buf      unsafe.Pointer // 环形队列指针
    elemsize uint16         // 元素大小
    sendx    uint           // 发送索引
    recvx    uint           // 接收索引
    recvq    waitq          // 等待接收的 goroutine 队列
    sendq    waitq          // 等待发送的 goroutine 队列
    lock     mutex          // 互斥锁
}

 

三种类型

package main

import (
    "fmt"
    "time"
)

func main() {
    // 1. 无缓冲通道（同步）
    ch1 := make(chan int)
    go func() {
        ch1 <- 42  // 阻塞，直到有接收者
    }()
    fmt.Println(<-ch1)  // 42
    
    // 2. 有缓冲通道（异步）
    ch2 := make(chan int, 3)
    ch2 <- 1
    ch2 <- 2
    ch2 <- 3
    // ch2 <- 4  // 阻塞，缓冲区已满
    fmt.Println(<-ch2)  // 1
    
    // 3. 单向通道（类型安全）
    ch3 := make(chan int)
    go producer(ch3)        // 只发送
    consumer(ch3)           // 只接收
}

func producer(ch chan<- int) {  // 只能发送
    for i := 0; i < 5; i++ {
        ch <- i
    }
    close(ch)
}

func consumer(ch <-chan int) {  // 只能接收
    for val := range ch {  // 自动处理关闭
        fmt.Println(val)
    }
}

 

高级用法

package main

import (
    "fmt"
    "time"
)

func main() {
    // select 多路复用
    ch1 := make(chan string)
    ch2 := make(chan string)
    
    go func() {
        time.Sleep(100 * time.Millisecond)
        ch1 <- "from ch1"
    }()
    
    go func() {
        time.Sleep(50 * time.Millisecond)
        ch2 <- "from ch2"
    }()
    
    select {
    case msg1 := <-ch1:
        fmt.Println(msg1)
    case msg2 := <-ch2:
        fmt.Println(msg2)  // 先触发
    case <-time.After(200 * time.Millisecond):
        fmt.Println("timeout")
    }
    
    // 非阻塞操作
    select {
    case msg := <-ch1:
        fmt.Println(msg)
    default:
        fmt.Println("no message")  // 立即执行
    }
    
    // 关闭检测
    ch := make(chan int, 2)
    ch <- 1
    ch <- 2
    close(ch)
    
    for {
        val, ok := <-ch
        if !ok {
            fmt.Println("channel closed")
            break
        }
        fmt.Println(val)
    }
}

 

最佳实践

✅ 通道使用原则

5. 结构体（Struct）

内存布局与对齐（和C语言的内存对齐机制一致）

package main

import (
    "fmt"
    "unsafe"
)

type BadStruct struct {
    a bool   // 1 字节
    b int64  // 8 字节（需对齐到 8 字节边界）
    c bool   // 1 字节
}

type GoodStruct struct {
    b int64  // 8 字节
    a bool   // 1 字节
    c bool   // 1 字节
}

func main() {
    fmt.Println(unsafe.Sizeof(BadStruct{}))   // 24 字节（浪费空间）
    fmt.Println(unsafe.Sizeof(GoodStruct{}))  // 16 字节（优化后）
}

 

嵌入与组合

package main

import "fmt"

type Animal struct {
    Name string
}

func (a Animal) Speak() {
    fmt.Println(a.Name, "makes a sound")
}

type Dog struct {
    Animal  // 嵌入（匿名字段）
    Breed string
}

func (d Dog) Speak() {  // 方法重写
    fmt.Println(d.Name, "barks")
}

func main() {
    d := Dog{
        Animal: Animal{Name: "Buddy"},
        Breed:  "Golden Retriever",
    }
    
    d.Speak()         // Buddy barks（使用重写方法）
    d.Animal.Speak()  // Buddy makes a sound（访问嵌入类型方法）
    fmt.Println(d.Name)  // Buddy（提升字段）
}

 

标签（Tag）与反射

package main

import (
    "encoding/json"
    "fmt"
    "reflect"
)

type User struct {
    ID       int    `json:"id" db:"user_id"`
    Name     string `json:"name" validate:"required"`
    Password string `json:"-"`  // 序列化时忽略
}

func main() {
    u := User{ID: 1, Name: "Alice", Password: "secret"}
    
    // JSON 序列化
    data, _ := json.Marshal(u)
    fmt.Println(string(data))  // {"id":1,"name":"Alice"}
    
    // 反射读取标签
    t := reflect.TypeOf(u)
    field, _ := t.FieldByName("ID")
    fmt.Println(field.Tag.Get("json"))  // id
    fmt.Println(field.Tag.Get("db"))    // user_id
}

 

6. 接口（Interface）

底层结构

// 空接口 interface{}
type eface struct {
    _type *_type         // 动态类型信息
    data  unsafe.Pointer // 动态值指针
}

// 非空接口
type iface struct {
    tab  *itab           // 接口表（类型 + 方法集）
    data unsafe.Pointer  // 动态值指针
}

 

动态派发

package main

import "fmt"

type Shape interface {
    Area() float64
}

type Circle struct {
    Radius float64
}

func (c Circle) Area() float64 {
    return 3.14 * c.Radius * c.Radius
}

type Rectangle struct {
    Width, Height float64
}

func (r Rectangle) Area() float64 {
    return r.Width * r.Height
}

func printArea(s Shape) {
    fmt.Printf("Area: %.2fn", s.Area())  // 动态派发
}

func main() {
    c := Circle{Radius: 5}
    r := Rectangle{Width: 4, Height: 6}
    
    printArea(c)  // Area: 78.50
    printArea(r)  // Area: 24.00
    
    // 类型断言
    var s Shape = c
    if circle, ok := s.(Circle); ok {
        fmt.Println("Radius:", circle.Radius)
    }
    
    // 类型判断
    switch v := s.(type) {
    case Circle:
        fmt.Println("This is a circle with radius", v.Radius)
    case Rectangle:
        fmt.Println("This is a rectangle")
    }
}

 

7. 性能对比与选型

基准测试示例

package main

import "testing"

func BenchmarkArrayAccess(b *testing.B) {
    arr := [1000]int{}
    for i := 0; i < b.N; i++ {
        _ = arr[500]
    }
}

func BenchmarkSliceAccess(b *testing.B) {
    slice := make([]int, 1000)
    for i := 0; i < b.N; i++ {
        _ = slice[500]
    }
}

func BenchmarkMapAccess(b *testing.B) {
    m := make(map[int]int)
    for i := 0; i < 1000; i++ {
        m[i] = i
    }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = m[500]
    }
}

 

选型建议

数据结构时间复杂度适用场景
ArrayO(1) 访问固定长度、栈分配
SliceO(1) 访问、O(1) 均摊追加动态数组、大部分场景
MapO(1) 均摊查找键值存储、快速查找
ChannelO(1) 发送/接收并发通信、任务队列

总结

Go 的数据结构设计遵循简洁高效的哲学：

  1. 切片是最常用的动态数组，理解扩容机制和共享语义至关重要
  2. 映射提供高效键值存储，注意并发安全问题
  3. 通道是并发的第一公民，优先使用通道而非共享内存
  4. 接口实现多态和解耦，动态派发有一定性能开销
  5. 结构体内存对齐影响性能，合理排列字段可节省空间

深入理解这些数据结构的底层实现，能帮助你写出更高效、更地道的 Go 代码。

参考资料

 

Tags: