哈希表

想要实现一个性能优异的哈希表，需要注意两个关键点 —— 哈希函数和冲突解决方法。

开放寻址法

开放寻址法2是一种在哈希表中解决哈希碰撞的方法，这种方法的核心思想是对数组中的元素依次探测和比较以判断目标键值对是否存在于哈希表中，如果我们使用开放寻址法来实现哈希表，那么在支撑哈希表的数据结构就是数组，不过因为数组的长度有限，存储 (author, draven) 这个键值对时会从如下的索引开始遍历：

index := hash("author") % array.len

当我们向当前哈希表写入新的数据时发生了冲突，就会将键值对写入到下一个不为空的位置：

开放寻址法中对性能影响最大的就是装载因子，它是数组中元素的数量与数组大小的比值，随着装载因子的增加，线性探测的平均用时就会逐渐增加，这会同时影响哈希表的读写性能

拉链法写入数据

当我们需要将一个键值对 (Key6, Value6) 写入哈希表时，键值对中的键 Key6 都会先经过一个哈希函数，哈希函数返回的哈希会帮助我们选择一个桶，和开放地址法一样，选择桶的方式就是直接对哈希返回的结果取模：

index := hash("Key6") % array.len

选择了 2 号桶之后就可以遍历当前桶中的链表了，在遍历链表的过程中会遇到以下两种情况：

找到键相同的键值对 —— 更新键对应的值；

没有找到键相同的键值对 —— 在链表的末尾追加新键值对；

拉链法实现的哈希也有装载因子这一概念：

装载因子 := 元素数量 / 桶数量

扩容

runtime.mapassign 函数会在以下两种情况发生时触发哈希的扩容：

装载因子已经超过 6.5；

哈希使用了太多溢出桶；

根据触发的条件不同扩容的方式分成两种，如果这次扩容是溢出的桶太多导致的，那么这次扩容就是等量扩容sameSizeGrow，sameSizeGrow 是一种特殊情况下发生的扩容，当我们持续向哈希中插入数据并将它们全部删除时，如果哈希表中的数据量没有超过阈值，就会不断积累溢出桶造成缓慢的内存泄漏4。runtime: limit the number of map overflow buckets 引入了 sameSizeGrow 通过重用已有的哈希扩容机制，一旦哈希中出现了过多的溢出桶，它就会创建新桶保存数据，垃圾回收会清理老的溢出桶并释放内存。

扩容的入口是 runtime.hashGrow 函数：

接口

在 Go 语言中如何定义接口。定义接口需要使用 interface 关键字，在接口中我们只能定义方法签名，不能包含成员变量

Go 语言中接口的实现都是隐式的，Go 语言实现接口的方式与 Java 完全不同：

在 Java 中：实现接口需要显式的声明接口并实现所有方法；

在 Go 中：实现接口的所有方法就隐式的实现了接口；

Go 语言只会在传递参数、返回参数以及变量赋值时才会对某个类型是否实现接口进行检查

func main() {
var rpcErr error = NewRPCError(400, "unknown err") // typecheck1
err := AsErr(rpcErr) // typecheck2
println(err) 
}
func NewRPCError(code int64, msg string) error {
return &RPCError{ // typecheck3
Code:    code,
Message: msg,
}
}
func AsErr(err error) error {
return err
}

Go 语言会编译期间对代码进行类型检查，上述代码总共触发了三次类型检查：

将 *RPCError 类型的变量赋值给 error 类型的变量 rpcErr；

将 *RPCError 类型的变量 rpcErr 传递给签名中参数类型为 error 的 AsErr 函数；

将 *RPCError 类型的变量从函数签名的返回值类型为 error 的 NewRPCError 函数中返回；

从类型检查的过程来看，编译器仅在需要时才对类型进行检查，类型实现接口时只需要实现接口中的全部方法，不需要像 Java 等编程语言中一样显式声明。

Go 语言中有两种略微不同的接口，一种是带有一组方法的接口，另一种是不带任何方法的 interface{}：

for range

数组和切片

循环永动机

如果我们在遍历数组的同时修改数组的元素，能否得到一个永远都不会停止的循环呢？你可以自己尝试运行下面的代码来得到结果：

func main() {
arr := []int{1, 2, 3}
for _, v := range arr {
arr = append(arr, v)
}
fmt.Println(arr)
}

$ go run main.go

1 2 3 1 2 3

上述代码的输出意味着循环只遍历了原始切片中的三个元素，我们在遍历切片时追加的元素不会增加循环的执行次数，所以循环最终还是停了下来。

range同时去遍历索引和元素也很常见。处理这种情况会使用下面这段的代码：

    tmp := nod(OINDEX, ha, hv1)
tmp.SetBounded(true)
a := nod(OAS2, nil, nil)
a.List.Set2(v1, v2)
a.Rlist.Set2(hv1, tmp)
body = []*Node{a}
}
n.Ninit.Append(init...)
n.Nbody.Prepend(body...)
return n

