Go语言常见数据结构实现原理

结构体

定义与初始化

结构体是一种可以包含不同类型的字段的数据类型。 示例代码：

type Person struct {
    Name string
    Age  int
}

func main() {
    var p Person
    fmt.Println(p) // 输出: {<nil> 0}

    // 初始化方式
    p = Person{"Alice", 30}
    fmt.Println(p) // 输出: {Alice 30}
}

内存布局

• 结构体在内存中的布局遵循严格的对齐规则。
• 每个字段按照其类型所需的对齐方式进行对齐。

方法

可以为结构体定义方法。

示例代码：

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%+v", p)
}

func (p *Person) SetAge(age int) {
    p.Age = age
}

func main() {
    p := Person{"Alice", 30}
    fmt.Println(p.String()) // 输出: {Name:Alice Age:30}

    p.SetAge(35)
    fmt.Println(p) // 输出: {Alice 35}
}

指针

基本概念

指针存储的是另一个变量的内存地址。

示例代码：

package main

import "fmt"

func main() {
    a := 10
    p := &a // 获取a的地址
    fmt.Println(*p) // 输出: 10
}

修改值

通过指针可以修改原变量的值。

示例代码：

func update(a *int) {
    *a = 20
}

func main() {
    x := 5
    update(&x)
    fmt.Println(x) // 输出: 20
}

字符串

字符串不可变性

Go中的字符串是不可变的。

示例代码：

s := "hello"
// 无法直接修改s的内容
// s[0] = 'H' // 错误: 字符串是只读的

字符串操作

使用strings包进行各种操作。

示例代码：

import (
    "fmt"
    "strings"
)

func main() {
    s := "hello world"
    fmt.Println(strings.ToUpper(s)) // 输出: HELLO WORLD
}

切片

基本用法

切片是基于数组的一种抽象数据类型。

示例代码：

func main() {
    arr := [5]int{1, 2, 3, 4, 5}
    slice := arr[1:3] // 创建一个切片
    fmt.Println(slice) // 输出: [2 3]
}

动态调整大小

切片支持动态扩展。

示例代码：

func main() {
    s := make([]int, 0, 5)
    for i := 0; i < 5; i++ {
        s = append(s, i)
    }
    fmt.Println(s) // 输出: [0 1 2 3 4]
}

底层数组与容量

切片包含指向数组的指针、长度和容量。

示例代码：

func main() {
    s := []int{1, 2, 3}
    fmt.Println(len(s), cap(s)) // 输出: 3 3
    s = append(s, 4)
    fmt.Println(len(s), cap(s)) // 输出: 4 6

map

底层实现

• Go语言中的map底层是一个哈希表，它由一个hmap结构体表示。
• hmap包含两个主要部分：buckets（桶）和oldbuckets（旧桶），用于实现哈希表的扩容。

数据结构

type hmap struct {
    count, B, sizehint, nevacuate int
    flags    uint8
    fill     uint16
    noverflow uint16
    buckets, oldbuckets, compare, bucket, oldbucket unsafe.Pointer
}

• count: 当前map中的元素数量。
• B: 位数，决定了桶的数量。
• sizehint: 初始大小提示。
• flags: 标志位。
• fill: 填充比例。
• noverflow: 溢出链表的元素数量。
• buckets: 指向当前桶的指针。
• oldbuckets: 指向旧桶的指针。
• compare: 比较函数。
• bucket: 当前桶的指针。
• oldbucket: 旧桶的指针。

桶结构

type bmap struct {
    overflow [1]uintptr
    keys     [0]uintptr
    values   [0]uintptr
}

• overflow: 指向溢出链表的指针。
• keys: 存放键的数组。
• values: 存放值的数组。

扩容过程

• 当map的负载因子（已使用的槽位 / 总的槽位）超过一定阈值时，Go会自动扩容map。
• 扩容时，旧的buckets会被复制到新的更大的buckets上，并重新计算哈希值以确定新位置。

删除操作

删除元素时，Go不会立即释放空间，而是标记该位置为删除状态，以便在后续的扩容过程中清理。

package main

import (
    "fmt"
)

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

    // 添加元素
    m[1] = "one"
    m[2] = "two"
    m[3] = "three"

    // 查找元素
    value, ok := m[2]
    fmt.Println(value, ok) // 输出: two true

    // 删除元素
    delete(m, 2)
    _, ok = m[2]
    fmt.Println(ok) // 输出: false
}

