003.Go标准库中的容器

参考：Go标准库容器介绍：list（双向链表）、heap（堆）、ring（圈）（作者：jxwu）

---

• slice（切片）
• map（字典、映射，go 中没有单独的 set 结构，用 map[key]interface{} 即可）
• list（双向链表）
• heap（堆）
• ring（圈）

双向链表 §

container/list 包下

Go 的双向链表主要包含两个数据结构：

// 链表的一个元素
type Element struct {
   next, prev *Element // 前后指针
   list *List          // 所属链表
   Value any           // 值
}
 
func (e *Element) Prev() *Element
func (e *Element) Next() *Element

// 链表
type List struct {
   root Element // 哨兵元素
   len  int     // 链表元素个数
}

哨兵的加入可以让各种操作变得简单一致

初始化 §

List 支持延迟初始化，因此不管使用 list.New() 创建一个已经初始化的 List，或者直接使 list.List{} 创建一个未初始化的 List，都可以正常运行

在调用 PushFront()、PushBack()、PushFrontList()、PushBackList() 时会调用 lazyInit() 检查是否已经初始化，如果没有初始化则调用 Init() 进行初始化

package main
 
import (
  "container/list"
  "fmt"
)
 
func main() {
  // 使用 list.New() 直接初始化
  l1 := list.New()
  l1.PushFront(1)
  fmt.Println(l1.Front().Value) // 1
 
  // 使用 list.List{} 延迟初始化
  l2 := list.List{}
  l2.PushFront(2)
  fmt.Println(l2.Front().Value) // 2
 
  // 使用 list.List{} 延迟初始化
  var l3 list.List
  l3.PushFront(3)
  fmt.Println(l3.Front().Value) // 3
}

添加元素 §

PushFront(v any) *Element、PushBack(v any) *Element 分别是在链表头部或尾部添加元素，PushFrontList(other *List)、PushBackList(other *List) 分别是在链表头部或在尾部插入链表

InsertBefore(v any, mark *Element) *Element、InsertAfter(v any, mark *Element) *Element 分别是在某个元素前插入，在某个元素后插入

获取元素及长度 §

Front() *Element、Back() *Element、Len() int 分别是获取头元素、获取尾元素、获取长度，都不会对链表修改

移动元素 §

MoveBefore(e, mark *Element)、MoveAfter(e, mark *Element)、MoveToFront(e *Element)、MoveToBack(e *Element) 分别是移动元素到某个元素前面、移动元素到某个元素后面、移动元素到头部、移动元素到尾部

移除元素 §

Remove(e *Element) any

应用 §

双端队列 §

双端队列

栈/队列 §

栈与队列

LRU 缓存 §

LRU 缓存

堆 §

Go标准库中的堆

应用 §

优先队列 §

圈 §

container/ring 包下

Ring 是一个在循环链表里面的元素，它没有头尾

type Ring struct {
   next, prev *Ring // 前后指针
   Value      any   // 值，使用者自己设置
}

空 Ring 必须是一个 nil

零值 Ring 是一个元素的 Ring

创建 Ring §

直接创建 §

可以直接创建圈，只指定需要存储的值，不需要管前后指针的初始化，因为 Ring 的方法都会在执行前检查 Ring 是否初始化，如果没有初始化则先进行初始化

package main
 
import (
   "container/ring"
   "fmt"
)
 
func main() {
   // 创建两个圈
   r1 := ring.Ring{Value: 1}
   r2 := ring.Ring{Value: 2}
   // 链接两个单圈
   r1.Link(&r2)
   // 遍历整个圈
   r1.Do(func(a any) {
      fmt.Println(a) 
   })
   // 1
   // 2
}

使用 New() §

也可以使用 New(n int) *Ring 创建圈，New() 的参数是指定要创建圈元素的个数，而且使用 New() 前后指针是已经初始化好的

package main
 
import (
   "container/ring"
   "fmt"
)
 
func main() {
   r1 := ring.New(1) // 创建一个元素的圈
   r2 := ring.New(2) // 创建两个元素的圈
   r1.Value = 1
   r2.Value = 2
   // 链接两个单圈
   r1.Link(r2)
   // 遍历整个圈
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   // 1
   // 2
   // <nil>
}

连接与取消连接 §

Link(s *Ring) *Ring 很好理解，就是拼接两个圈；Unlink(n int) *Ring 就是与当前节点后面的第 n + 1 个节点进行链接，这样中间的 n 个节点就被 unlink 了

package main
 
import (
   "container/ring"
   "fmt"
)
 
func main() {
   r1 := ring.New(1) // 创建一个元素的圈
   r2 := ring.New(1) // 创建一个元素的圈
   r3 := ring.New(1) // 创建一个元素的圈
   r1.Value = 1
   r2.Value = 2
   r3.Value = 3
   r1.Link(r2) // 链接两个单圈
   r2.Link(r3) // 链接两个单圈
   // 遍历整个圈
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   // 1
   // 2
   // 3
 
   // unlink掉后面1个节点
   r1.Unlink(1)
   // 遍历整个圈
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   // 1
   // 3
}

移动 §

Prev() *Ring、Next() *Ring 分别是前一个节点、后一个节点

Move(n int) *Ring：向后 (n < 0) 或向前 (n >= 0) 移动 n % r.Len() 个元素，并返回该环元素

• Move(1) == Next()
• Move(-1) == Prev()

Len() int、Do(f func(any)) §

分别是圈元素个数和堆圈中每个元素执行操作

应用 §

环形缓冲器（Ring Buffer） §

一种生产者消费者模式的结构，而且如果只有一个读线程、一个写线程，二者没有共享的被修改的控制变量，那么可以证明这种情况下不需要并发控制

一致性 Hash §

一致性哈希算法是一种特殊的哈希算法，目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题