Go语言map、slice、channel底层实现（go面试）

slice

切片是一个引用类型，其底层实现是一个结构体，包含以下字段：

ptr：一个指向底层数组的指针，指针指向数组的第一个元素。
len：切片当前包含的元素数量。
cap：切片的容量，即底层数组从切片的起始位置到底层数组末尾的元素数量。

Map

map 的底层实现是一个哈希表（hash table），实际上是维护一个数组，它通过将键映射到一个固定大小的数组（桶）中，然后在每个桶中存储对应的值。通过哈希函数，可以将键转换为数组索引，从而快速定位到对应的桶。
如何解决哈希冲突：每个桶存储了一个链表或红黑树，用于解决哈希冲突（多个键映射到同一个桶的情况）在哈希表（hash table）中，桶（bucket）是用于存储键值对的容器。每个桶可以存储一个或多个键值对。

map 的底层数据结构是 hmap 结构体：

type hmap struct {
	count     int #表示当前 map 中的键值对数量。
	flags     uint8 #表示一些标志位，用于标识 map 的状态和特性。
	B         uint8 #表示桶的数量的对数。B 的值决定了哈希表的大小，即桶的数量为 2^B。
	noverflow uint16 #表示溢出桶的数量，即哈希冲突时使用的额外桶的数量
	hash0     uint32 #表示哈希种子值，用于计算键的哈希值

	buckets    unsafe.Pointer #是一个指向桶数组的指针，存储了实际的键值对数据
	oldbuckets unsafe.Pointer #是一个指向旧的桶数组的指针，用于扩容时的过渡状态
	nevacuate  uintptr #表示正在迁移的桶的数量，即正在从旧桶迁移到新桶的过程中的桶数量

	extra *mapextra #是一个指向额外信息的指针，用于存储一些额外的数据
}
1
2
3
4
5
6
7
8
9
10
11
12
13

map底层如何删除一个键值对：

delete(mp, "name")
1

从底层角度讲，分为以下几个步骤

1：根据key计算哈希，值找到对应的桶
2：在桶中遍历链表或者红黑树找到对应节点
3：根据链表or红黑树的规则删除节点
4：删除节点后，桶中没有其他节点了，将桶置为 nil，表示该桶为空
5：更新 map 的计数器count，将键值对的数量减一

1
2
3
4
5
6

懂得了如何删除，插入和查询大概流程也是这样，插入先检查有无节点，有则更新，无则插入并且对count++，查询直接遍历就行

channel

通道底层数据结构是 hchan 结构体

type hchan struct {
	qcount   uint           // 当前队列中的元素个数
	dataqsiz uint           // 缓冲区的大小
	buf      unsafe.Pointer // 缓冲区的指针
	elemsize uint16         // 元素的大小
	closed   uint32         // 通道是否已关闭的标志
	elemtype *_type         // 元素的类型
	sendx    uint           // 发送操作的索引
	recvx    uint           // 接收操作的索引
	recvq    waitq          // 接收操作的等待队列
	sendq    waitq          // 发送操作的等待队列
	lock     mutex          // 互斥锁
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里对channel的操作遇到注意几个点：
对已经关闭的通道写入：报错
对已经关闭的通道读取：（1）若通道有数据：数据照样读取出来
（2）若通道无数据：返回通道类型的零值和false

最后，学习一项数据结构或者技巧，我们不仅仅要掌握如何使用，最好要了解他们背后的原理，这样可以加深对其的理解