channel

底层实现

• channel本质上是一个环形缓冲区，由chan关键字声明。
• 包含一个指向内部队列的指针、读写索引、缓冲区大小、锁等信息。
• channel可以是带缓冲的也可以是非缓冲的，带缓冲的channel可以在不阻塞的情况下发送消息。

数据结构

type hchan struct {
    qcount   atomic.Value // number of items in circular queue
    dataqsiz int          // len of circular queue
    buf      unsafe.Pointer
    elemsize uintptr      // bytes in each elem
    closed   uint32       // closed or not
    elemtype *_type       // element type
    sendx    uint64       // send index
    recvx    uint64       // receive index
    lock mutex
    sema    uint64
}

• qcount: 队列中的元素数量。
• dataqsiz: 队列的大小。
• buf: 指向队列的指针。
• elemsize: 元素的大小。
• closed: 是否关闭。
• elemtype: 元素类型。
• sendx: 发送索引。
• recvx: 接收索引。
• lock: 互斥锁。
• sema: 信号量。

同步机制

• 非缓冲的channel在没有接收者时会阻塞发送者，反之亦然。
• 缓冲的channel在缓冲区满时会阻塞发送者，在空时会阻塞接收者。

示例代码

package main

import (
    "fmt"
    "sync"
)

func producer(ch chan int, wg *sync.WaitGroup) {
    defer wg.Done()
    for i := 0; i < 10; i++ {
        ch <- i
    }
    close(ch)
}

func consumer(ch chan int, wg *sync.WaitGroup) {
    defer wg.Done()
    for n := range ch {
        fmt.Println(n)
    }
}

func main() {
    ch := make(chan int, 10)
    var wg sync.WaitGroup

    wg.Add(2)
    go producer(ch, &wg)
    go consumer(ch, &wg)

    wg.Wait()
}

interface

底层实现

• 在Go语言中，interface是一个特殊的类型，它允许存储任何实现了该接口的方法集的对象。
• 实现interface的类型会在运行时动态绑定方法，这称为动态调度。
• 每个实现了interface的类型都会有一个指向其方法表的指针，这个方法表包含了所有该类型实现的方法。

数据结构

type eface struct {
    _type *_type
    data  unsafe.Pointer
}

type iface struct {
    tab  *itab
    data unsafe.Pointer
}

• eface: 空接口的结构体。
• _type: 类型信息。
• data: 指向实际数据的指针。
• iface: 有具体类型的接口的结构体。
• tab: 方法表。
• data: 指向实际数据的指针。

类型断言

• interface{}可以存储任何类型的值，通过类型断言可以恢复原始类型。
• 断言时，Go会检查存储的类型是否匹配目标类型，如果不匹配则会引发运行时错误。

示例代码

package main

import (
    "fmt"
)

type Shape interface {
    Area() float64
}

type Rectangle struct {
    Width  float64
    Height float64
}

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

func main() {
    rect := Rectangle{Width: 10, Height: 5}
    var shape Shape = rect

    // 类型断言
    if r, ok := shape.(Rectangle); ok {
        fmt.Println("Area:", r.Area())
    } else {
        fmt.Println("Not a Rectangle")
    }
}

方法调用

方法绑定

• 在Go中，方法是与接收者类型绑定的函数。
• 当调用一个方法时，编译器会生成一个带有额外参数（接收者）的函数调用。

动态调度

• 对于接口类型的接收者，方法调用会在运行时根据实际存储的类型来决定调用哪个方法。
• 这意味着即使在编译时不知道具体类型，只要实现了接口，就可以调用相应的方法。

示例代码

package main

import (
    "fmt"
)

type Shape interface {
    Area() float64
}

type Rectangle struct {
    Width  float64
    Height float64
}

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

func main() {
    rect := Rectangle{Width: 10, Height: 5}
    var shape Shape = rect

    // 调用方法
    fmt.Println(shape.Area()) // 输出: 50
}