Data Structure

Go 中常用数据结构

Slice实现

Slice结构如下

slice struct {
  array unsafe.Pointer
  len int
  cap int
}

Slice底层依赖于数组来实现，有一个数组指针，指向实际存储数据的数组。

• len指的是slice创建时制定的大小。
• cap与数据数组的容量有关，当然创建时也可指定。

append时，当cap足够（即比len大），则不会更换底层的数组。

多个slice可以指向同一个数组，同时他们的len和cap都可以指定，修改元素、新增时其他slice会感受到，但新增更换底层数组就不是同一个数组，也就感受不到了。

String实现

String的结构如下

type stringStruct struct {
  str unsafe.Pointer 
  len int
}

值得注意的是，

len表示的是占的字节个数。比如：

s := "你好"
fmt.Println(len(s)) // len(s) = 6

字符串可为空，但不可为nil，也不支持修改。为什么不支持修改呢？

1. 像C++中的string，它本身是含有内存空间的，所以支持修改string。而在go的实现中，string只有一个内存的指针，不含实际存储空间，这样做的好处是string非常轻量，可以很方便的传递，不用担心太多内存拷贝。
2. 因为string通常指向字符串字面量，而字符串字面量一般位于只读段，而不是堆或者栈，所以才有了不可修改的设定。

字符串的构建

可以通过双引号和反引号来构建字符串。

s1 := "str"
s2 := ` Jiahao Sa: "Hello" ` //生字符串，不做任何转义。

通常是先构建stringStruct,再强转成string。

//go:nosplit
func gostringnocopy(str *byte) string {
  ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)} // 先构造 stringStruct
  s := *(*string)(unsafe.Pointer(&ss)) // stringStruct 转换成 string
  return s
}

[]byte与string互相转换

string 的数据结构有点类似于切片，切片比它多了一个容量成员。string 和 byte 切片经常互转。

func ByteToString(s []byte) string {
  return string(s)
}

func StringToByte(str string) []byte {
  return []byte(str)
}

转换的过程是深拷贝，涉及新内存的分配与内容拷贝。但特定情况下，无需拷贝内存。

有时只是临时需要字符串的场景下，byte 切片转换成 string 时并不会拷贝内存，而是直接返回一个 string，这个 string 的指针指向切片的内存。如

• 使用 m[string(b)] 来查找 map（map 是 string 为 key，临时把切片 b 转成 string）
• 字符串拼接，如”<” + “string(b)” + “>”
• 字符串比较：string(b) == “foo”

[]byte与string应用场景区别

• []byte适用于

  1. 修改字符，尤其是修改粒度为一个字符的场景。

  2. 需要nil值，作为一个slice，可以指向nil。

  3. 需要slice操作的场景。

• string适用于

  1. 不需要nil的场景
  2. 需要比较字符串的场景。

实际上，string更具有可读性，所以适用范围更多。偏底层时，[]byte才使用更多。

字符串拼接

str := "str1" + "str2" + "str3" + "str4"

先计算长度再分配内存。分配好内存后，返回这个地址对应的切片，由于二者共用存储，后面向切片写入字符时，字符串就能看到修拼接后的值，也就间接修改了string。

虽然

Map实现原理

https://zhuanlan.zhihu.com/p/495998623

type hmap struct {
    count     int    // 元素的个数
    B         uint8  // buckets 数组的长度就是 2^B 个
    overflow uint16 // 溢出桶的数量
    buckets    unsafe.Pointer // 2^B个桶对应的数组指针
    oldbuckets unsafe.Pointer  // 发生扩容时，记录扩容前的buckets数组指针
    extra *mapextra //用于保存溢出桶的地址
}

B代表着当前Map的大小，表示当前有$2^B $个桶，哈希函数取模后会映射到这些桶中。下图是一个B=2的一个例子，即4个桶。

bucket的数据结构

bucket数据结构由runtime/map.go/bmap定义：

type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

每个bucket可以存储8个键值对。

• tophash是个长度为8的数组，哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。
• data区存放的是key-value数据，存放顺序是key/key/key/…value/value/value，如此存放是为了节省字节对齐带来的空间浪费。
• overflow 指针指向的是下一个bucket，据此将所有冲突的键连接起来。

注意：上述中data和overflow并不是在结构体中显示定义的，而是直接通过指针运算进行访问的。

下图展示bucket存放8个key-value对：

哈希冲突

当有多个元素经哈希函数分配到同一个桶中，即发生了哈希冲突。

