JZTXT

【总结】盘点程序员必知必会的常见数据结构和算法

发布时间 2023-04-17 11:16:39作者: 琴水玉

引子

数据结构和算法的作用究竟是什么呢？有多重要？

假设你要运送 100 个苹果到码头，那么，你是用手一个一个把苹果拿过去呢 ？还是用几个箱子把苹果先放进去，再把箱子运送到码头呢？大概率你会选择后者吧。那么，数据结构就好比这几个箱子，可以容纳更多的数据，批量处理数据，算法就好比运送方法，使得数据处理的效率更高。互联网的价值即在于提升效率。

数据结构和算法是软件的基石。软件是由组件组合而成，而组件的底层基本就是数据结构和算法。在数据结构和算法的基础上通过设计的封装、扩展和组合实现更完善的组件功能。比如 Guava cache, 底层是哈希表（数组+链表或红黑树），通过加锁保证线程安全，通过过期策略来保证缓存功能，再加上一些监控统计的功能。

本文就来盘点下，程序员必知必会的常见数据结构和算法。部分高级数据结构和算法可能不需要自己写，甚至不一定会用到，但了解更多的数据结构和算法，对于求解问题和扩展见识来说，总是多多益善。

数据结构

物理存储结构

数组和链表展示了数据结构所依赖的两种基本的物理存储顺序，在物理存储结构的基础上可以构造各种逻辑存储结构。比如队列，既可以用数组来实现，也可以用链表来实现。

数组

长度固定，有限连续空间，元素邻近顺序放置。根据下标随机访问元素的效率高，但插入和删除的效率较低（因为需要移动大量元素）。数组是那种你很容易忽视它的存在却无处不在的基础数据结构（贴心小棉袄）。主要是因为它的结构和操作比较简单，线性的，符合人的心智模型。

可通过排序算法将数组变成有序数组。有序数组通过二分查找可以提供高效查找。 B+ 树实质是用指针将多个有序数组连接起来，基于二分查找。

数组应用： 实现位向量、字符串、可变列表、堆、工作队列、高级数据结构（比如哈希表）的底层支撑。

链表

长度不固定，非连续空间，元素不是邻近顺序放置，而是通过地址引用来确定元素的前后顺序。链表的插入和删除操作高效，但查询的效率不佳。

链表有单链表、双链表、跳表三种变体。链表算法题技巧：快指针与慢指针。链表是编程面试题的常考点。

链表应用：实现二叉树、红黑树、阻塞队列、条件队列、内存分配中的空闲块链表。在开发中直接使用场合不多，常见于库代码里。

逻辑数据结构

每一种逻辑数据结构，实际上定义的是操作接口及接口规格，而存储结构基于考虑数组、链表或者数组与链表的组合。

列表

开发中最常用的数据结构之一。顺序存储、通过索引随机访问，但长度可变。底层实现是基于数组，通过数组扩容来实现长度可变。数组扩容时需要大量拷贝工作，因此在设置列表时选择合适的长度。

列表应用：将数据库中的数据转换成对象列表来存储。

映射

开发中最常用的数据结构之一。由键和值组成对应关系的数据结构。底层是数组和链表（也可以是红黑树）的组合。

常用于将唯一标识与对象、对象与对象关联起来。

映射应用： 实现缓存、Session会话、并发计数器等。

集合

集合与列表类似，所不同的是集合中的元素是不重复的。集合常用来判断元素是否存在，可用于多重循环降重。

JSON

标量、列表和映射的任意嵌套的组合体。

应用：前后端、子系统之间的标准数据交换和数据通信。

栈

将元素先压入后弹出。后进先出。

常用于保存上下文语境，结合递归算法使用。

栈应用：实现深度优先遍历、回溯算法、方法调用、配对括号的语法检查、表达式转换。

队列

基本的队列操作是：元素从队列一端入，从队列另一端出。基于实际场景，队列有多种变体。有循环队列、双端队列、单调队列、优先级队列、阻塞队列。

  • 循环队列：当队列使用数组实现时，避免假溢出。可用于保证命令的按序执行。
  • 单调队列：两端删除，一端插入。队列元素保持单调性（递增或递减）。用于求解滑动窗口的最值问题。
  • 优先级队列：队首元素总是最大值或最小值。可使用堆实现。
  • 阻塞队列：用于“生产者-消费者”模式、消息通道。

单调队列和优先级队列的相同点是队首都是最值。不同点在于：单调队列的所有元素都保持有序性，但优先级队列的元素并不是完全有序的；单调队列每次取区间的最大值，因此可以丢弃元素，但优先级队列中的元素都是需要处理的，不可丢弃。

