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
    value...