go使用链地址法来解决哈希冲突。每一个桶中可以存放8个键值对，当超出时，会由overflow指向下一个桶。这样就形成了一个桶链表。如下图所示：

扩容

负载因子

负载因子用于衡量一个哈希表冲突情况，Go中的计算方式为：
$$
负载因子 = \frac{键数量}{bucket数量}
$$

例如，对于一个bucket数量为4，包含4个键值对的哈希表来说，这个哈希表的负载因子为1.

哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行rehash，也即键值对重新组织：

• 哈希因子过小，说明空间利用率低
• 哈希因子过大，说明冲突严重，存取效率低

每个哈希表的实现对负载因子容忍程度不同，比如Redis实现中负载因子大于1时就会触发rehash，而Go则在在负载因子达到6.5时才会触发rehash，因为Redis的每个bucket只能存1个键值对，而Go的bucket可能存8个键值对，所以Go可以容忍更高的负载因子。

扩容时机

为了保证访问效率，当新元素将要添加进map时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。 触发扩容的条件有二个：

1. 负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
2. overflow数量 > 2^15时，也即overflow数量超过32768时。

扩容方式

采用阻塞、全盘迁移的方式，会导致某一个请求耗时很长。所以一般采用渐进式扩容。GO中的扩容有两种

• 增量扩容：容量变大，数据迁移到更大的存储中。
• 等量扩容：容量不变，但把桶中元素变得紧凑。

渐进式扩容时的粒度是：一个hash位置。会把这个一整个桶链表迁移过去。

增量扩容

增量扩容增大B的大小，即每次至少扩大为2倍。假如当前为1个桶，扩容后变为2个，旧数据由oldbuckets指向。

hmap数据结构中oldbuckets成员指身原bucket，而buckets指向了新申请的bucket。新的键值对被插入新的bucket中。 后续对map的访问操作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后，删除oldbuckets。

等量扩容

由于链表节点是一个桶，含多个元素，所以频繁删除时，可能导致桶的稀疏。此时需要进行等量扩容来紧凑数据。

使用

查找

查找过程如下：

1. 跟据key值算出哈希值
2. 取哈希值低位与hmpa.B取模确定bucket位置
3. 取哈希值高位在tophash数组中查询
4. 如果tophash[i]中存储值与哈希值相等，则去找到该bucket中的key值进行比较
5. 当前bucket没有找到，则继续从下个overflow的bucket中查找。

如果当前处于扩容迁移过程，则优先从oldbuckets查找，再查buckets

注：如果查找不到，也不会返回空值，而是返回相应类型的0值。

插入

1. 跟据key值算出哈希值
2. 取哈希值低位与hmap.B取模确定bucket位置
3. 查找该key是否已经存在，如果存在则直接更新值
4. 如果没找到将key，将key插入

sync.Map原理

Channel实现原理

Channel结构如下

type hchan struct {
	qcount   uint //Channel 中的元素个数；
	dataqsiz uint //Channel 中的循环队列的长度；
	buf      unsafe.Pointer //Channel 的缓冲区数据指针；
	elemsize uint16 //收发元素的大小
	closed   uint32
	elemtype *_type //收发元素的类型
	sendx    uint //Channel 的发送操作处理到的位置
	recvx    uint //Channel 的接收操作处理到的位置；
	recvq    waitq //处于阻塞的接收队列
	sendq    waitq //处于阻塞的发送队列

	lock mutex //防止并发的锁
}

缓冲区

Go中的缓冲区是通过环型队列实现的，创建时指定。下图展示了一个可缓存6个元素的channel示意图：

• dataqsiz指示了队列长度为6，即可缓存6个元素；
• buf指向队列的内存，队列中还剩余两个元素；
• qcount表示队列中还有两个元素；
• sendx指示后续写入的数据存储的位置，取值[0, 6)；
• recvx指示从该位置读取数据, 取值[0, 6)；

等待队列

从channel读数据，如果channel缓冲区为空或者没有缓冲区，当前goroutine会被阻塞。 向channel写数据，如果channel缓冲区已满或者没有缓冲区，当前goroutine会被阻塞。

被阻塞的goroutine将会挂在channel的等待队列中：

• 因读阻塞的goroutine会被向channel写入数据的goroutine唤醒；
• 因写阻塞的goroutine会被从channel读数据的goroutine唤醒；

下图展示了一个没有缓冲区的channel，有几个goroutine阻塞等待读数据：

数据类型

一个channel只能传递一种类型的值，类型信息存储在hchan数据结构中。

• elemtype代表类型，用于数据传递过程中的赋值；
• elemsize代表类型大小，用于在buf中定位元素位置。