这段代码处理的就是遍历数组和切片时，同时关心索引和切片的情况。它不仅会在循环体中插入更新索引的语句，还会插入赋值操作让循环体内部的代码能够访问数组中的元素：

ha := a
hv1 := 0
hn := len(ha)
v1 := hv1
for ; hv1 < hn; hv1++ {
    tmp := ha[hv1]
    v1, v2 := hv1, tmp
    ...
}

对于所有的 range 循环，Go 语言都会在编译期将原切片或者数组赋值给一个新的变量 ha，在赋值的过程中就发生了拷贝，所以我们遍历的切片已经不是原始的切片变量了。

而遇到这种同时遍历索引和元素的 range 循环时，Go 语言会额外创建一个新的 v2 变量存储切片中的元素，循环中使用的这个变量 v2 会在每一次迭代被重新赋值而覆盖，在赋值时也发生了拷贝。

func main() {
arr := []int{1, 2, 3}
newArr := []*int{}
for i, _ := range arr {
newArr = append(newArr, &arr[i])
}
for _, v := range newArr {
fmt.Println(*v)
}
}

因为在循环中获取返回变量的地址都完全相同，所以会发生神奇的指针一节中的现象。所以如果我们想要访问数组中元素所在的地址，不应该直接获取 range 返回的变量地址 &v2，而应该使用 &a[index] 这种形式。

HashMap

遍历哈希表时会使用 runtime.mapiterinit 函数初始化遍历开始的元素：

func mapiterinit(t *maptype, h *hmap, it *hiter) {
it.t = t
it.h = h
it.B = h.B
it.buckets = h.buckets
r := uintptr(fastrand())
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))
it.bucket = it.startBucket
mapiternext(it)
}

该函数会初始化 hiter 结构体中的字段，并通过 runtime.fastrand 生成一个随机数帮助我们随机选择一个桶开始遍历。Go 团队在设计哈希表的遍历时就不想让使用者依赖固定的遍历顺序，所以引入了随机数保证遍历的随机性。

字符串

在遍历时会获取字符串中索引对应的字节并将字节转换成 rune。我们在遍历字符串时拿到的值都是 rune 类型的变量，for i, r := range s {} 的结构都会被转换成如下所示的形式：

ha := s
for hv1 := 0; hv1 < len(ha); {
    hv1t := hv1
    hv2 := rune(ha[hv1])
    if hv2 < utf8.RuneSelf {
        hv1++
    } else {
        hv2, hv1 = decoderune(h1, hv1)
    }
    v1, v2 = hv1t, hv2
}

在前面的字符串一节中我们曾经介绍过字符串是一个只读的字节数组切片，所以范围循环在编译期间生成的框架与切片非常类似，只是细节有一些不同。

使用下标访问字符串中的元素时得到的就是字节，但是这段代码会将当前的字节转换成 rune 类型。如果当前的 rune 是 ASCII 的，那么只会占用一个字节长度，每次循环体运行之后只需要将索引加一，但是如果当前 rune 占用了多个字节就会使用 runtime.decoderune 函数解码，

通道

使用 range 遍历 Channel 也是比较常见的做法，一个形如 for v := range ch {} 的语句

该循环会使用 <-ch 从管道中取出等待处理的值，这个操作会调用 runtime.chanrecv2 并阻塞当前的协程，当 runtime.chanrecv2 返回时会根据布尔值 hb 判断当前的值是否存在，如果不存在就意味着当前的管道已经被关闭了，如果存在就会为 v1 赋值并清除 hv1 变量中的数据，然后会重新陷入阻塞等待新数据。

select

当我们在 Go 语言中使用 select 控制结构时，会遇到两个有趣的现象：

select 能在 Channel 上进行非阻塞的收发操作；
select 在遇到多个 Channel 同时响应时会随机挑选 case 执行；

在通常情况下，select 语句会阻塞当前 Goroutine 并等待多个 Channel 中的一个达到可以收发的状态。但是如果 select 控制结构中包含 default 语句，那么这个 select 语句在执行时会遇到以下两种情况：

当存在可以收发的 Channel 时，直接处理该 Channel 对应的 case；

当不存在可以收发的 Channel 是，执行 default 中的语句；

随即执行

另一个使用 select 遇到的情况是同时有多个 case 就绪时，select 会选择那个 case 执行的问题，我们通过下面的代码可以简单了解一下

func main() {
ch := make(chan int)
go func() {
for range time.Tick(1 * time.Second) {
ch <- 0
}
}()
for {
select {
case <-ch:
println("case1")
case <-ch:
println("case2")
}
}
}

select 控制结构中的 case 却使用 runtime.scase 结构体来表示：

type scase struct {
c           *hchan
elem        unsafe.Pointer
kind        uint16
pc          uintptr
releasetime int64
}

