数据结构¶
约 4571 个字 197 行代码 1 张图片 预计阅读时间 25 分钟
Slice¶
1. slice的底层结构是怎样的？¶
slice 的底层数据其实也是数组，slice 是对数组的封装，它描述一个数组的片段。slice 实际上是一个结构体，包含三个字段：长度、容量、底层数组。
// runtime/slice.go
type slice struct {
array unsafe.Pointer // 元素指针
len int // 长度
cap int // 容量
}
2. Go语言里slice是怎么扩容的？¶
1.17及以前
-
如果期望容量大于当前容量的两倍就会使用期望容量；
-
如果当前切片的长度小于 1024 就会将容量翻倍；
-
如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；
Go1.18及以后，引入了新的扩容规则：
当原slice容量(oldcap)小于256的时候，新slice(newcap)容量为原来的2倍；原slice容量超过256，新slice容量newcap = oldcap+(oldcap+3*256)/4
3. 从一个切片截取出另一个切片，修改新切片的值会影响原来的切片内容吗¶
在截取完之后，如果新切片没有触发扩容，则修改切片元素会影响原切片，如果触发了扩容则不会。
示例
package main
import "fmt"
func main() {
slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
s1 := slice[2:5]
s2 := s1[2:6:7]
s2 = append(s2, 100)
s2 = append(s2, 200)
s1[2] = 20
fmt.Println(s1)
fmt.Println(s2)
fmt.Println(slice)
}
运行结果：
s1 从 slice 索引2（闭区间）到索引5（开区间，元素真正取到索引4），长度为3，容量默认到数组结尾，为8。 s2 从 s1 的索引2（闭区间）到索引6（开区间，元素真正取到索引5），容量到索引7（开区间，真正到索引6），为5。
接着，向 s2 尾部追加一个元素 100：
s2 容量刚好够，直接追加。不过，这会修改原始数组对应位置的元素。这一改动，数组和 s1 都可以看得到。
再次向 s2 追加元素200
这时，s2 的容量不够用，该扩容了。于是，s2 另起炉灶，将原来的元素复制新的位置，扩大自己的容量。并且为了应对未来可能的 append 带来的再一次扩容，s2 会在此次扩容的时候多留一些 buffer，将新的容量将扩大为原始容量的2倍，也就是10了。
最后，修改 s1 索引为2位置的元素：
这次只会影响原始数组相应位置的元素。它影响不到 s2 了，人家已经远走高飞了。
再提一点，打印 s1 的时候，只会打印出 s1 长度以内的元素。所以，只会打印出3个元素，虽然它的底层数组不止3个元素。
4. slice作为函数参数传递，会改变原slice吗？¶
当 slice 作为函数参数时，因为会拷贝一份新的slice作为实参，所以原来的 slice 结构并不会被函数中的操作改变，也就是说，slice 其实是一个结构体，包含了三个成员：len, cap, array并不会变化。但是需要注意的是，尽管slice结构不会变，但是其底层数组的数据如果有修改的话，则会发生变化。若传的是 slice 的指针，则原 slice 结构会变，底层数组的数据也会变。
示例
package main
func main() {
s := []int{1, 1, 1}
f(s)
fmt.Println(s)
}
func f(s []int) {
// i只是一个副本，不能改变s中元素的值
/*for _, i := range s {
i++
}
*/
for i := range s {
s[i] += 1
}
}
程序输出：
果真改变了原始 slice 的底层数据。这里传递的是一个 slice 的副本，在 f 函数中，s 只是 main 函数中 s 的一个拷贝。在f 函数内部，对 s 的作用并不会改变外层 main 函数的 s的结构。
要想真的改变外层 slice，只有将返回的新的 slice 赋值到原始 slice，或者向函数传递一个指向 slice 的指针。我们再来看一个例子：
package main
import "fmt"
func myAppend(s []int) []int {
// 这里 s 虽然改变了，但并不会影响外层函数的 s
s = append(s, 100)
return s
}
func myAppendPtr(s *[]int) {
// 会改变外层 s 本身
*s = append(*s, 100)
return
}
func main() {
s := []int{1, 1, 1}
newS := myAppend(s)
fmt.Println(s)
fmt.Println(newS)
s = newS
myAppendPtr(&s)
fmt.Println(s)
}
程序输出
myAppend 函数里，虽然改变了 s，但它只是一个值传递，并不会影响外层的 s，因此第一行打印出来的结果仍然是 [1 1 1]。
而 newS 是一个新的 slice，它是基于 s 得到的。因此它打印的是追加了一个 100 之后的结果： [1 1 1 100]。
最后，将 newS 赋值给了 s，s 这时才真正变成了一个新的slice。之后，再给 myAppendPtr 函数传入一个 s 指针，这回它真的被改变了：[1 1 1 100 100]
Map¶
1. Go语言Map的底层实现原理是怎样的？¶
map的就是一个hmap的结构。Go Map的底层实现是一个**哈希表**。它在运行时表现为一个指向hmap结构体的指针，hmap中记录了**桶数组指针buckets、**溢出桶指针**以及**元素个数**等字段。每个桶是一个bmap结构体，能存储**8个键值对**和**8个tophash，并有指向下一个**溢出桶的指针overflow。为了**内存紧凑，bmap中采用的是先存8个键再存8个值的存储方式。
分析
hmap结构定义：
// A header for a Go map.
type hmap struct {
count int // map中元素个数
flags uint8 // 状态标志位，标记map的一些状态
B uint8 // 桶数以2为底的对数，即B=log_2(len(buckets))，比如B=3，那么桶数为2^3=8
noverflow uint16 //溢出桶数量近似值
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 指向buckets数组的指针
oldbuckets unsafe.Pointer // 是一个指向buckets数组的指针，在扩容时，oldbuckets 指向老的buckets数组(大小为新buckets数组的一半)，非扩容时，oldbuckets 为空
nevacuate uintptr // 表示扩容进度的一个计数器，小于该值的桶已经完成迁移
extra *mapextra // 指向mapextra 结构的指针，mapextra 存储map中的溢出桶
}
2. Go语言Map的遍历是有序的还是无序的？¶
Go语言里Map的遍历是**完全随机**的，并没有固定的顺序。map每次遍历,都会从一个随机值序号的桶,在每个桶中，再从按照之前选定随机槽位开始遍历,所以是无序的。
3. Go语言Map的遍历为什么要设计成无序的？¶
map 在扩容后，会发生 key 的搬迁，原来落在同一个 bucket 中的 key，搬迁后，有些 key 就要远走高飞了（bucket 序号加上了 2^B）。而遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。搬迁后，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的结果就不可能按原来的顺序了。
Go团队为了避免开发者写出依赖底层实现细节的脆弱代码，而**有意为之**的一个设计。通过在遍历时引入随机数，Go从根本上杜绝了程序员依赖特定遍历顺序的可能性，强制我们写出更健壮的代码。
4. Map如何实现顺序读取？¶
如果业务上确实需要有序遍历，最规范的做法就是将Map的键（Key）取出来放入一个切片（Slice）中，用sort包对切片进行排序，然后根据这个有序的切片去遍历Map。
package main
import (
"fmt"
"sort"
)
func main() {
keyList := make([]int, 0)
m := map[int]int{
3: 200,
4: 200,
1: 100,
8: 800,
5: 500,
2: 200,
}
for key := range m {
keyList = append(keyList, key)
}
sort.Ints(keyList)
for _, key := range keyList {
fmt.Println(key, m[key])
}
}
5. Go语言的Map是否是并发安全的？¶
map 不是线程安全的。
在查找、赋值、遍历、删除的过程中都会检测写标志，一旦发现写标志置位（等于1），则直接 panic。赋值和删除函数在检测完写标志是复位之后，先将写标志位置位，才会进行之后的操作。
检测写标志：
设置写标志：
6. Map的Key一定要是可比较的吗？为什么？¶
Map的Key必须要可比较。
首先，Map会对我们提供的Key进行哈希运算，得到一个哈希值。这个哈希值决定了这个键值对大概存储在哪个位置（也就是哪个"桶"里）。然而，不同的Key可能会产生相同的哈希值，这就是"哈希冲突"。当多个Key被定位到同一个"桶"里时，Map就没法只靠哈希值来区分它们了。此时，它必须在桶内进行逐个遍历，用我们传入的Key和桶里已有的每一个Key进行**相等（==）**比较。这样才能确保我们操作的是正确的键值对。
7. Go语言Map的扩容时机是怎样的？¶
向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容
-
装载因子超过阈值，源码里定义的阈值是 6.5，这个时候会触发双倍扩容
-
overflow 的 bucket 数量过多：
-
当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；
-
当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15
这两种情况下会触发双倍扩容
8. Go语言Map的扩容过程是怎样的？¶
Go的扩容是**渐进式（gradual）**的。它不会在触发扩容时"stop the world"来一次性把所有数据搬迁到新空间，而是只分配新空间，然后在后续的每一次插入、修改或删除操作时，才会顺便搬迁一两个旧桶的数据。这种设计将庞大的扩容成本分摊到了多次操作中，极大地减少了服务的瞬间延迟（STW），保证了性能的平滑性。
如果是触发双倍扩容，会新建一个buckets数组，新的buckets数量大小是原来的2倍，然后旧buckets数据搬迁到新的buckets。如果是等量扩容，buckets数量维持不变，重新做一遍类似双倍扩容的搬迁动作，把松散的键值对重新排列一次，使得同一个 bucket 中的 key 排列地更紧密，这样节省空间，存取效率更高
9. 可以对Map的元素取地址吗？¶
无法对 map 的 key 或 value 进行取址。会发生编译报错，这样设计主要是因为map一旦发生扩容，key 和 value 的位置就会改变，之前保存的地址也就失效了。
示例
会出现编译报错：
10. Map 中删除一个 key，它的内存会释放么？¶
不会，delete一个key，并不会立刻释放或收缩Map占用的内存。具体来说，delete(m, key) 这个操作，只是把key和value对应的内存块标记为"空闲"，让它们的内容可以被后续的垃圾回收（GC）处理掉。但是，Map底层为了存储这些键值对而分配的"桶"（buckets）数组，它的规模是不会缩小的。只有在置空这个map的时候，整个map的空间才会被垃圾回后释放
11. Map可以边遍历边删除吗¶
map 并不是一个线程安全的数据结构。如果多个线程边遍历，边删除，同时读写一个 map 是未定义的行为，如果被检测到，会直接 panic。
如果是发生在多个协程同时读写同一个 map 的情况下。 如果在同一个协程内边遍历边删除，并不会检测到同时读写，理论上是可以这样做的。但是，遍历的结果就可能不会是相同的了，有可能结果遍历结果集中包含了删除的 key，也有可能不包含，这取决于删除 key 的时间：是在遍历到 key 所在的 bucket 时刻前或者后。这种情况下，可以通过加读写锁sync.RWMutex来保证
Interface¶
1. Go语言中，interface的底层原理是怎样的？¶
Go的interface底层有两种数据结构：eface和iface。
eface是空interface{}的实现
只包含两个指针：_type指向类型信息，data指向实际数据。这就是为什么空接口能存储任意类型值的原因，通过类型指针来标识具体类型，通过数据指针来访问实际值。
iface是带方法的interface实现
包含itab和data两部分。itab是核心，它存储了接口类型、具体类型，以及方法表。方法表是个函数指针数组，保存了该类型实现的所有接口方法的地址。
分析
eface定义：
iface定义：
其中itab的结构定义如下：
type itab struct {
inter *interfacetype
_type *_type
hash uint32 // copy of _type.hash. Used for type switches.
_ [4]byte
fun [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
}
2. iface和eface的区别是什么？¶
iface和eface的核心区别在于是否包含方法信息。
eface是空接口interface{}的底层实现，结构非常简单，只有两个字段：_type指向类型信息，data指向实际数据。因为空接口没有方法约束，所以不需要存储方法相关信息。
iface是非空接口的底层实现，结构相对复杂，包含itab和data。关键是这个itab，它不仅包含类型信息，还包含了一个方法表，存储着该类型实现的所有接口方法的函数指针。
3. 类型转换和断言的区别是什么？¶
类型转换、类型断言本质都是把一个类型转换成另外一个类型。不同之处在于，类型断言是对接口变量进行的操作。对于**类型转换**而言，类型转换是在编译期确定的强制转换，转换前后的两个类型要相互兼容才行，语法是T(value)。而**类型断言**是运行期的动态检查，专门用于从接口类型中提取具体类型，语法是value.(T)
安全性差别很大
类型转换在编译期保证安全性，而类型断言可能在运行时失败。所以实际开发中更常用安全版本的类型断言value, ok := x.(string)，通过ok判断是否成功。
使用场景不同
类型转换主要解决数值类型、字符串、切片等之间的转换问题；类型断言主要用于接口编程，当你拿到一个interface{}需要还原成具体类型时使用。
底层实现也不同
类型转换通常是简单的内存重新解释或者数据格式调整；类型断言需要检查接口的底层类型信息，涉及到runtime的类型系统。
4. Go语言interface有哪些应用场景¶
Go语言的interface主要有几个核心应用场景：
-
依赖注入和解耦。通过定义接口抽象，让高层模块不依赖具体实现，比如定义一个
UserRepo接口，具体可以是MySQL、Redis或者Mock实现。这样代码更容易测试和维护，也符合SOLID原则。 -
多态实现。比如定义一个
Shape接口包含Area()方法，不同的图形结构体实现这个接口，就能用统一的方式处理各种图形。这让代码更加灵活和可扩展。 -
标准库中大量使用interface来提供统一API。像
io.Reader、io.Writer让文件、网络连接、字符串等都能用统一的方式操作；sort.Interface让任意类型都能使用标准库的排序算法。 -
还有类型断言和反射的配合使用，比如JSON解析、ORM映射等场景，先用
interface{}接收任意类型，再通过类型断言或反射处理具体逻辑。 -
插件化架构也heavily依赖interface。比如Web框架的中间件、数据库驱动、日志组件等，都通过接口定义规范，让第三方能够轻松扩展功能。
5. 接口之间可以相互比较吗？¶
-
接口值之间可以使用
==和!＝来进行比较。两个接口值相等仅当它们都是nil值，或者它们的动态类型相同并且动态值也根据这个动态类型的==操作相等。如果两个接口值的动态类型相同，但是这个动态类型是不可比较的（比如切片），将它们进行比较就会失败并且panic。 -
接口值在与非接口值比较时，Go会先将非接口值尝试转换为接口值，再比较。
-
接口值很特别，其它类型要么是可比较类型（如基本类型和指针）要么是不可比较类型（如切片，映射类型，和函数），但是接口值视具体的类型和值，可能会报出潜在的panic。
分析
接口类型和 nil 作比较
接口值的零值是指动态类型和动态值都为 nil。当仅且当这两部分的值都为 nil 的情况下，这个接口值就才会被认为 接口值 == nil。
package main
import "fmt"
type Coder interface {
code()
}
type Gopher struct {
name string
}
func (g Gopher) code() {
fmt.Printf("%s is coding\n", g.name)
}
func main() {
var c Coder
fmt.Println(c == nil)
fmt.Printf("c: %T, %v\n", c, c)
var g *Gopher
fmt.Println(g == nil)
c = g
fmt.Println(c == nil)
fmt.Printf("c: %T, %v\n", c, c)
}
程序输出：
一开始，c 的 动态类型和动态值都为 nil，g 也为 nil，当把 g 赋值给 c 后，c 的动态类型变成了 *main.Gopher，仅管 c 的动态值仍为 nil，但是当 c 和 nil 作比较的时候，结果就是 false 了。
6. 什么类型可以作为map的key¶
在Go语言中，map的key可以是任何可以**比较**的类型。这包括所有的基本类型，如**整数、浮点数、字符串和布尔值，以及结构体和数组**，只要它们没有被定义为包含不可比较的类型（如切片、映射或函数）。
以下是一些可以作为map key的类型的例子：
- 整数类型
- 字符串类型
- 布尔类型
- 结构体类型（只要结构体的所有字段都是可比较的）
- 数组类型（数组的元素类型必须是可比较的）
go
m := make(map[[2]int]string)
m[[2]int{1, 2}] = "1,2"
注意，切片、映射和函数类型是不可比较的，因此不能作为map的key。如果你需要一个包含这些类型的key，你可以考虑使用一个指向这些类型的指针，或者将它们封装在一个可比较的结构体中，并确保结构体不包含任何不可比较的类型。
底层实现补充（节选）¶
slice¶
运行时 slice 为 { array, len, cap }。截取**子切片仍可能共享底层数组，修改重叠区间会彼此影响；**仅当 append 触发扩容时，新数组与旧数组分离。cap 从截取起点算到**原底层数组末尾**（在合法 cap 约束下），与“长度”不同，截取后可用容量常大于 len。
map¶
运行时核心为 hmap + bmap 桶数组；每个桶通常容纳 8 个槽位，含 tophash 等。**拉链**通过 overflow 桶链接。扩容与**渐进式迁移**时会出现 oldbuckets / nevacuate 等字段；遍历顺序**不保证**稳定。并发读写请用**互斥**或 sync.Map，不要依赖 map 自带线程安全。
string¶
字符串是**只读字节序列**（builtin 注释：8-bit bytes，惯例上**多为 UTF-8 文本）。运行时可用 stringStruct{ str, len } 理解：len 为**字节长度，非“字符数”。string 与 []byte 转换通常会**分配新内存**（或共享只读后备，依场景优化），修改内容请通过 []byte 再转回。