【数据结构】查找表

发表于 | 分类于 |

数据结构笔记-查找表部分。

查找表

查找表是一种用于存储和检索数据的数据结构，其核心功能是快速定位和访问数据项。

静态查找表

静态查找表是指一旦创建，其存储结构不会被改变的查找表。这种查找表主要用于查找和读取元素，不支持动态地添加或删除元素。

静态查找表通过不同的查找方法提供了对数据项的快速访问。 顺序查找适用于无序数据，二分查找和分块查找适用于有序数据，而静态树表查找则提供了一种在有序数据上进行高效查找的树形结构。

查找方法

顺序查找

  • 概念：从查找表的第一个元素开始，逐个检查每个元素，直到找到目标元素或遍历完所有元素。
  • 时间复杂度：平均情况下为O(n)。
  • 优点：实现简单，不需要元素的预排序。
  • 缺点：效率较低，特别是对于大量数据。

二分查找

  • 概念：在已排序的查找表中，通过比较中间元素与目标值来决定是继续在左半部分还是右半部分进行查找，直到找到目标或查找范围为空。
  • 时间复杂度：O(log n)。
  • 优点：查找效率高。
  • 缺点：要求查找表预先排序。

分块查找

  • 概念：将查找表分成多个块，每块内部有序，块与块之间无序。查找时，先确定目标值可能在哪个块，然后在块内进行顺序查找。
  • 时间复杂度：取决于块的大小和数量。
  • 优点：减少了顺序查找的范围，提高了查找效率。
  • 缺点：块的划分和维护可能较为复杂。

应用场景

静态查找表适用于数据量不大或数据不经常变动的场景。例如，查找某个固定集合内的元素、字典中的单词查找等。

动态查找表

二叉排序树（Binary Search Tree, BST）

二叉排序树，也称为二叉搜索树，是一种特殊的二叉树，其节点存储具有可比性的数据项，并且满足以下性质：

  • 每个节点的左子树上所有节点的键值小于它的键值。
  • 每个节点的右子树上所有节点的键值大于它的键值。
  • 每个节点的左右子树也分别是二叉排序树。
  • 没有键值相等的节点。

特点

  • 可以高效地进行数据的插入、删除和查找操作。
  • 查找操作的时间复杂度为O(h)，其中h是树的高度。
  • 树的平衡性对操作效率有重要影响，极端情况下（如退化成链表）时间复杂度为O(n)。

插入操作

  1. 从根节点开始：将新节点与根节点进行比较。
  2. 遍历树：根据比较结果，将新节点插入到相应的子树中。
  3. 递归或迭代：重复上述过程，直到找到适当的位置。

删除操作

  1. 查找待删除的节点：首先找到需要删除的节点。
  2. 删除节点：有三种情况：
    • 没有子节点：直接删除该节点。
    • 有一个子节点：用其子节点替换它。
    • 有两个子节点：找到其后继（通常是右子树中的最小节点）替换它，然后删除后继节点。

查找操作

  1. 从根节点开始：将目标值与根节点的键值进行比较。
  2. 遍历树：根据比较结果，选择进入左子树或右子树。
  3. 递归或迭代：重复上述过程，直到找到目标值或遍历到叶子节点。

二叉排序树的应用

  • 二叉排序树由于其结构特性，常用于实现关联数组、数据库索引等。
  • 它们提供了一种在有序数据上进行动态操作的有效方法。

AVL树

AVL树是一种自平衡二叉搜索树。

AVL树的节点除了存储数据和指向子节点的指针外，还包含一个额外的字段来存储节点的平衡因子。 AVL树的每个节点都有一个平衡因子，该因子是其左子树深度和右子树深度的差。

AVL树的平衡因子绝对值永远不会超过1，这保证了树的高度大致为$ \log_2{(n+1)}$，其中n是树中节点的数量。

基本定义

  • 平衡因子：对于任何节点，其左子树和右子树的高度差不能超过1。
  • 平衡操作：当插入或删除操作导致树失去平衡时，需要进行旋转操作来恢复平衡。

特点

  • 保持了二叉搜索树的所有性质。
  • 所有叶子节点具有相同的深度，或高度差至多为1。
  • 插入和删除操作的时间复杂度为O(log n)。