因为非默认的 case 中都与 Channel 的发送和接收有关，所以 runtime.scase 结构体中也包含一个 runtime.hchan 类型的字段存储 case 中使用的 Channel；除此之外，elem 是接收或者发送数据的变量地址、kind 表示 runtime.scase 的种类，总共包含以下四种：

const (
caseNil = iota
caseRecv
caseSend
caseDefault
)

这四种常量分别表示不同类型的 case

空的 select 语句会直接阻塞当前的 Goroutine，导致 Goroutine 进入无法被唤醒的永久休眠状态。

在处理单操作 select 语句时，会根据 Channel 的收发情况生成不同的语句。当 case 中的 Channel 是空指针时，就会直接挂起当前 Goroutine 并永久休眠。

当 select 中仅包含两个 case，并且其中一个是 default 时，Go 语言的编译器就会认为这是一次非阻塞的收发操作

调度器

Go 语言调度器

G — 表示 Goroutine，它是一个待执行的任务；

M — 表示操作系统的线程，它由操作系统的调度器调度和管理；

P — 表示处理器，它可以被看做运行在线程上的本地调度器；

基于工作窃取的多线程调度器将每一个线程绑定到了独立的 CPU 上，这些线程会被不同处理器管理，不同的处理器通过工作窃取对任务进行再分配实现任务的平衡，也能提升调度器和 Go 语言程序的整体性能，今天所有的 Go 语言服务都受益于这一改动。

标记清除

标记清除

标记清除（Mark-Sweep）算法是最常见的垃圾收集算法，标记清除收集器是跟踪式垃圾收集器，其执行过程可以分成标记（Mark）和清除（Sweep）两个阶段：

标记阶段 — 从根对象出发查找并标记堆中所有存活的对象；

清除阶段 — 遍历堆中的全部对象，回收未被标记的垃圾对象并将回收的内存加入空闲链表；

三色标记算法将程序中的对象分成白色、黑色和灰色三类4：

白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；

黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；

灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

三色的对象

在垃圾收集器开始工作时，程序中不存在任何的黑色对象，垃圾收集的根对象会被标记成灰色，垃圾收集器只会从灰色对象集合中取出对象开始扫描，当灰色集合中不存在任何对象时，标记阶段就会结束

三色标记垃圾收集器的执行过程

三色标记垃圾收集器的工作原理很简单，我们可以将其归纳成以下几个步骤：

从灰色对象的集合中选择一个灰色对象并将其标记成黑色；

将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收；

重复上述两个步骤直到对象图中不存在灰色对象；

当三色的标记清除的标记阶段结束之后，应用程序的堆中就不存在任何的灰色对象，我们只能看到黑色的存活对象以及白色的垃圾对象，垃圾收集器可以回收这些白色的垃圾，下面是使用三色标记垃圾收集器执行标记后的堆内存，堆中只有对象 D 为待回收的垃圾：

并发收集器

并发（Concurrent）的垃圾收集不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响：

concurrent-collector

并发垃圾收集器

虽然并发收集器能够与用户程序一起运行，但是并不是所有阶段都可以与用户程序一起运行，部分阶段还是需要暂停用户程序的，不过与传统的算法相比，并发的垃圾收集可以将能够并发执行的工作尽量并发执行；当然，因为读写屏障的引入，并发的垃圾收集器也一定会带来额外开销，不仅会增加垃圾收集的总时间，还会影响用户程序，这是我们在设计垃圾收集策略时必须要注意的。

线程,进程,协程

1、进程

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。由于进程比较重量，占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大，但相对比较稳定安全。

2、线程

线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。线程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。

3、协程

协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

线程是操作系统调度时的最基本单元

多个线程可以属于同一个进程并共享内存空间。因为多线程不需要创建新的虚拟内存空间，所以它们也不需要内存管理单元处理上下文的切换，线程之间的通信也正是基于共享的内存进行的，与重量级的进程相比，线程显得比较轻量。

虽然线程比较轻量，但是在调度时也有比较大的额外开销。每个线程会都占用 1 兆以上的内存空间，在对线程进行切换时不止会消耗较多的内存，恢复寄存器中的内容还需要向操作系统申请或者销毁对应的资源，每一次线程上下文的切换都需要消耗 ~1us 左右的时间1，但是 Go 调度器对 Goroutine 的上下文切换约为 ~0.2us，减少了 80% 的额外开销2。

Go 语言的调度器通过使用与 CPU 数量相等的线程减少线程频繁切换的内存开销，同时在每一个线程上执行额外开销更低的 Goroutine 来降低操作系统和硬件的负载。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

程序员编程交流QQ群：805358732

如果你想用Python开辟副业赚钱，但不熟悉爬虫与反爬虫技术，没有接单途径，也缺乏兼职经验
关注下方微信公众号：Python编程学习圈，获取价值999元全套Python入门到进阶的学习资料以及教程，还有Python技术交流群一起交流学习哦。