堆

结构特征：任何一个父节点的值均不小于其子节点的值。根节点是最大值。可以构造基于数组的完全二叉树来实现。

堆应用：优先级队列、前K最大（小）值。

表

一种由二维或多维数组构成的表格。可以通过索引或键来快速访问其中的元素。

表可以用来存储常用的数据和程序。缓存行即是表的一种运用。

表应用：关系数据库的数据存储、路由器的路由表、编译器的符号表、中断向量表。

位向量

由若干个位组成的长数组。节省空间。

位图应用： 不重复数组的排序、雪花算法、布隆过滤器。

二叉查找树

结构特征：左子树节点均小于根节点，右子树节点均大于根节点。

应用：快速查找、排序。由于其不平衡的最差效率，通常使用其变体红黑树。

SkipList

有序链表，空间换时间策略。通过在每个节点上新增多级索引指向后继节点，实现跳跃查找，平均 O(logN) ，最坏 O(N) 查找效率；批量顺序操作。

跳表应用：Redis 的有序集合键。

红黑树

二叉查找树的改进版。在最坏情形下，二叉查找树变成了线性链表，查询效率为 O(n)。

对二叉查找树进行扩展，可以得到 2-3 树，这种树在插入新的元素后自下而上生长，始终可以保持平衡性。但 2-3 树需要维护两种不同节点和多种操作情况，因此演变成红黑树。红黑树是特殊的二叉查找树，其红链接表示 3-节点，黑链接表示普通的 2-节点。

红黑树应用：哈希表、排序树；Select-Epoll 机制中的监听文件描述符的就绪事件列表；CFS 的公平任务调度。

B+树

多级有序数组的链表。每个节点都有多个元素，这些元素在同一层级都是有序的，不同层级的节点遵循二叉查找树的特性。

B+树应用：数据库索引。

布隆过滤器

一个很长的二进制向量和一系列哈希函数。主要用于判断一个元素是否在一个集合中。可以检查值是 “可能在集合中” 还是 “绝对不在集合中”。

使用多个哈希函数将一个值映射成多个哈希值，并投影到二进制向量上，并置为 1。如果指定 key 通过哈希函数映射到位图上，有一个位为 0， 则一定不存在这个 key 。

布隆过滤器应用：网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断、缓存穿透。

倒排索引

键值结构。以关键字为键，以关键字所在文档及位置为值。

  • 关键词分割
  • 关键词所在的文档及位置的存储
  • 词典索引构建与优化。

基本思想： 倒排索引 + 前缀树 + FST + 压缩数字列表

倒排索引应用： 文本检索。

DAG

DAG（Directed Acyclic Graph），有向无环图。有拓扑排序、最小路径算法。

DAG应用： 对象依赖图（GC算法）、组件依赖图和执行顺序（微服务治理）、多对象多模式匹配（RETE算法）、项目甘特图、区块链、Git分布式版本控制。

前缀树

又称单词查找树或键树。通过较少的空间存储大量字符串（节点只存储单个字符，复用了存储空间），节省空间，提升字符串查找效率。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

前缀树应用：自动补全、拼写检查、字符串排序、前缀查找。

算法

算法策略

分治

没有分治解决不了的问题。如果有，那说明分解的还不够细。

分治是应对复杂问题的最基本最有效的策略。从水平分，可以把大数据集分解为多个子数据集分别处理再汇总；从垂直分，可以把一个复杂任务分解为多个相对容易的子任务分别求解再综合。

归并排序就是典型的分治求解。先将一个集合分成两个集合（可以按照不同方式切分，比如前后、奇偶），对两个集合分别排序，然后再将两个集合的排序结果做一个合并处理，即得到原集合的排序结果。

递归

递归是非常重要的一种程序化求解思维。

如果一个问题涉及多个子问题，而子问题和原问题可以使用相同的方法处理，就可以适用于递归思维。

举个简单的例子。 1+2+3+4+5 = 1+（2+3+4+5）= 1+ （2 + （3+4+5）） = 1+（2+（3+（4+5））） = 1+（2+（3+（4+（5））））。 1-5 的和等于 1-4 的和加上 5。

当整体结构与子结构具有相似性时，很适合用递归求解。比如二叉查找树的查询。当然，递归的效率较低，可转换为非递归的求解。

减治

减治是分治与递归结合的一种方法。假设要处理一个集合，且处理这个集合的子集与处理原集合的方法相同，则可以从这个集合拿掉若干个元素，然后先递归处理子集合，然后再将子集合的解与拿到元素进行合并处理得到原集合的解。

