数据结构

树结构

定义

• 树（Tree） 是由n（n≥0）个节点组成的有限集合，满足：

  1. 有且仅有一个根节点（Root）（无父节点）；
  2. 除根节点外，其余节点分为若干个互不相交的子集，每个子集仍是一棵树（称为子树（Subtree））；
  3. 节点之间通过边（Edge） 连接，不存在环路。

• 节点（Node）：树的基本单元，包含数据和指向子节点的引用；

• 父节点 / 子节点：若节点 A 直接指向节点 B，则 A 是 B 的父节点，B 是 A 的子节点（类比父子关系）；

• 兄弟节点：同一父节点的子节点互称兄弟（类比兄弟姐妹）；

• 叶子节点（Leaf）：没有子节点的节点（类比家族中的 “晚辈”）；

• 节点的深度（Depth）：从根节点到当前节点的边数（根节点深度为 0）；

• 节点的高度（Height）：从当前节点到最深叶子节点的边数（叶子节点高度为 0）；

• 树的高度：从树的叶子节点开始计数，直到根节点。通常情况下，叶子节点的高度为0，然后向上逐层增加。因此，只有一个根节点的树高度为0，如果树为空（没有节点），则高度为-1。

• 树的深度：从树的根节点开始计数，直到最深的叶子节点。根节点的深度为0，然后向下逐层增加。

• 度：当前节点下的子节点个数

• 节点的层（Level）：深度 + 1（根节点为第 1 层）。

• 树的层数：与节点的深度类似，但计数起点为1。也就是说，根节点位于第1层。

• 数据在计算机中的存储结构主要为顺序存储结构、链式存储结构、索引存储结构、散列存储结构，其中链式存储结构最常见的示例是链表与树，链式存储结构主要有以下特点：
  • 优点：逻辑相邻的节点物理上不必相邻，插入、删除灵活，只需改变节点中的指针指向
  • 缺点：存储空间利用率低，需通过指针维护节点间的逻辑关系；查找效率比顺序存储慢

二叉树

• 二叉树是最基础的树结构，每个节点最多有 2 个子节点（左子节点和右子节点），即度（子节点数量）≤2。左侧子树节点称为“左子树”（left subtree），右侧子树节点称为“右子树”（right subtree）。
• 二叉树的特点
  • 至少有一个节点(根节点)
  • 每个节点最多有两颗子树，即每个节点的度小于3。
  • 左子树和右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。
• 满二叉树（Full Binary Tree）：所有非叶子节点都有 2 个子节点，且叶子节点在同一层。
• 完全二叉树（Complete Binary Tree）：叶子节点从左到右依次填充，且除最后一层外，其余层都是满的；最后一层的叶子节点靠左排列（适合用数组存储，如堆）。

二叉搜索树

• 二叉搜索树（又称二叉排序树，二叉查找树，（Binary Search Tree, BST））是有序的二叉树，满足：
  1. 左子树中所有节点的值 < 根节点的值；
  2. 右子树中所有节点的值 > 根节点的值；
  3. 左、右子树也必须是二叉搜索树。
• 核心特性：
  1. 查找高效：通过比较目标值与根节点，可快速缩小范围（类似二分查找）；
  2. 中序遍历（左→根→右）结果为升序序列。
• 二叉查找树的查询效率介于O(log n)~O(n)之间，理想的排序情况下查询效率为O(log n),极端情况下BST就是一个链表结构(如下图)，此时元素查找的效率相等于链表查询O(n)。
• 问题：若插入数据有序（如 1,2,3,4），BST 会退化为链表（所有节点只有右子节点），此时查找时间复杂度从 O (logn) 恶化到 O (n)。

节点序号关系

• 在根节点序号为 1 的完全二叉树中，节点的序号与层次（深度）存在严格对应关系：第k层（层次从 1 开始）的节点序号范围是 [2^(k-1), 2^k - 1]。

