本文主要记录常用的一些数据结构。

源码实现

可以参考开源项目的代码,比如说linux和redis等。

数组

静态数组

大小固定的数组,适合存储固定大小的数据。

动态数组

可动态调整大小的数组,一般的实现在扩容时有复制旧数据的性能开销。
可以考虑使用deque替代(内部是多个数据块拼接)。

适合存储后进先出的数据。
可以用来模拟递归调用,避免栈溢出。
在深度优先搜索中也比较常用。

队列

FIFO队列

适合存储先进先出的数据。
在广度优先搜索中也比较常用。
具体实现参考STL的queue或linux的sys/queue.h文件。

优先级队列

按优先级出队,适合存储需要按优先级处理的数据。
一般是通过大堆实现。

双端队列deque

前端、后端皆可快速插入、删除的队列。
适合撤消历史(环形缓冲可能更适合)或者work-stealing场景使用1

链表

C语言中通用链表一般是通过void *或者像linux那样内嵌节点实现。
C++一般是通过泛型,具体参考STL容器即可。
可以使用冗余节点或双重指针简化插入、删除操作,快慢指针检查是否循环等。
配合哈希表使用,可以实现一些操作在O(1)的数据结构(比如说LRU, LFU)。

双向链表

可正向、反向遍历的链表,已经找到节点的情况下可快速删除、插入节点。

单向链表

只能正向遍历的链表,比双向链表节省空间。

循环链表

形成循环的链表,可以模拟环形缓冲。
STL的list内部通过循环链表实现。

跳跃表skiplist

随机化数据结构。多层链表,加快查找、插入、删除操作(复杂度为logN)。
相比平衡树,在内存占用、范围查找、实现难易等方面有优势。

哈希表

在冲突率不高时,查找、插入、删除可在常量时间完成。
哈希表的快速是靠空间换时间,会多耗一些内存。
在冲突率高时,需要扩容并重新哈希,建议采用类似redis那样的渐进式rehash。

多阶哈希表

通过多次哈希解决冲突、提高空间利用率的哈希表,可以通过一维数组模拟(可放入共享内存)。

Bloom Filter

快速判断元素是否在集合中。
比如说垃圾邮件过滤的场景或者辅助加速查询。
优点是速度快、省空间,缺点是有小概率误报、不能删除元素。

Cuckoo Filter

类似Bloom Filter,支持删除元素(不漏报)。

CQF

大小堆

适合存储1~N个极值的数据。
适合TopN类需求或者优先级队列、定时器的场景。
虽然大小堆是树结构,但是底层存储使用动态数组即可。

红黑树

平衡树变种,简化插入、删除后调整树的操作。
在红黑树的基础上可以实现set、map等容器。
具体可以参考linux的实现版本。

不相交集 / 并查集

不相交集是一种可以在接近常量的时间内查询和合并的数据结构。
可以参考boost的disjoint_sets或者《算法(第四版)》的实现。

trie树

前缀树,适合大量字符串检索、去重、前缀匹配、统计等场景。

赢家树,输家树

外部排序用到的数据结构,类似小堆可快速取出最小元素(速度快一点)。

B树系列

todo

哈夫曼编码树

位图bitmap

按位存储的数据结构,节省空间,适合存储类似标志位的数据。

环形缓冲

环形缓冲(ringbuffer)是单读单写可无锁的数据结构,一般通过数组模拟。
通过多个ringbuffer可以实现多对一的无锁通信。

双缓冲

空间换取并发安全的数据结构。
可以用来定时更新配置。
具体参考 DoubleBuffer 的说明。

todo

组合类型

LRU结构

LRU(Least Recently Used)底层可以通过哈希表+双向链表实现。
redis的实现是一种通过随机淘汰(K个)的近似LRU。

LFU结构

与LRU类似,通过双哈希表+双向链表+minFreq实现。
一个哈希表按key存储节点指针(迭代器),一个哈希表按freq存储双向链表(头部存最近访问节点)。

定时器

红黑树或最小堆

数量级在O(logN),比较容易想到的实现方式。
linux高精度(纳秒级)定时器hrtimer是基于红黑树实现的。

分级时间轮

具体参考 论文 的说明,插入、删除、更新都可以在常量时间内完成。
底层实现是环形缓冲(数组)+双向链表(或哈希链表),可以参考linux的实现(timer.c) 或者 这个
缺点是低精度(毫秒以上),级联操作时间不确定。
主要适合设置超时的场景,比如说网络、IO操作的超时。

参考链接


  1. https://en.wikipedia.org/wiki/Double-ended_queue#Applications ↩︎