前言

Java 内置了丰富的容器类，不同容器用于处理各种业务场景。 Go 虽然语言设计上和 Java 有很多相似的地方， 但原生并没有支持太多容器类的数据结构，只有 map 和 slice。标准库的 container package 对容器数据结构做了扩展，支持堆（Heap）、链表（LinkedList） 和循环链表（Circular List）3个容器。

容器

熟悉 C++ 和 Java 对容器应该都有清晰的了解， 它是现代编程实践中不可或缺的一部分，具有多种形式， 一般被描述为具有操作容器内容的方法的对象。Go 提供的基本容器主要有6个：

  • 内置容器：
    • map: 关联容器
    • slice： 动态扩容的顺序容器
  • channels：队列
  • container标准库（pkg/container）:
    • list：链表容器
    • ring：循环链表容器
    • heap： 堆容器，提供 heap 的实现

slice 、map 和 channel 是 Go 最常见、也是内置的容器数据结构，其他容器都在标准库的 container 包下。在使用 container 三个容器的时候，不必再费心实现数据结构相关的算法。同时，因为container 提供的容器支持的入参类型都是 interface{}， 所以只要实现了容器的 interface, 就可以处理任何类型的值。

container/list

链表容器 list 的代码是一个双向链表的实现。list 维护两个结构体：Element 和 List：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value interface{}
}

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}

linkedList

当通过 list.New() 创建一个 list 时，会初始化一个 Element 作为 Root Pointer，它要么指向列表的初始元素，要么为 nil。每一个 Element 除了数据字段Value外,还有 prev 和 next 分别指向 直接前驱 和 直接后继， 来允许用户在 list 中前后移动元素。

list 容器支持的方法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

type Element
    func (e *Element) Next() *Element
    func (e *Element) Prev() *Element
type List
    func New() *List
    func (l *List) Back() *Element   // 最后一个元素
    func (l *List) Front() *Element  // 第一个元素
    func (l *List) Init() *List  // 链表初始化
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素后插入
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在某个元素前插入
    func (l *List) Len() int // 在链表长度
    func (l *List) MoveAfter(e, mark *Element)  // 把 e 元素移动到 mark 之后
    func (l *List) MoveBefore(e, mark *Element)  // 把 e 元素移动到 mark 之前
    func (l *List) MoveToBack(e *Element) // 把 e 元素移动到队列最后
    func (l *List) MoveToFront(e *Element) // 把 e 元素移动到队列最头部
    func (l *List) PushBack(v interface{}) *Element  // 在队列最后插入元素
    func (l *List) PushBackList(other *List)  // 在队列最后插入接上新队列
    func (l *List) PushFront(v interface{}) *Element  // 在队列头部插入元素
    func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列
    func (l *List) Remove(e *Element) interface{} // 删除某个元素

下面是 list 的一个简单例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

package main

import (
	"container/list"
	"fmt"
)

func main() {
	// Create a new list and put some numbers in it.
	l := list.New()
	e4 := l.PushBack(4)
	e1 := l.PushFront(1)
	l.InsertBefore(3, e4)
	l.InsertAfter(2, e1)

	// Iterate through list and print its contents.
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf(".2d",e.Value)
	}

}

这段代码的输出是： 1234。在初始化 list 后，在尾结点插入4，在头结点插入1；再在4前插入3，在1后插入2，所以结果是1234。

list 在插入、删除数据的时间复杂度在 $O(1)$； 随机查找效率较低，为 $O(N)$ （slice 随机查找的时间效率为 $O(1)$）

链表容器常见的应用场景是用于做 LRU 缓存。

container/ring

循环链表容器 ring 是一个没有头节点和尾节点的链表，这里可以看成是一个简化版的 list。ring 维护一个结构体 Ring:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
	next, prev *Ring
	Value      interface{} // for use by client; untouched by this library
}

ring

但跟 list 不同的是 ring 的方法是不一样的：

1
2
3
4
5
6
7
8
9

type Ring
    func New(n int) *Ring  // 初始化环
    func (r *Ring) Do(f func(interface{}))  // 循环环进行操作
    func (r *Ring) Len() int // 环长度
    func (r *Ring) Link(s *Ring) *Ring // 连接两个环
    func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前（n 可以为负数）
    func (r *Ring) Next() *Ring // 当前元素的下个元素
    func (r *Ring) Prev() *Ring // 当前元素的上个元素
    func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除 n 个元素

