数据结构

# 数据类型

# 数据类型占用的字节数

# 整数

int 64位操作系统默认为int64,32位操作系统为int32,但是类型检查时时int
int8 (byte 1字节)
int16 (short 2字节)
int32 (int 4字节)
int64 (long 8字节)

# 浮点数

float32 (4字节 float)
float64 (8字节 double)

# 字符型

golang没有专门的char类型，一般用单个byte保存单个字母字符

# 数组

数组初始化几种方式

arr1 := [3]int{1, 2, 3}
arr2 := [...]int{1, 2, 3}

1
2

编译器会进行下面的优化

当元素数量小于或者等于 4 个时，会直接将数组中的元素放置在栈上；
当元素数量大于 4 个时，会将数组中的元素放置到静态区并在运行时取出；

# 切片

数组用的其实不多，更常用的是切片，也叫动态数组，长度不固定，我们可以想切片中追加元素。

# 切片的数据结构

type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}

1
2
3
4
5

Data 是指向数组的指针;
Len 是当前切片的长度；
Cap 是当前切片的容量，即 Data 数组的大小：

# 切片初始化

arr[0:3] or slice[0:3]
slice := []int{1, 2, 3}
slice := make([]int, 10)

1
2
3

# 获取切片长度

使用 len 和 cap 获取长度或者容量是切片最常见的操作

slice:=[]int{1,2,3}
fmt.Println(len(slice))
fmt.Println(cap(slice))
//3
//3

1
2
3
4
5

# 切片扩容

如果期望容量大于当前容量的两倍就会使用期望容量；
如果当前切片的长度小于 1024 就会将容量翻倍（扩容2倍）；
如果当前切片的长度大于 1024 就会每次增加 25% 的容量（扩容1.25倍），直到新容量大于期望容量；
切片的最大大小与系统位数有关，如果是64位系统那么就是math.MaxUint64，也就是2的64次方-1

# 切片拷贝

使用 copy(a, b) 来进行拷贝，拷贝是之间把整块内存中的内容拷贝到目标的内存区域中

# 哈希表

说白了就是map

# 底层数据结构

分为 hmap 和 bmap （也叫bucket），hmap字段如下

bmap字段结构如下

hmap里面包含buckets的数组指针，然后buckets里main就以链表的形式来存储数据

最后的实际构如下

这里写图片描述

参考：解剖Go语言map底层实现 - 菜刚RyuGou的博客 (i6448038.github.io) (opens new window)

# hash碰撞解决方法

开放地址法 依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中
拉链法 实现拉链法一般会使用数组加上链表（go默认采用的方法）

# 特点

哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。

# map扩容

随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的 数量翻倍 ，元素再分配的过程也是在调用写操作时 增量进行 的，不会造成性能的瞬时巨大抖动。

下面两种情况会触发扩容

装载因子已经超过 6.5；
哈希使用了太多溢出桶；

因为 Go 语言哈希的扩容不是一个原子的过程，所以 runtime.mapassign (opens new window) 还需要判断当前哈希是否已经处于扩容状态，避免二次扩容造成混乱。
扩容过程不是原子的，而是通过 runtime.growWork (opens new window) 增量触发的
在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流。除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会整理哈希的内存减少空间的占用。

map参考：理解 Golang 哈希表 Map 的原理 | Go 语言设计与实现 (draveness.me) (opens new window)

# 并发相关

Go 的 map 不是并发安全的，这是设计人员经过长期讨论做出的决定：因为大部分使用 map 的场景不需要并发读写，如果将 map 设计为并发安全的，将降低大多数程序的性能。

只有在更新 map 的时候，map 才是并发不安全的，全部是读操作的并发是安全的。Go 1.6 对 map 的并发读写进行了更明确的规定 (opens new window)：当一个协程正在对 map 进行写操作的时候，不能有其它协程在对同一个 map 进行操作，读和写都不行。Go 的 runtime 会对 map 的并发读写进行监测，如果发现不安全的操作直接 crash。

sync.Map 才是并发安全的，下面贴一下简单的使用方法

package main
import (
    "sync"
    "fmt"
)

func main() {
    //开箱即用
    var sm sync.Map
    //store 方法,添加元素
    sm.Store(1,"a")
    //Load 方法，获得value
    if v,ok:=sm.Load(1);ok{
        fmt.Println(v)
    }
    //LoadOrStore方法，获取或者保存
    //参数是一对key：value，如果该key存在且没有被标记删除则返回原先的value（不更新）和true；不存在则store，返回该value 和false
    if vv,ok:=sm.LoadOrStore(1,"c");ok{
        fmt.Println(vv)
    }
    if vv,ok:=sm.LoadOrStore(2,"c");!ok{
        fmt.Println(vv)
    }
    //遍历该map，参数是个函数，该函数参的两个参数是遍历获得的key和value，返回一个bool值，当返回false时，遍历立刻结束。
    sm.Range(func(k,v interface{})bool{
        fmt.Print(k)
        fmt.Print(":")
        fmt.Print(v)
        fmt.Println()
        return true
    })
}