第 1 层（根节点）：序号1（范围[2^0, 2^1-1] = [1,1]）；
第 2 层：序号2、3（范围[2^1, 2^2-1] = [2,3]）；
第 3 层：序号4、5、6、7（范围[2^2, 2^3-1] = [4,7]）；
第k层：共2^(k-1)个节点，序号从2^(k-1)到2^k - 1。

• ⌊log₂a⌋ = ⌊log₂b⌋意味着：节点a和b在完全二叉树的同一层次（深度相同）。
• 节点x的父节点序号为⌊x/2⌋

平衡二叉搜索树

• 为解决 BST 退化问题，平衡二叉搜索树（Balanced Tree）通过控制左右子树高度差，维持 O (logn) 的高效操作。
• 核心思想：插入 / 删除后若失衡，通过旋转调整结构。

AVL树

• AVL树最早的平衡二叉搜索树，由Adelson-Velskii和Landis在1962年提出。
• AVL 树是严格平衡的二叉搜索树，要求：左右子树的高度差（平衡因子）绝对值 ≤ 1（平衡因子 = 左子树高度 - 右子树高度）。
• 失衡与旋转：当插入 / 删除导致某节点平衡因子＞1 或＜-1 时，需通过旋转修复。有 4 种基础旋转：

LL 旋转（左左失衡）：
    失衡节点的左子树的左子树过深（平衡因子 = 2）。
    操作：将失衡节点的左子树作为新根，失衡节点作为新根的右子节点，新根原右子树作为失衡节点的左子树。
RR 旋转（右右失衡）：
    失衡节点的右子树的右子树过深（平衡因子 =-2）。
    操作：与 LL 对称，将失衡节点的右子树作为新根，失衡节点作为新根的左子节点。
LR 旋转（左右失衡）：
    失衡节点的左子树的右子树过深（平衡因子 = 2）。
    操作：先对左子树做 RR 旋转，再对失衡节点做 LL 旋转（两步旋转）。
RL 旋转（右左失衡）：
    失衡节点的右子树的左子树过深（平衡因子 =-2）。
    操作：先对右子树做 LL 旋转，再对失衡节点做 RR 旋转（两步旋转）。

• 特点：
  1. 严格平衡，查询效率极高（O (logn)）；
  2. 但旋转频繁（插入 / 删除可能多次旋转），适合查询多、修改少的场景（如数据库索引早期）。
• 总结：由于插入(或删除)一个节点时需要扫描两趟树，一次向下查找插入点，一次向上平衡树，所以AVL树不如下面介绍的红黑树效率高，也不如红黑树常用。(也就是说为了保持平衡，平衡二叉树定义节点的左子树和右子树的高度差不大于1，这种规定过于严格，导致在做插入或删除操作时需要自底向上逐层检查节点的平衡性(高度差)，因此效率较低)

红黑树

• 红黑树（Red-Black Tree）是弱平衡的二叉搜索树，通过颜色规则维持平衡（不严格控制高度差，而是保证最长路径≤最短路径的 2 倍）。
• 核心规则：
  1. 每个节点非红即黑；
  2. 根节点是黑的；
  3. 叶子节点（NIL 节点，空节点）是黑的；
  4. 红节点的子节点必为黑（无连续红节点）；
  5. 从任意节点到其所有叶子节点的路径中，黑节点数量相同（黑平衡）。
• 失衡修复：插入 / 删除后若违反规则，通过变色和旋转（LL/RR/LR/RL，与 AVL 类似）修复。

平衡多路查找树

• BST、AVL、红黑树都是典型的二叉查找树结构，其查找的时间复杂度与树高相关。那么降低树高自然对查找效率是有所帮助的。另外还有一个比较实际的问题：就是在大量数据存储中实现查询的场景下，平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。那么如何减少树的深度（当然不能减少查询数据量），一个基本的想法就是：
  1. 每个节点存储多个元素 （但元素数量不能无限多，否则查找就退化成了节点内部的线性查找了）。
  2. 摒弃二叉树结构而采用多分支(多叉)树（由于节点内元素数量不能无限多，自然子树的数量也就不会无限多了）。

