2.Data Structures

1. 是什么 - 可动态扩容的数组 2. 动态数组 2.1. 数据结构 - 存放数据的数组 - 已使用的长度 - 总长度 2.2. API 2.3. 实现 2.3.1. 测试 3. 刷题套路 3.1. 双指针 3.1.1. 同向 - - [0, i) 是处理好的数据， [i, j) 是处理过但不需要

1. 是什么 - K-V对 2. 二叉搜索树实现 2.1. 数据结构 - 二叉搜索树 2.2. API 2.3. 实现 2.3.1. 测试 3. 哈希表实现 3.1. hash函数的设计 - 原则 - 一致性：如果a==b，则hash（a）==hash（b） - 高效性：计算高效简便 - 均匀性：哈

1. 是什么 2. 数组 vs 链表 数组按照索引查找快，链表插入删除快 3. 单向链表 3.1. 数据结构 - 头节点 - 长度 3.2. API 3.3. 实现 3.3.1. 测试 4. 双向链表 4.1. 数据结构 - 头节点 - 尾节点 - 长度 4.2. API - 同单向链表 4.3.

1. 是什么 - 先进先出 2. 普通队列 2.1. 数据结构 - 动态数组或链表 2.2. API 2.3. 实现 2.3.1. 测试 3. 循环队列 3.1. 数据结构 - 存放数据的数组 - 已使用的长度 - 总长度 - 头节点下标位置 - 尾节点下标位置 3.2. API - 同队列 3.3

1. 是什么 - 无序、不重复的集合 1.1. 数据结构 - hashmap 1.2. API 1.3. 实现 1.3.1. 测试

1. 是什么 - 后进先出 1.1. 数据结构 - 动态数组或链表 1.2. API 2. 实现 2.1. 测试

1. 二叉树是什么 每个节点最多有两个子节点 2. 二叉树操作 2.1. 遍历 2.1.1. 先序遍历 先访问根节点，然后访问左子树，最后访问右子树 2.1.2. 中序遍历 先访问左子树，然后访问根节点，最后访问右子树 2.1.3. 后序遍历 先访问左子树，然后访问右子树，最后访问根节点 2.1.4

1. 红黑树是什么 - 一种平衡二叉查找树 - 满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值 - 满足5条特性即可保证平衡 - 节点 要么是Red，要么是Black - 根节点 是Black - 叶子节点 （外部节点以及空节点）都是Black - Red

1. 跳表是什么 - 跳表相当于普通的链表有两个区别 - 有上、下、左、右四个指针 - 多了层的概念 1.1. 举例 - 普通链表 - - 有效层数为2的跳表 - - 有效层数为4的跳表 - 1.2. 特点 - 随机的数据结构 - 最底层包含了整个跳表的所有元素 - 典型的空间换时间，增删查改效率为

1. 堆是什么 逻辑上看成一棵树，实际上是个数组。 - 位置关系 在数组起始位置为0的情形中： - 父节点i的左子节点在位置 2 i + 1 - 父节点i的右子节点在位置 2 i + 2 - 子节点i的父节点在位置 (i - 1) / 2 - 排序属性 - 最大堆：父节点的值 左右节点 - 最小堆：

1. BitMap是什么 - 又叫位图 - 把数据存放在一个以bit为单位的数据结构里，每位都只有0和1两个值。为0的时候，证明值不存在；为1的时候说明存在。 1.1. 举例 这个时候假如我们要存放2 4 6 8 9 10 17 19 21这些数字到我们的BitMap里，我们只需把对应的位设置为1就

1. 为什么需要BloomFilter 1.1. BloomFiler vs HashSet 一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？ 若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出 - 如果使

1. 图是什么 - 由边和顶点组成 2. 图分类 有方向 无方向 ------ --------- --------- 有权重 有向有权图 无向有权图 无权重 有向无权图 无向无权图 3. 图的表示 3.1. 邻接矩阵 - 用二维数组存储顶点之间的关系：两顶点相邻则为1，不相邻则为 0 - 3.2.

1. 是什么 - 一种树结构，区别在于是孩子指向父亲 2. 有什么用 - 解决连接问题（比路径问题更加简单） 3. 实现 3.1. API 3.2. Quick Find 3.2.1. 测试 3.3. Quick Union - 3.3.1. 测试 3.4. 基于size的优化 3.4.1. 测试

1. 是什么 - log-structured merge-tree - 一种数据结构，用于write-heavy的场景 2. 为什么LSM适合写多读少 - 利用了磁盘顺序写的速度快于磁盘随机写 3. 数据结构 3.1. SSTables - Sorted Strings Table - 数据持久化

1. 什么是ziplist - Redis底层的一种数据结构，用于实现list、zset > 2026 注：这是旧版 Redis 的实现背景；现代 Redis 已不再以 ziplist 作为这些结构的主要编码。 - 一段连续的内存空间 2. 为什么需要ziplist - 动态数组：由长度+元素列表组成。每个元素占用的空间大小相同，类型也是相同的 - - ziplist：也由长度+元素列表组成。不同之处在于 - 每个元素

1. B Tree是什么 - self-balance search tree中的一种 - 是个多叉查找树 - 2. 为什么需要B Tree 2.1. 背景 - 数据库查询的需求： - 根据某个值查找数据，比如 select from user where id=1234； - 根据区间值来查找某些

1. 什么是稀疏索引 - 首先他是个索引 - 索引.md - 其次他是稀疏的 - 稀疏索引和密集索引的区别在于是否为每个key都建立索引 2. 为什么需要稀疏索引 稀疏索引占用空间小 2.1. 稀疏索引 vs 密集索引 稀疏索引 密集索引 ------------------ -----------

1. 索引是什么 - 索引是一种把查找关键字和对应的数据记录关联起来（可以看作key-value对）的数据结构 - 索引查找是通过索引来查找数据 2. 为什么需要索引 - 用来加速数据的查找 3. 稀疏索引 vs 稠密索引 - 稀疏索引.md 4. 正排索引 vs 倒排索引 - 倒排索引.md 5.

1. 正排索引 文档Id- 文档 ，比如MySQL 1.1. 如何查找包含关键词的文档 1. 需要遍历所有文档 【O(N)】 2. 逐字逐字匹配 【O(m+n)】 2. 倒排索引 关键词- 文档Id + 文档Id- 文档 ，比如ES 先把文档分词，然后记录分词以及对应文档Id的映射，同时记录文档ID