旋转

插入或删除节点后，AVL树可能失去平衡。这时，需要从被修改的节点开始，逐层向上检查并调整平衡因子，直到根节点。 如果发现任何节点的平衡因子绝对值大于1，则需要进行以下四种类型的旋转之一来恢复平衡：

  • LL旋转（左左旋转）：当一个节点的左子节点的左子树过高时，进行LL旋转。
  • RR旋转（右右旋转）：当一个节点的右子节点的右子树过高时，进行RR旋转。
  • LR旋转（左右旋转）：当一个节点的左子节点的右子树过高时，先对左子节点进行RR旋转，然后对原节点进行LL旋转。
  • RL旋转（右左旋转）：当一个节点的右子节点的左子树过高时，先对右子节点进行LL旋转，然后对原节点进行RR旋转。

构造过程

  1. 插入操作：按照二叉搜索树的规则插入新节点。
  2. 更新平衡因子：从插入点向上遍历，更新每个节点的平衡因子。
  3. 检测不平衡：如果任何节点的平衡因子绝对值大于1，执行旋转操作。

AVL树的应用

  • AVL树由于其自平衡特性，常用于需要频繁插入和删除的场景，如实时应用和索引结构。

B树

B树和B+树是多路搜索树，主要用于数据库和文件系统。

  • B树的每个内部节点可以有多个子节点，通常是2到M个。
  • B树的节点包含数据项和指向子节点的指针。
  • 所有键都在节点的内部，数据项在节点内部按顺序排列。
  • 所有叶子节点都在同一层。
  • 内部节点的键将子树分为连续范围。

基本定义

  • 度：一个节点最多可以拥有的子节点数。
  • 最小度数：通常是度的一半，确保树的平衡。

构造过程

  1. 插入操作：从根节点开始，将新键插入到适当的子树中。如果节点未满，直接插入；如果节点已满，需要分裂节点。
  2. 分裂操作：如果一个节点在插入新键后超过最大度，会将节点分裂成两个节点，并将中间的键提升到父节点。如果父节点也满了，这个过程会递归地向上进行。

B树操作

范围查询

B树支持高效的范围查询，因为内部节点的键将子树分为连续的范围。

可以通过遍历一个节点的所有子节点，然后递归地在相应的子树中进行查询。

插入操作
  1. 搜索：从根节点开始，根据键值搜索到适当的插入位置的节点。
  2. 节点未满：如果节点的键数小于最大度数，直接插入到该节点的适当位置。
  3. 节点已满：如果节点的键数等于最大度数，需要将节点分裂成两个节点，并将中间的键提升到父节点。
  4. 递归分裂：如果父节点也满了，继续进行分裂，直到根节点。如果根节点满了，根节点分裂后需要创建一个新的根节点。
删除操作
  1. 搜索：从根节点开始，搜索到包含待删除键的节点。
  2. 删除：如果待删除的键在非叶子节点，找到该键并删除，然后从其子节点中找到后继（或前驱）键替换它。
  3. 调整：如果删除操作导致节点的键数小于最小度数，需要从兄弟节点借用键或合并节点，以保持树的平衡。

B+树

B+树是B树的变种，所有键都存储在叶子节点，内部节点只存储键的副本和子节点的指针。

特点

  • 叶子节点通过指针连接，便于顺序访问。
  • 内部节点不存储数据，只存储键和子节点的指针。

构造过程

  1. 插入操作：与B树类似，但所有键最终存储在叶子节点。
  2. 分裂操作：如果叶子节点满了，将中间的键提升到新的内部节点。

B+树操作

顺序访问

B+树的叶子节点通过指针连接，形成了一个链表，这使得B+树非常适合顺序访问。可以通过遍历叶子节点的链表来实现顺序访问。

范围查询

B+树的范围查询非常高效。首先定位到范围的起始键所在的叶子节点，然后通过叶子节点的链表顺序访问直到范围的结束键。