B树

• B树（B-Tree）是为磁盘或其他直接存储的辅助设备而设计的一种平衡搜索树。B树类似于红黑树，但它们在降低磁盘I/O操作次数方面要更好一些。

• 一棵m阶的B-Tree有如下特性：  　　1. 每个节点最多有m个孩子。  　　2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。  　　3. 若根节点不是叶子节点，则至少有2个孩子  　　4. 所有叶子节点都在同一层，且不包含其它关键字信息  　　5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）  　　6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1  　　7. ki(i=1,…n)为关键字，且关键字升序排序。  　　8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

• B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

• 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

• 查找关键字29的过程：

  1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
  2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
  3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
  4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
  5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
  6. 在磁盘块8中的关键字列表中找到关键字29。

• 由于节点内部的关键字是有序的，所以在节点内部的查找可以使用二分法进行。分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+树

• B+树是B树的一种变种和优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

• 从上面的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

• B树与B+树对比

B*树

B*树是B+树的变体，在B+Tree的非根和非叶子结点再增加指向兄弟的指针

红黑树意义

问题：有了二叉查找树、平衡树（AVL），为啥还需要红黑树？

答案：

极端情况下，二叉树会退化成链表，时间复杂度从O(logn)退化为O(n)。所以有了平衡二叉树。平衡二叉树对平衡的要求过于严格——每个节点的左右子树的高度差最多为1。这样导致每次进行插入或删除时都会破坏平衡规则，需要进行左旋和右旋来调整。所以有了红黑树。

红黑树具有如下特点：1、具有二叉查找树的特点。2、根节点是黑色的；3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。

正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。与平衡树不同的是，红黑树在插入、删除等操作时不会像平衡树那样频繁着破坏红黑树的规则，所以不需要频繁的调整，这也是大多数情况下使用红黑树的原因。

但是，仅在查找效率方面，平衡树比红黑树快。所以，红黑树是一种不大严格的平衡树，可以说是一个折中发方案。

总之：平衡树是为了解决二叉搜索树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。

哈希

• 哈希定义：哈希（又称 “散列”）是一种将任意长度的输入数据，通过特定算法（哈希函数）映射到固定长度输出值的技术。这个输出值称为 “哈希值”（或 “散列值”）。

• 哈希特点

  1. 相同输入一定得到相同哈希值；
  2. 不同输入可能得到相同哈希值（称为 “哈希冲突”，无法完全避免，但好的哈希函数会尽量减少）；
  3. 计算快速，且从哈希值反推原始数据极难（单向性）。

• 举例

一个简单的哈希函数是 “取数字除以 10 的余数”：
输入 123 → 哈希值 3（123 % 10 = 3）；
输入 456 → 哈希值 6（456 % 10 = 6）；
输入 783 → 哈希值 3（与 123 冲突）。

哈希表

存储/查询过程

• 定义:是一种基于哈希函数实现的高效数据结构，核心是 “用哈希值快速定位数据存储位置”，用于实现 “键值对（KV）” 的存储和查询。
• 原理：
  1. 有一个数组（称为 “哈希表”），每个位置称为 “桶（Bucket）”；
  2. 插入键值对（Key, Value）时：
  3. 用哈希函数计算 Key 的哈希值；
  4. 用哈希值对数组长度取模，得到数组下标（即桶的位置）；
  5. 将 Value 存入该下标对应的桶中；
  6. 查询时，用同样的方法计算 Key 的哈希值→下标→直接从桶中取 Value（时间复杂度接近 O (1)）。
• 工作流程：哈希表的工作流程本质是：用哈希函数将 “键（Key）” 转换为数组索引，再将 “值（Value）” 存入该索引对应的数组位置（桶）。
• 举例