动态规划

先运用分治策略，将原问题分解成多个子问题，分别求解子问题然后综合。

关键在于，在求解过程中要将子问题的计算结果缓存起来复用，从而使得时间复杂度降低一个量级。要学会划分可复用的子问题，并理清楚子问题与原问题之间的关联。

空间换时间

由于时间非常宝贵，而存储空间较为廉价，往往会采用空间换时间的策略。

预处理

通过预排序、预索引、拓扑结构等预处理将原数据集构造特定的数据结构，以高效支持后续的查找或操作，比如 KMP, RETE ，倒排索引，都运用了这种策略。预处理实际上是空间换时间策略的运用。

算法评价与选用

时间复杂度和空间复杂度。在空间存储充足的情况下，通常考虑时间复杂度。

当然，在移动端以及大数据存储方面，空间复杂度也需要仔细考虑。


具体算法

查找

  • 主要有：有序查找、哈希查找。
  • 有序查找：构建有序数据结构，比如有序数组、跳表、二叉查找树、红黑树，B+ 树，从而使用二分查找来提升查找效率，减少比较次数，查找时间复杂度 O(logn) 。变体有插值查找、斐波那契查找。
  • 哈希查找：构建哈希 key-value 映射结构，解决哈希冲突，查找时间复杂度 O(1) 。哈希查找需要仔细选择哈希函数（通过参数调优来提升性能），不支持 rank 和 select 操作（第 K 大元素），通常用于 K-V 结构的存储系统； 顺序查找的查找效率与哈希接近，支持 rank 和 select 操作，通常用于有序表、关系型数据库等。可以结合两种查找结构使用。比如 java8 的 HashMap 是哈希查找与顺序查找的结合。
  • 动态查找：一致性哈希。环状队列 + 多哈希 + 虚拟节点。构建一个 serverMap = TreeMap[VirtualNodeHash, Server] 的有序映射。对数据进行哈希 h 后，在 serverMap 找到第一个不小于 h 的键 S，将该数据分布到服务器 serverMap[S] 上。
  • 哈希算法：可采用 Fowler-Noll-Vo 哈希算法。一致性哈希的性质：平衡性、单调性、分散性、负载、平滑性。
  • 全文检索： 倒排索引。
  • 查找的可扩展性： 分表、分库、分片、分区。

排序

常用排序算法：

  • 快速排序：时间复杂度O(nlogn)，空间复杂度O(nlogn)，不稳定排序；适合随机的大数据集。
  • 归并排序：时间复杂度O(nlogn)，空间复杂度O(1)，稳定排序；适合随机的大数据集。
  • 堆排序，时间复杂度 O(nlogn) ，空间复杂度O(1)，不稳定排序；适合随机的大数据集。
  • 多关键字排序：MSD 和 LSD。 MSD 是先按高位排序分组，把高位相同的放在一组；然后按照次高位再做排序分组。LSD是先从最低位开始排序，再对次低位进行排序，依次重复，直到对所有关键字排序后便得到一个有序序列。采用链表减少存储空间。
  • 基数排序：将整数位切分为多个数位，然后按照多关键字排序。
  • 桶排序： 分治 + 其它排序。把数据映射到某个桶里，针对每个桶单独排序，然后合并。适合均匀分布的数据。桶的数量和映射函数要仔细设计，保证在桶内均匀分布且基本有序。
  • 文件排序：适合有限内存或针对磁盘文件排序。基于归并排序，先划分为多个子文件，针对每个子文件排序并将有序分段写入外部存储器，再对子文件进行归并。
  • 简单插入排序、选择排序、冒泡排序：时间复杂度 O(n*n)，空间复杂度 O(1)，实现简单，适合于数据量小的场景。插入排序适合数据基本有序的情况。

选择排序算法的依据：数据量大小；是否需要稳定排序；数据是否基本有序或者完全随机；数据的分布；内存是否有限或者有运行时间限制。

遍历

  • 数组：按索引遍历。
  • 链表：按节点指针遍历。
  • 映射：按照映射里的 key 进行遍历。
  • 二叉树：前序遍历、中序遍历、后序遍历。
  • 图：深度优先遍历、广度优先遍历。

字符串匹配

  • 朴素字符串匹配 - 双重循环，简单，低频场景；
  • 有限自动机 - 根据模式字符串构造有限自动机，再匹配文本，适用模式串的不同字符数很少的情形；
  • KMP - 根据模式字符串及构造后缀匹配数组（PMT，Partial Match Table，前缀集合与后缀集合的交集字符串的最长长度），避免无用位移测试，适用生产环境。

