数据结构与算法
2023-08-23 15:05:10 2 举报AI智能生成
数据结构与算法
作者其他创作
大纲/内容
哈希表（Hash Table）
存储特点
散列函数
无限的输入值域，集中均匀的输出值域
相同的输入有相同的输出
不同的输入有不同或相同（哈希冲突）的输出
设计原则
合理的混合函数
使用素数
使用位操作
考虑输入的所有部分
使用加密技术
避免冲突
使用随机化
哈希冲突
开放地址法
线性探测法
再哈希法
链地址法
布隆过滤器（Bloom Filter）
基本组成
处理流程
构造
判断值是否存在
散列函数
处理误判
算法实现
布谷鸟过滤器（Cuckoo Filter）
处理流程
构造
判断值是否存在
子主题
应用实例
算法实现
一致性哈希（Consistent Hashing）
处理流程
构造
选取节点
添加节点
删除节点
虚拟节点
算法实现
应用场景
哈希索引
追加写入
偏移量
分段压缩
文件格式
删除记录
崩溃恢复
部分写入
并发控制
局限性
哈希表必须全部放入内存
区间访问效率不高
找出出现次数最多的元素
找出重复的元素
淘汰算法
最近最少使用（LRU）
算法实现
最不经常使用（LFU）
算法实现
线性表（Linear List）
数组（Array）
使用须知
避免越界
使用容器
使用哨兵
访问效率
链表（Linked List）
访问效率
应用场景
栈（Stack）
实现方式
访问效率
应用场景
队列（Queue）
算法实现
访问效率
应用场景
跳表（Skip List）
构造
查找
插入和删除
保持平衡
算法实现
访问、存储效率
应用实例
堆（Heap）
访问效率
大顶堆/小顶堆（Max/Min Heap）
算法实现
优先级队列（Priority Queue）
算法实现
斐波那契堆（Fibonacci Heap）
二项堆（Binomial Heap）
索引堆（Index Heap）
应用场景
找出出现次数最多的 N 个元素
位图（Bit Map）
应用场景
找出指定范围内未出现的元素
找出指定范围内任意一个未出现的元素
找出出现 2 次的元素
树（Tree）
二叉树（Binary Tree）
二叉搜索树（Binary Search Tree）
平衡二叉搜索树（AVL）
红黑树（Red-Black Tree）
存储特点
基本操作
插入节点
删除节点
初步调整
二次调整
应用场景
伸展树（Splay Tree）
树堆（Treap）
哈夫曼树（Huffman Tree）
构造
应用实例
线段树（Segment Tree）
存储特点
多叉树（Multi-Branch Tree）
字典树（Trie）
基本操作
内存消耗
缩点优化
存储节点
应用场景
实现
AC 自动机（AC Automaton）
构造
Trie 树
失败指针
应用实例
树状数组（Binary Indexed Tree）
区间查询
单点修改
并查集（Union Find）
基本操作
查询
合并
添加
算法实现
B 树 / B+ 树
B+ 树
与红黑树比较
支持范围访问
二级索引
在索引中存储值
堆文件
聚簇索引
多列索引
级联索引
全文搜索和模糊索引
分页设计
B* 树
基本操作
查找
更新
插入
分裂
合并
平衡
可靠性
预写日志
并发控制
性能优化
写时复制
键略缩信息
相邻布局
添加额外指针
分形树
优势与劣势
读取较快
写入较慢
并发控制
LSM 树（Log-Structured-Merge-Tree）
SSTables
压缩段
查找键
处理流程
处理写请求
处理读请求
合并和压缩
崩溃恢复
WAL
性能优化
布隆过滤器
压缩合并策略
优势与劣势
写放大
写入较快
读取较慢
更好的压缩
写入带宽开销
应用实例
Cassandra、HBase
Elasticsearch、Solr
图（Graph）
基本概念
存储结构
邻接矩阵
邻接表
边
路径
平行边
自环边
环
有/无环图
桥（Bridge）
简单图
连通图
连通分量
生成树/森林
顶点
相连/相连
度
入度（Indegree）/出度（Outdegree）
稀疏图/稠密图/完全图
割点（Articulation Points）
切分
二分图
同构图
完全图
有向图/无向图（Directed/Undirected）
有权图/无权图（Weighted/Unweighted）
有向/无向图完全通用
无权图
广度优先遍历（BFS）
无权最短路径
状态转换
遍历树
深度优先遍历（DFS）
哈密尔顿回路与路径（Hamilton Loop and Path）
回溯（Backtracking）
状态压缩（State Compress）
记忆化搜索（Memory Search）
有权图
最短路径（Shortest Path）
Dijkstra 算法
Moore-Bellman-Ford 算法
SPFA 算法
Floyd 算法（所有点对）
有向/无向图通用且有差别
无权图
欧拉回路与路径（Euler Loop and Path）
回溯（Backtracking）
Fleury 算法
Hierholzer 算法
环（Cycle）检测
当前路径记录
拓扑排序（Topological Sorting）
深度优先遍历（后序的逆序）
有权图
网络流模型（Network Flow）
最大流（Max Flow）
Ford-Fulkerson 思想
Edmonds-Karp 算法
Dinic 算法
MPM 算法
最小割（Min Cut）
Push-relabel 算法
无向图
无权图
寻找桥（边）与割点
遍历树
泛洪填充（Flood Fill）
二分图（Bipartite Graph）
匹配问题（Matching）
最大流算法（Max Flow）
Hungarian 算法
有权图
最小生成树（MST）
Kruskal 算法
Prim 算法
Fredman-Tarjan 算法
Chazelle 算法
关键路径（Key Path）
AOE 网
有向图
无权图
拓扑排序（Topological Sorting）
深度优先遍历（后序的逆序）
强连通分量（Strongly Connected Components）
Kosaraju 算法
算法
机器学习
位运算
数学（Math）
数论（Number Theory）
计算几何（Computation Geometry）
概率统计（Probability Statistics）
随机抽样
拓扑网络（Topology Network）
线性代数（Linear Algebra）
随机（Random）
洗牌算法（Shuffle）
Fisher-Yates 算法
并行处理
高性能队列
阻塞队列
无锁队列
CAS 原子操作
解决 ABA 问题
链表实现
数组实现
Disruptor
基本使用
进阶应用
串/并行操作
多生产者多消费者模型
核心组件
RingBuffer
Sequencer
Sequence
Sequence Barrier
WaitStrategy
EventProcessor
WorkProcessor
局部性原理
伪共享
ArrayBlockingQueue
缓存行填充
无锁算法
算法思想
贪心（Greedy）
应用场景
分治（Divide and Conquer）
问题特征
应用场景
回溯（Backtracking）
应用场景
动态规划（Dynamic Programming）
模型特征
多阶段决策最优解模型
最优子结构
无后效性
重复子问题
解题思路
状态转移表
状态转移方程
常见类型
线性动态规划
单串
双串
矩阵
前缀和
区间动态规划
背包问题
状态压缩
计数问题
矩阵快速幂
数位动态规划
应用场景
枚举（Enumerating）
复杂度分析
大 O 复杂度表示法
分析方法
1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
常见的复杂度量级
O(1)：不存在循环语句、递归语句
O(logn)：二分查找
O(n)：一层循环
O(nlogn)：高级排序
O(m+n)、O(m*n)：两个数据规模
O(n^2)：排序
O(2^n)：排列
...
最好、最坏情况时间复杂度
平均情况时间复杂度
均摊时间复杂度
排序（Sort）
分析维度
内存消耗
稳定性
有序度
执行效率
最好/最坏/平均时间复杂度
时间复杂度的系数、常数 、低阶
比较次数和交换/移动次数
比较型（Comparation）
选择
选择排序（Selection Sort）
堆排序（Heap Sort）
交换
冒泡排序（Bubble Sort）
鸡尾酒排序（Cocktail Shaker Sort）
快速排序（Quick Sort）
归并排序（Merge Sort）
插入
插入排序（Insertion Sort）
希尔排序（Shell Sort）
分配型（Distribution）
桶排序（Bucket Sort）
计数排序（Counting Sort）
基数排序（Radix Sort）
查找（Search）
二分查找（Binary Search）
二叉搜索树（Binary Search Tree）
B 树（B Tree）
哈希表（Hash Table）
跳表（Skip List）
算法实现
布隆过滤器（Bloom Filter）
算法实现
字符串匹配（String）
单模式匹配
BF
RK
哈希函数
BM
KMP
Sunday
多模式匹配
字典树（Trie）
基本操作
内存消耗
缩点优化
存储节点
应用场景
AC 自动机（AC Automaton）
后缀数组（Suffix Array）
构造
直接排序
DC3 算法
SA-IS 算法
基本操作
子串查找
最长公共前缀
最长重复子串
海量数据
判断元素是否出现在集合中
使用布隆过滤器判断某个元素已存在于集合
找出出现次数最多的元素
1. 根据数据特征设计哈希函数，要将数据集均等划分。
2. 使用哈希函数把数据集划分到多个小文件：
相同元素存在于同一文件、单个文件数据量 <= 数据集大小。
3. 对每个小文件使用哈希表统计元素出现的个数。
根据每个小文件中的元素出现频度、求出现次数最多的元素。
2. 使用哈希函数把数据集划分到多个小文件：
相同元素存在于同一文件、单个文件数据量 <= 数据集大小。
3. 对每个小文件使用哈希表统计元素出现的个数。
根据每个小文件中的元素出现频度、求出现次数最多的元素。
找出出现次数最多的 N 个元素
1. 哈希函数把数据分流到多台机器上、用哈希函数拆分到多个小文件中；
2. 对每个小文件，使用哈希表统计元素出现频率；
3. 遍历哈希表，使用容量为 N 的小根堆收集 top N 元素；
4. 对每个文件小根堆（top N）进行外部排序或使用小根堆处理，得到最终 top N。
2. 对每个小文件，使用哈希表统计元素出现频率；
3. 遍历哈希表，使用容量为 N 的小根堆收集 top N 元素；
4. 对每个文件小根堆（top N）进行外部排序或使用小根堆处理，得到最终 top N。
找出指定范围内未出现的元素
1. 创建长度为数据集大小的位图，要求元素是非负整数，否则要做映射；
2. 遍历数据集，元素值对应位图的下标，修改该位置的值为 1；
3. 遍历位图，如某个位置上标记为 0，表示该元素在数据集中未出现。
2. 遍历数据集，元素值对应位图的下标，修改该位置的值为 1；
3. 遍历位图，如某个位置上标记为 0，表示该元素在数据集中未出现。
找出指定范围内任意一个未出现的元素
1. 遍历数据集，根据元素的值，在区间计数数组上统计区间上元素个数；
2. 遍历区间计数数组，找到值小于 n/k 的区间编号 i，定为目标区间；
3. 遍历数据集，关注落在目标区间内的元素（num/(n/k) == i），位图位置 bitmap[num-(n/k)*i] 设为 1；
4. 遍历位图找到未被设为 1 的位置 j，则 j+(n/k)*i 即为第一个未出现的元素。
2. 遍历区间计数数组，找到值小于 n/k 的区间编号 i，定为目标区间；
3. 遍历数据集，关注落在目标区间内的元素（num/(n/k) == i），位图位置 bitmap[num-(n/k)*i] 设为 1；
4. 遍历位图找到未被设为 1 的位置 j，则 j+(n/k)*i 即为第一个未出现的元素。
找出重复的元素
使用哈希函数将元素分配到多台机器上，每台机器分别统计重复的值；
或将大文件拆分成多个小文件，每个小文件再用哈希表遍历找到重复的值。
或将大文件拆分成多个小文件，每个小文件再用哈希表遍历找到重复的值。
求中位数
参考“找出指定范围内任意一个未出现的元素”的区间计数法：
1. 遍历数据集，根据元素的值，在区间计数数组上统计区间上元素个数。
2. 遍历计数数组，累计每个区间的计数，找出累计元素不过半与过半之间的区间编号
（比如 40 个数，前 0~k-1 区间上有 18 个，加上第 k 区间后超过 20 个，可知第 20 个数在第 k 区间第 2 个）。
3. 申请区间长度的数组，再次遍历数据集，关注出现在该区间的元素、做词频统计（找到该区间上的第 2 个元素）。
1. 遍历数据集，根据元素的值，在区间计数数组上统计区间上元素个数。
2. 遍历计数数组，累计每个区间的计数，找出累计元素不过半与过半之间的区间编号
（比如 40 个数，前 0~k-1 区间上有 18 个，加上第 k 区间后超过 20 个，可知第 20 个数在第 k 区间第 2 个）。
3. 申请区间长度的数组，再次遍历数据集，关注出现在该区间的元素、做词频统计（找到该区间上的第 2 个元素）。
找出出现 2 次的元素
比如元素值域是 [0, n]，则申请长度为 2n 的位图，用两个位置表示一个值出现的频率。
1. 遍历数据集，初次遇到 num 则把 bitmap[num*2+1] 和 bitmap[num*2] 设置为 01，
第二次则设置为 10，第三次则设置为 11，还遇到则不再设置。
2. 遍历位图，如果发现 bitmap[num*2+1] 和 bitmap[num*2] 设置为 10，则该位置表示的则为出现 2 次的元素。
1. 遍历数据集，初次遇到 num 则把 bitmap[num*2+1] 和 bitmap[num*2] 设置为 01，
第二次则设置为 10，第三次则设置为 11，还遇到则不再设置。
2. 遍历位图，如果发现 bitmap[num*2+1] 和 bitmap[num*2] 设置为 10，则该位置表示的则为出现 2 次的元素。
一致性哈希（Consistent Hashing）
算法实现
数据倾斜
布隆过滤器（Bloom Filter）
算法实现
0 条评论
下一页