哈希函数：比如用 “key 的 ASCII 码之和”（简化版）；
数组长度：设为 8（索引 0~7）；
取模操作：哈希值 % 8，得到数组索引。
现在插入键值对 ("abc", 100)：
步骤 1：计算 key 的哈希值。"a"(97) + "b"(98) + "c"(99) = 294；
步骤 2：对数组长度取模。294 % 8 = 6（因为 8×36=288，294-288=6）；
步骤 3：将 100 存入数组索引 6 的位置。

查询 "abc" 时，同样计算哈希值 294 → 取模 6 → 直接访问索引 6 得到 100。

底层数据

哈希表的核心功能就是存储和快速查询键值对（KV），而它的底层实现几乎都是以数组为基础的，原因是：

• 数组的最大优势是 “随机访问”—— 通过索引可以直接定位到目标位置（时间复杂度 O (1)），这与哈希表追求 “快速查询” 的目标完美匹配。
• 哈希表的工作流程本质是：用哈希函数将 “键（Key）” 转换为数组索引，再将 “值（Value）” 存入该索引对应的数组位置（桶）。

冲突解决

链表法

• 假设哈希表的底层结构是「数组 + 链表」

  1. 计算目标键的哈希值：用与插入时相同的哈希函数，计算目标 Key 的哈希值（例如 Java 中 key.hashCode()）。
  2. 定位到对应的桶（数组索引）：用哈希值对数组长度取模，得到目标 Key 所在的桶（数组索引），此时这个桶中存储着一个链表（所有哈希冲突的键值对都在这里）。
  3. 遍历链表，比较原始键的相等性：链表中的每个节点都存储着完整的键值对（Key + Value）。遍历链表时，对每个节点的 Key 执行两步判断：
     1. 第一步：比较哈希值：先快速比较目标 Key 的哈希值与节点中 Key 的哈希值。如果不相等，直接跳过（哈希值不同的 Key 一定不是目标）。
     2. 第二步：比较原始键本身：若哈希值相等，再用 equals() 方法（Java）或 == 运算符（C++，需重载）比较原始 Key 的实际内容，确认是否完全一致。
  4. 找到匹配项后返回对应的值：当找到某个节点的 Key 与目标 Key 完全相等时，返回该节点的 Value；若遍历完链表仍无匹配，说明哈希表中不存在该 Key。

• 核心思想：

  • 哈希值用于快速缩小范围：先定位到可能的桶（减少遍历范围），哈希值不同的 Key 直接排除。
  • 原始键的相等性比较用于最终确认：因为不同的 Key 可能有相同的哈希值（哈希冲突），必须通过原始 Key 的实际内容比对才能确定是否为目标。
  • 这种 “哈希值粗筛 + 原始键精筛” 的方式，既利用了哈希的高效定位能力，又解决了哈希冲突可能导致的误判问题。
  • 数组（桶）负责通过哈希值快速定位到大致范围（链表的起点）；
  • 链表负责存储所有哈希冲突的键值对，每个节点完整保存 key、value 和 next 指针；
  • 这种设计既保证了哈希表的高效查询（平均 O (1)），又解决了哈希冲突问题。

• 分析：

  • 桶（数组元素）的作用：数组的每个元素（桶）本质是一个 “指针 / 引用”，指向链表的第一个节点。如果该桶没有哈希冲突（没有键值对映射到这里），则指针为 null。
  • 链表节点的内容：每个链表节点必须同时存储：
    1. key：原始键（用于发生冲突时，通过 equals 比较确认目标）；
    2. value：键对应的值（哈希表要存储的实际数据）；
    3. next：指向链表中下一个节点的指针（形成链表结构，存储所有冲突的键值对）。
  • 为什么必须同时存 key 和 value：
    1. value 是必须的（哈希表的核心是存储键值对）；
    2. key 也是必须的：当发生哈希冲突时，多个键值对会存在同一个链表中，必须通过 key 才能区分它们，找到目标键值对。