压缩

  • RLE、增量编码、哈夫曼编码、Rice编码、LZ77编码、位表示、Trie前缀树;
  • snappy, gzip, lz4;
  • 图像视频压缩（MLP、CNN、GAN）。

生成全局唯一ID

全局唯一ID 的要求：全局唯一不重复；单调递增；信息安全；ID生成系统高可用；分配支持；长度适宜。

  • UUID 生成
  • 数据库自增ID
  • Redis INCR 命令
  • snowflake 算法，生成 64 bit 的 long 型数值作为唯一ID。41bit (毫秒数) + 10 bit (5bit 数据中心 + 5bit 机器号) + 12bit (毫秒内的偏移量) + 1bit (=0)

号段模式：每次申请和取出若干个 ID 进行分配，分配完后再去批量申请新的 ID。

负载均衡选择

  • （加权）轮询：服务端配置高的权重更高。
  • 最少连接数：根据服务端当前的连接数动态选择连接数最少负载最小的服务器。
  • （加权）随机选择：不常使用。

位操作技巧

一般用于求哈希值、模运算、高效计算（比如 m mod 2^n == m & (n-1) ）、状态位设置、节省空间等。

哈希计算

主要基于整数或二进制位来计算。如果是浮点、字符串、IP地址、对象，先将其转换成整数型，再进行计算。最好能用到 key 里面所有相异的部分。常见的哈希函数有取模（模最好是素数）、MurmurHash2 算法（源码可以在 GitHub 上搜到）。可以编写一个程序，来检测哈希值的分布均匀度。如果哈希计算代价比较昂贵，需要做哈希值缓存。

利用ChatGPT扩展知识

【提问】list all the data structures so far

Here are some common data structures:
Array: A collection of elements, each identified by an index or a key.
Linked List: A collection of elements, each containing a reference to the next element in the list.
Stack: A collection of elements with last-in, first-out (LIFO) access.
Queue: A collection of elements with first-in, first-out (FIFO) access.
Hash Table: A data structure that maps keys to values using a hash function to compute an index into an array of buckets.
Set: A collection of unique elements.
Tree: A hierarchical data structure composed of nodes, with each node having zero or more child nodes.
Graph: A collection of vertices and edges that connect them.
Heap: A binary tree-based data structure that maintains its elements in a specific order.
Trie: A tree-like data structure used to store a dynamic set of strings.
Bloom Filter: A probabilistic data structure used to test if an element is a member of a set.
Bit Array: A compact data structure consisting of a fixed-size array of bits.
Bloomier Filter: A hybrid data structure combining the features of a hash table and a Bloom filter.
Skip List: A probabilistic data structure used for efficient searching, insertion, and deletion operations.
Red-Black Tree: A self-balancing binary search tree that guarantees logarithmic time complexity for insertions, deletions, and lookups.
B-Tree: A self-balancing data structure designed for storing large amounts of data on disk.
Note that this is not an exhaustive list and there are many other data structures used in computer science and programming.

【提问】list the data structures not in above list

Here are some additional data structures that were not mentioned in the previous list:
Bloom Trie: A combination of a trie and a Bloom filter, used to store a large number of keys while minimizing memory usage.
Fenwick Tree (also known as Binary Indexed Tree): A data structure used to efficiently calculate prefix sums of an array of numbers.
Segment Tree: A tree-based data structure used to efficiently perform range queries over an array of elements.
Bucket Sort: A sorting algorithm that uses buckets to distribute elements into groups based on their values, and then sorts each bucket individually.
Radix Tree (also known as Trie or Prefix Tree): A tree-like data structure used for efficient searching and retrieval of strings.
Patricia Trie: A space-optimized version of a radix tree, where nodes with only one child are compressed into a single node.
Rope: A data structure used to efficiently store and manipulate large strings by breaking them down into smaller pieces.
Bloom Set: A probabilistic data structure used to test if an element is a member of a set, similar to a Bloom filter but with more flexible deletion capabilities.
Suffix Array: An array of all suffixes of a given string, used for efficient substring search and pattern matching.
Van Emde Boas Tree: A data structure used to implement a priority queue with logarithmic time complexity for insertions, deletions, and lookups.
Note that this is still not an exhaustive list, as there are many other data structures used in computer science and programming.

可以一直提问 list the data structures not in above list。

小结

数据结构和算法，是软件组件的基本组成结构，是解决很多疑难编程问题的强有力的法宝，也是程序员装备自身编程技能的一件利器。

参考资料