共计 6919 个字符,预计需要花费 18 分钟才能阅读完成。
前言
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
- 数据后果 – 容器(汇合)
- 数据结构:堆
- 数据结构 | 双向链表简略实现和图示