• 举例：

哈希表数组（table）:
+----+    +----+    +----+
| 0  | -> |null|    |    |  // 桶0：无冲突，指针为null
+----+    +----+    +----+
| 1  | -> |节点A| -> |节点B|  // 桶1：有冲突，链表存储多个键值对
+----+    +----+    +----+
| 2  | -> |null|    |    |  // 桶2：无冲突
+----+    +----+    +----+

// 链表节点结构（简化）：
节点A: {
  key: "apple",    // 键
  value: 10,       // 值
  next: 节点B      // 指向下一个节点的指针
}

节点B: {
  key: "apply",    // 另一个键（与"apple"哈希冲突）
  value: 20,       // 对应的值
  next: null       // 链表末尾
}

开放寻址法

• 核心思想：当哈希冲突发生时，不额外创建链表，而是在哈希表的数组中重新寻找一个空闲的桶（位置）来存储冲突的键值对。

• 具体实现方式：

  1. 线性探测（也叫线性探测再散列法）：如果冲突时，依次检查下一个桶（索引 + 1），直到找到空闲位置。例如键 A 哈希到索引 3，若被占用，则尝试 4、5、6... 直到找到空位。
  2. 二次探测：冲突时，按 “索引 ±1²、±2²、±3²...” 的顺序寻找空闲位置（避免线性探测的 “聚集效应”）。
  3. 双重哈希：冲突时，用第二个哈希函数计算步长，按 “索引 + 步长” 的方式寻找空位（步长与键相关，更分散）。

[!NOTE] 适用场景：哈希表装载因子（已存储元素 / 数组容量）较低时（通常 < 0.7），查询效率较高。常见于：C++ 的 std::unordered_map 某些实现（视编译器而定）；一些内存敏感的场景（无需额外存储链表指针，节省内存）。

• 优缺点：

  1. 优点：无需指针 / 引用，内存连续性好，缓存利用率高；
  2. 缺点：删除元素复杂（不能直接清空，需标记为 “已删除”），装载因子过高时性能急剧下降。

• 举例

假设有一个容量为 10 的哈希表（数组索引 0~9），哈希函数为 h1(key) = key % 10（用于计算初始位置），需要插入的键依次为：23、13、33、43（这些键的初始哈希值都是 3，会发生连续冲突）。

线性探测（Linear Probing）
原理：冲突时，依次检查下一个索引（index+1、index+2...），直到找到空闲位置（或哈希表满）。
插入过程：
插入 23：h1(23)=23%10=3，索引 3 空闲，直接存入 → 哈希表 [3] = 23。
插入 13：h1(13)=13%10=3，索引 3 已被占用（冲突），探测下一个位置 3+1=4，空闲 → 存入哈希表 [4] = 13。
插入 33：h1(33)=33%10=3，索引 3 被占用，探测 4（被 13 占用），再探测 5（空闲）→ 存入哈希表 [5] = 33。
插入 43：h1(43)=43%10=3，探测 3（占用）→4（占用）→5（占用）→6（空闲）→ 存入哈希表 [6] = 43。
结果：哈希表索引 3~6 分别存储：23、13、33、43。

二次探测（Quadratic Probing）
原理：冲突时，按 “index ± 1²、± 2²、± 3²...” 的顺序探测，避免线性探测的 “聚集效应”（连续占用一片区域）。
插入过程（仍用上述键和哈希表）：
插入 23：同线性探测，存入索引 3。
插入 13：初始索引 3 冲突，探测 3 + 1²=4（空闲）→ 存入索引 4 = 13。
插入 33：初始索引 3 冲突，探测 4（占用），再探测 3 - 1²=2（空闲）→ 存入索引 2 = 33。
插入 43：初始索引 3 冲突，探测 4（占用）→2（占用），再探测 3 + 2²=7（空闲）→ 存入索引 7 = 43。
结果：哈希表索引 2、3、4、7 分别存储：33、23、13、43（分布更分散，避免连续占用）。