插入操作
  1. 搜索：与B树类似，从根节点开始，搜索到适当的插入位置的节点。
  2. 叶子节点插入：新键总是插入到叶子节点。如果叶子节点未满，直接插入；如果满了，需要分裂节点。
  3. 分裂：与B树类似，分裂节点并将中间的键提升到父节点。如果父节点也满了，继续分裂直到根节点。
删除操作
  1. 搜索：与B树类似，搜索到包含待删除键的叶子节点。
  2. 删除：直接从叶子节点中删除键。
  3. 调整：如果删除后叶子节点的键数少于最小度数，可能需要从兄弟节点借用键或合并节点。与B树不同，B+树的内部节点不存储数据，所以调整过程只涉及键和指针。

B+树的应用

  • B+树由于其顺序访问和范围查询的特性，常用于数据库和文件系统，特别是需要顺序读取大量数据的场景。
  • 在数据库和文件系统中，B+树由于其高效的顺序访问和范围查询性能，被广泛使用。

哈希表

哈希表是一种高效的数据结构，用于实现关联数组，即以键-值对的形式存储数据。它使用哈希函数将键映射到数组的索引上，从而实现快速查找、插入和删除操作。

哈希函数

一个将任意大小的键转换为固定大小的索引的函数。理想的哈希函数应该使键尽可能均匀地分布在数组中。

以下是几种常用的哈希函数：

  1. 除留余数法：
    • 公式: h(key) = key mod m，其中m是哈希表的大小。
    • 这是最简单的哈希函数，易于实现，但m的选择很重要，通常m取素数以提高散列质量。
  2. 乘法散列：
    • 公式: h(key) = floor(m * (A * key mod 1))，其中A是一个介于0和1之间的常数，通常选择A使得A = (sqrt(5) - 1) / 2。
    • 这种方法试图减少对低阶位的依赖，提高散列的质量。
  3. 随机散列：
    • 使用伪随机数生成器为每个键生成哈希值，可以提供更好的散列效果，但实现起来更复杂。
  4. 哈希函数组合：
    • 结合多种哈希函数，如CRC32、MD5或SHA-1/SHA-256等，适用于安全性要求高的场景。

冲突解决策略

当两个或多个不同的键被哈希到同一个索引时，会发生冲突。常见的冲突解决策略包括链地址法（开放寻址法）和开放寻址法（二次探测、线性探测）。

  1. 链地址法（Separate Chaining）：
    • 在每个哈希位置存储一个链表或某种动态数据结构。
    • 当发生冲突时，将键值对添加到相应位置的链表中。
  2. 开放寻址法（Open Addressing）：
    • 所有元素都存储在哈希表本身，没有外部链接。
    • 主要有三种技术：
      • 线性探测（Linear Probing）：当发生冲突时，线性地寻找下一个可用位置。
      • 二次探测（Quadratic Probing）：探测间隔逐渐增加，如1, 4, 9, 16…，以减少聚集。
      • 双重散列（Double Hashing）：使用第二个哈希函数来决定跳跃的步长，以避免线性探测中的集群效应。
  3. 再散列（Rehashing）：
    • 当冲突频繁发生时，可以采用再散列，即重建整个哈希表，通常伴随着增大哈希表的大小。

主要操作

插入

计算键的哈希值，检查是否有冲突，如果没有，则将键值对存入该位置；如果有冲突，则根据冲突解决策略处理。

查找

同样使用哈希函数计算键的位置，如果位置已被占用（冲突），则根据冲突解决策略来处理。否则直接访问该位置获取值。

删除

先查找键，然后移除相应的键值对，可能需要调整冲突解决策略。

性能分析

  • 平均情况下，哈希表的插入、查找和删除操作的时间复杂度接近O(1)。
  • 最坏情况下，如果所有键都哈希到同一个位置，时间复杂度可能退化至O(n)。

优化

  • 负载因子：哈希表中存储的键值对数量与哈希表大小的比率。通常保持在较低水平（如0.7以下）可以减少冲突。
  • 动态调整大小：当负载因子过高时，应重新哈希（rehashing），即创建一个更大的哈希表并将所有键值对重新插入。

应用场景

  • 缓存机制，如数据库缓存、网页缓存等。
  • 字典和集合数据类型，在编程语言的标准库中常见。