前言
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:
// 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 }
当通过 list.New() 创建一个 list 时,会初始化一个 Element 作为 Root Pointer,它要么指向列表的初始元素,要么为 nil。每一个 Element 除了数据字段Value外,还有 prev 和 next 分别指向 直接前驱 和 直接后继, 来允许用户在 list 中前后移动元素。
list 容器支持的方法如下:
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 的一个简单例子:
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:
// 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 }
但跟 list 不同的是 ring 的方法是不一样的:
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 的一个简单例子:
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)就是用数组实现的完全二叉树。根据堆的特性可以分为两种:最大堆和最小堆,两者的区别在于节点的排序方式上:
- 在最大堆中,父节点的值比每一个子节点的值都要大,堆最大元素在 root 节点
- 在最小堆中,父节点的值比每一个子节点的值都要小, 堆最小元素在 root 节点
Go 的堆容器 heap 在实现上是一个最小堆,heap 维护一个 Interface 接口:
// 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, 它实现了三个方法:
// 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)
只要实现了 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 容器支持的方法如下:
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:
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 下搜索是否有可用到的数据结构。
参考
- container pkg
- Go Containers Explained In Color
- container — 容器数据类型:heap、list 和 ring
- Go Containers
- 堆 heap
- 数据结果--容器(集合)
- 数据结构:堆
- 数据结构|双向链表简单实现和图示
有疑问加站长微信联系(非本文作者)