双重哈希（Double Hashing）
原理：冲突时，用第二个哈希函数 h2(key) 计算 “步长”，按 “index + h2(key)、index + 2*h2(key)...” 探测（步长与键相关，更分散）。
设定：
第一个哈希函数 h1(key) = key % 10（初始位置）；
第二个哈希函数 h2(key) = 7 - (key % 7)（确保步长不为 0，且与表长互质，减少重复探测）。
插入过程：
插入 23：h1(23)=3，空闲 → 存入索引 3 = 23。
插入 13：h1(13)=3（冲突），h2(13)=7 - (13%7)=7-6=1 → 步长 1。探测 3+1=4（空闲）→ 存入索引 4 = 13。
插入 33：h1(33)=3（冲突），h2(33)=7 - (33%7)=7-5=2 → 步长 2。探测 3+2=5（空闲）→ 存入索引 5 = 33。
插入 43：h1(43)=3（冲突），h2(43)=7 - (43%7)=7-1=6 → 步长 6。探测 3+6=9（空闲）→ 存入索引 9 = 43。
结果：哈希表索引 3、4、5、9 分别存储：23、13、33、43（分布最分散，冲突概率更低）。

链表 + 红黑树

• 核心思想：这是对链表法的优化：当链表长度超过阈值（如 Java 中默认 8），自动将链表转为红黑树。

• 红黑树的 “左小右大” 特性是实现高效查询的关键：查找时，只需根据键的比较结果，从根节点开始向左或向右遍历（类似二分查找），时间复杂度为 O (log n)，远快于链表的 O (n)。

• 冲突较少时用链表（插入简单，内存开销小）；

• 冲突较多（链表过长）时转红黑树（查询、删除的时间复杂度从 O (n) 优化为 O (log n)）。

典型案例：

其他方案

• 再哈希法：冲突时，用新的哈希函数重新计算哈希值，直到找到空闲桶（但多次哈希可能影响性能）。
• 建立公共溢出区：将哈希表分为 “基本表” 和 “溢出表”，冲突的元素统一存到溢出表（类似链表法的集中版，查询时需先查基本表，再查溢出表）。

总结对比

• 开放寻址法的三种实现通过不同的 “探测步长” 解决冲突，其中双重哈希分布最分散，线性探测最简单但易聚集；
• 链表 + 红黑树中，冲突的键值对在红黑树中按键的比较顺序有序存储，以保证高效的查询性能。

装填因子

• 装填因子（Load Factor）是哈希表的一个核心参数，定义为：装填因子 = 哈希表中已存储的键值对数量 / 哈希表的总容量

• 当装填因子为 0.6 时，意味着哈希表中已使用的空间占总容量的 60%（例如，容量为 100 的哈希表中已存入 60 个键值对）。

• 装填因子的意义：

  1. 与冲突概率正相关：装填因子越大，哈希表越 “满”，键值对之间发生冲突的概率越高；反之，装填因子越小，冲突概率越低，但空间利用率也越低。
  2. 性能平衡点：实际应用中，哈希表的装填因子通常会设置一个阈值（如 0.7、0.6），当实际装填因子超过阈值时，会触发哈希表的 “扩容”（扩大容量并重新哈希所有键值对），以平衡冲突概率和空间利用率。

• 举例：Java HashMap 默认的装填因子阈值为 0.7，当实际装填因子超过 0.7 时，会自动扩容为原来的 2 倍，避免冲突过多导致性能下降。而 0.6 的装填因子意味着更保守的设置，冲突概率更低，但空间利用率稍差。

哈希表的实现

2. HashMap

   • 最常用的哈希表实现，存储键值对（Key-Value），允许 Key 和 Value 为 null。
   • 底层用数组 + 链表 / 红黑树实现（当链表长度超过阈值时转为红黑树优化查询）。
   • 线程不安全，适合单线程场景。