下面是 ring 的一个简单例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

package main

import (
	"container/ring"
	"fmt"
)

func main() {

	// Create a new ring of size 5
	r := ring.New(5)

	// Get the length of the ring
	n := r.Len()

	// Initialize the ring with some integer values
	for i := 0; i < n; i++ {
		r.Value = i
		r = r.Next()
	}

	// Iterate through the ring and print its contents
	r.Do(func(p interface{}) {
		fmt.Printf("%d", p.(int))
	})

}

这段代码的输出是01234。 在初始化 ring 后， 对每个元素的 Value 赋值， 因为 ring 提供 Do 方法，所以遍历到当前元素的是时候，执行 Print 函数打印结果。

从 ring 的实现上可以知道相关操作的时间复杂度在$O(N)$。因为 ring 节点没有头尾区分和 FIFO 的特性，所以一个能用到的应用场景是环形缓冲区：在不消费资源的情况下提供对缓冲区的互斥访问 。

container/heap

堆（Heap）就是用数组实现的完全二叉树。根据堆的特性可以分为两种：最大堆和最小堆，两者的区别在于节点的排序方式上：

  1. 在最大堆中，父节点的值比每一个子节点的值都要大，堆最大元素在 root 节点
  2. 在最小堆中，父节点的值比每一个子节点的值都要小， 堆最小元素在 root 节点

Go 的堆容器 heap 在实现上是一个最小堆，heap 维护一个 Interface 接口：

1
2
3
4
5
6
7
8

// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

除了 出堆方法Push()和 入堆方法push()， Interface 内联了 sort.Interface, 它实现了三个方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)

min-heap

只要实现了 Interface 方法的数据类型， 就满足构建最小堆条件：

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

通过 heap.Init() 函数构建一个最小堆（按先序遍历排序的 slice），内部实现的 up() 和 down() 分别来对 堆来进行 上调整 和 下调整。

  • Push()：当往堆中插入一个元素的时候，这个元素插入到最右子树的最后一个节点中，然后调用up() 向上保证最小堆。
  • Pop()：当要从堆中推出一个元素的时候，先把这个元素和右子树最后一个节点交换，然后弹出最后一个节点，然后对 root 调用 down()，向下保证最小堆。

heap 容器支持的方法如下：

1
2
3
4
5

func Fix(h Interface, i int) // 在 i 位置更新数据，重建最小堆
func Init(h Interface) // 初始化，把 h 构建成最小堆 
func Pop(h Interface) interface{} // 出堆操作
func Push(h Interface, x interface{}) // 入堆操作
func Remove(h Interface, i int) interface{} // 移除第 i 个元素

下面是使用 heap 容器的一个例子， 构建一个优先级队列 pq：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

package main

import (
	"container/heap"
	"fmt"
)

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority > pq[j].priority }

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

func main() {
	items := map[string]int{
		"banana": 3,
		"apple":  2,
		"pear":   4,
	}

	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)

	// insert a new item
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	heap.Push(&pq, item)
	pq.update(item, item.value, 5)

	fmt.Printf("\nheap length: %d\n", len(pq))
	for pq.Len() > 0 {
		i := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s\t", i.priority, i.value)
	}
	fmt.Printf("\nheap length: %d\n", len(pq))
}

这段代码的输出是05:orange 04:pear 03:banana 02:apple。 首先是定义一个 PriorityQueue的结构体数组作为队列，有个 priority字段标识优先级，在 Less() 方法里比较两个元素的优先级，队列 update()用于更新元素的优先级。然后每次在执行 heap.Pop(&pq).(*Item)操作，会把最大堆里高priority元素出堆。

heap 在初始化的时候，时间复杂度在 $O(N)$；入堆、出堆、移动元素和重建最小堆的时间复杂度都是 $O(logN)$

堆容器在实际应用上是比较常见的， 在生产上经常用于实现优先级队列 和 高性能定时器。

小结

本文主要梳理了 Go 的 容器数据结构，分析标准库里 container包实现的三个容器：list、ring 还有较复杂的 heap， 介绍它们的实现、特性和使用场景。虽然 slice 和 map 作为在 Go 中是经常被使用到的容器，但如果在实际开发中发现这两个数据结构并不满足我们的需求，可以在 pkg/container 下搜索是否有可用到的数据结构。

参考