3. HashTable

   • 早期的哈希表实现，功能与 HashMap 类似，但线程安全（方法加了 synchronized 锁）。
   • 不允许 Key 或 Value 为 null，性能比 HashMap 差，现在较少使用（推荐用 ConcurrentHashMap 替代）。

4. ConcurrentHashMap

   • 线程安全的哈希表实现，用于多线程环境。
   • 采用分段锁（JDK 1.7）或 CAS + synchronized（JDK 1.8）实现高效并发，性能优于 HashTable。

5. HashSet

   • 基于 HashMap 实现的 “集合”（仅存储键，不存储值）。
   • 本质是用 HashMap 的 Key 存储元素，Value 存一个空对象（PRESENT），利用哈希表实现元素的快速去重和查询。

6. std::unordered_map

   • 存储键值对（Key-Value）的哈希表，Key 唯一，通过 Key 快速查询 Value。
   • 底层用数组 + 链表（或开链法）处理哈希冲突，元素无序（与 std::map 基于红黑树的有序性不同）。

7. std::unordered_set

   • 基于哈希表的 “集合”，仅存储不重复的元素（类似 Java 的 HashSet）。
   • 底层通常复用 std::unordered_map 的实现（Key 为元素，Value 无实际意义），元素无序。
   • 集合中存储的是原始键本身，哈希操作仅用于计算存储位置，不会修改原始键。

8. std::unordered_multimap / std::unordered_multiset

   • 允许 Key 重复的哈希表（multimap 存键值对，multiset 存元素）。
   • 其他特性与 unordered_map / unordered_set 一致，适合需要存储重复键的场景。

• 举例

hashCode("abc") = 96354，hashCode("def") = 100884；
数组长度为 10，取模后：96354 % 10 = 4，100884 % 10 = 4（索引都是 4）；
底层数组索引 4 的位置会形成链表："abc" → "def"（存储的是原始字符串）；
当调用contains("def")时：
    计算"def"的哈希值→取模→定位到索引 4；
    遍历链表，用equals比较每个元素，找到"def"并返回true。
查询依赖哈希 + 原始键比对：先通过哈希快速定位到索引，再通过原始键的 equals/== 比对找到具体元素，兼顾效率和准确性。

例题

题目

将序列 8 ，10，9，12，15，20散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 H (K) = K^2 mod 6，处理冲突采用线性探测再散列法，装填因子为 0.6，则在计算等概率情况下，查找成功的平均查找长度为？

解答

9. 确定散列表容量
   • 散列表容量 = 元素数量 / 装填因子 = 6 / 0.6 = 10，即散列表是下标为 0~9 的数组。(当冲突位置在 9 时，下一个位置会循环到 0)
10. 计算各元素的初始哈希位置

H(8) = 8² mod 6 = 64 mod 6 = 4（6×10=60，64-60=4）
H(10) = 10² mod 6 = 100 mod 6 = 4（6×16=96，100-96=4）
H(9) = 9² mod 6 = 81 mod 6 = 3（6×13=78，81-78=3）
H(12) = 12² mod 6 = 144 mod 6 = 0（6×24=144，144-144=0）
H(15) = 15² mod 6 = 225 mod 6 = 3（6×37=222，225-222=3）
H(20) = 20² mod 6 = 400 mod 6 = 4（6×66=396，400-396=4）

11. 用线性探测法处理冲突，确定最终位置及查找长度

插入 8：
    初始位置 4 空闲，直接存入。
    查找长度 = 1（只检查位置 4）。
插入 10：
    初始位置 4 已被 8 占用（冲突），探测位置 5（空闲），存入。
    查找长度 = 2（检查位置 4→5）。
插入 9：
    初始位置 3 空闲，直接存入。
    查找长度 = 1（只检查位置 3）。
插入 12：
    初始位置 0 空闲，直接存入。
    查找长度 = 1（只检查位置 0）。
插入 15：
    初始位置 3 已被 9 占用（冲突），探测位置 4（被 8 占用）→位置 5（被 10 占用）→位置 6（空闲），存入。
    查找长度 = 4（检查位置 3→4→5→6）。
插入 20：
    初始位置 4 已被 8 占用（冲突），探测位置 5（被 10 占用）→位置 6（被 15 占用）→位置 7（空闲），存入。
    查找长度 = 4（检查位置 4→5→6→7）。

12. 计算平均查找长度

    • 总查找长度 = 1（8） + 2（10） + 1（9） + 1（12） + 4（15） + 4（20） = 13

13. 平均查找长度 = 总查找长度 / 元素数量 = 13 / 6 ≈ 2.17

堆

基础定义

• 堆(Heap)核心特性是父节点与子节点之间存在严格的大小关系。根据这种关系，堆可分为最小堆和最大堆。

• 最小堆（Min Heap）:任意节点的值小于等于其左右子节点的值，且根节点是整个堆中最小的元素。

• 最大堆（Max Heap）:任意节点的值大于等于其左右子节点的值，且根节点是整个堆中最大的元素。

• 堆逻辑上是一种完全二叉树结构，但通常物理上用数组实现,因为完全二叉树的节点索引有明确规律，可通过数组下标快速定位父节点和子节点：若节点索引为 i（从 1 开始）：则左子节点索引：2*i；右子节点索引：2*i + 1；父节点索引：i/2（向下取整）。这种结构避免了树节点的指针开销，且操作高效（时间复杂度多为 O(log n)）。

堆化

• 堆化（Heapify）：维持堆特性的核心操作
• 堆化是当堆的特性被破坏时（如插入新元素或删除根节点后），通过调整节点位置恢复堆特性的过程。分为上浮（Sift Up） 和下沉（Sift Down） 两种
• 应用：优先队列、堆排序、Top-K 问题等，依赖堆的高效插入和删除极值特性。

上浮（用于插入元素后）

• 最大堆的插入操作可以简单看成是“结点上浮”。当我们在向最大堆中插入一个结点必须满足完全二叉树的标准，那么被插入结点的位置的是固定的。而且要满足父结点关键字值不小于子结点关键字值，那么就需要去移动父结点和子结点的相互位置关系。

• 将元素插入最后一位，再进行向上冒泡，即如果父节点的值小于被插入的元素，父节点下移，被插入的元素上移。时间复杂度取决于树的高度h。而完全二叉树的树的高度为[logn+1]的上取整，所示时间复杂度为O(logn)。

下沉（用于删除根节点后）

• 当删除根结点20之后明显不是一个完全二叉树，更确切地说被分成了两棵树。需要移动子树的某一个结点来充当该树的根节点，那么在(15,2,14,10,1)这些结点中移动哪一个呢？显然是移动结点1，如果移动了其他结点（比如14，10）就不再是一个完全二叉树了。显然现在看来该二叉树虽然是一个完全二叉树，但是它并不符合最大堆的相关定义，目的是要在删除完成之后，该完全二叉树依然是最大堆。1）、此时在结点（15，2）中选择较大的一个和1做比较，即15 > 1的，所以15上浮到之前的20的结点处。 2）、同第1步类似，找出（14，10）之间较大的和1做比较，即14>1的，所以14上浮到原来15所处的结点。 3）、因为原来14的结点是叶子结点，所以将1放在原来14所处的结点处。

• 删除操作的逻辑为，删除堆的根节点，将最后一个节点补到根节点位置，得到一颗不符合规则的堆。再对根节点进行向下冒泡，即如果父节点小于某一孩子或所有孩子，将元素值最大 的孩子与父节点交换。孩子上移，父节点下移，下移后与孩子重复该操作，直到比孩子都大或没有孩子。删除操作向下冒泡，操作时间还是取决于树的高度，时间复杂度为O(logn)