《大话数据结构》学习记录8——查找

查找

查找 (Searching) 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素 (或记录)。

一、查找概论

• 查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。
• 关键字（Key）是数据元素中某个数据项的值，又称为键值，.用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为关键码
• 若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）。
• 可以识别多个数据元素（或记录）的关键字，我们称为次关键字
• 查找方式
  • 静态查找表 (Static Search Table): 只作查找操作的查找表。
    • 查询某个“特定的”数据元素是否在查找表中。
    • 检索某个“特定的”数据元素和各种属性
  • 动态查找表 (Dynamic Search Table): 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
    • 查找时插入数据元素。
    • 查找时删除数据元素

二、顺序表查找

顺序查找 (Sequential Search) 又叫线性查找，是最基本的查找技术。它的查找过程是：

• 从表中第一个 (或最后一个) 记录开始，逐个进行记录的关键字和给定值比较，
  • 若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；
  • 如果直到最后一个 (或第一个) 记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

三、有序表查找

1、折半查找

折半查找（BinarySearch）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

• 基本思想
  • 在有序表中，取中间记录作为比较对象，
    • 若给定值与中间记录的关键字相等，则查找成功；
    • 若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；
    • 若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。
  • 不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

2、插值查找

插值查找 (Interpolation Search) 是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法。
核心就在于插值的计算公式$ \frac{key -a[low]}{a[high]-a[low]}$

3、斐波那契查找

斐波那契查找（Fibonacci Search）是一种用于在有序数组中查找特定元素的搜索算法。它是一种分割点查找法，类似于二分查找，但它使用黄金分割比例来确定分割点，从而在某些情况下可以比二分查找更快地找到目标元素。

• 基本流程：

  • 初始化两个斐波那契数列元素，通常命名为F(k-1)和F(k)，使得F(k) 刚好大于或等于待搜索数组的长度（k是一个非负整数，通常初始为2，然后逐渐增大）。
  • 计算黄金分割点的位置，也就是将数组分成两部分的索引位置。黄金分割点位置的计算公式为：$mid=start+F(k-1)-1$其中，start是搜索范围的起始索引，mid是黄金分割点的索引。
  • 比较目标元素与黄金分割点上的元素的大小。
    • 如果目标元素等于黄金分割点上的元素，搜索成功，返回黄金分割点的索引
    • 如果目标元素小于黄金分割点上的元素，说明目标元素在左半部分，更新搜索范围为[start, mid - 1]
    • 如果目标元素大于黄金分割点上的元素，说明目标元素在右半部分，更新搜索范围为[mid + 1, end]
  • 重复步骤2和3，直到找到目标元素或者搜索范围为空（start > end），此时搜索失败。

• 基本思想：

  • 斐波那契查找利用了黄金分割的概念，将数组分成两部分，其中一部分的比例接近黄金分割比例。通过这种方式，它可以在某些情况下减少比较次数，使搜索更加高效。

四、线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程，所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。

1、稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。

• 对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。

• 它与稀疏索引相对应，稠密索引会为数据库表中的每一条记录创建一个索引条目，而稀疏索引则只为部分记录创建索引条目。

• 优点：

  • 快速数据检索：稠密索引可以大大加速数据的检索操作，因为它为表中的每一条记录都创建了索引。这使得在索引字段上执行的查找非常快速。
  • 适用于范围查询：稠密索引在范围查询（例如，查找某个范围内的值）时表现良好，因为它包含了所有记录的索引。
  • 高效的等值查询：对于等值查询（例如，查找特定值的记录），稠密索引同样也非常高效。

• 缺点：

  • 占用存储空间：由于为每一条记录创建索引条目，稠密索引通常需要占用较大的存储空间。这可能会导致索引文件变得非常庞大，从而增加了数据库的存储成本。
  • 更新开销：当表中的数据发生插入、更新或删除操作时，稠密索引需要相应地维护。这可能会导致额外的更新开销，并可能降低数据修改操作的性能。
  • 不适用于所有情况：稠密索引在某些情况下可能不适用，特别是当数据表非常大且更新频繁时。在这种情况下，维护稠密索引可能成为性能瓶颈。

2、分块索引

对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

• 分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

  • 块内无序，即每一块内的记录不要求有序。
  • 块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来效率。

• 分块索引的索引项结构分三个数据项：

  • 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
  • 存储了块中的记录个数，以便于循环时使用；
  • 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

• 在分块索引表中查找，就是分两步进行：

  • 在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。
  • 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

3、倒排索引

倒排索引（Inverted Index）是一种用于加速文本检索的索引结构，通常用于搜索引擎和信息检索系统中。倒排索引的核心思想是将文档集合中的每个文档拆分成单词或词项，并记录每个词项出现在哪些文档中。这个过程的结果是一个由词项到文档列表的映射，允许快速查找包含特定词项的文档。

• 主要特点和优点：
  • 高效的文本搜索：倒排索引允许快速查找包含特定词项的文档，因此非常适用于文本搜索应用，如搜索引擎。
  • 节省存储空间：相对于稠密索引，倒排索引通常占用较少的存储空间，因为它只记录词项和文档之间的关系，而不是为每个文档创建索引条目。
  • 支持布尔查询：倒排索引可以轻松支持布尔查询，例如AND、OR和NOT操作，以便更精确地过滤搜索结果。
  • 高效的部分匹配搜索：它还支持部分匹配搜索，允许用户找到包含与查询词项相关的词根、前缀或同义词的文档。
  • 提供排名功能：倒排索引通常还会记录每个文档中词项的频率信息，这使得搜索引擎能够根据相关性对搜索结果进行排名。
• 索引项的通用结构是：
  • 次关键码
  • 记录号表
    其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引（inverted index）

五、二叉排序树

二叉排序树（BinarySort Tree）, 又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值;
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
• 它的左、右子树也分别为二叉排序树。
  构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

二叉排序树（Binary Search Tree，BST）是一种二叉树，其具有以下性质：

1. 对于每个节点，其左子树中的所有节点的值都小于等于该节点的值。
2. 对于每个节点，其右子树中的所有节点的值都大于等于该节点的值。
3. 左子树和右子树都是BST。

基于这些性质，我们可以执行查找、插入和删除操作

1. 查找操作

BST的查找操作是利用二叉搜索树的性质进行的。从根节点开始，比较目标值与当前节点的值，如果目标值小于当前节点的值，就向左子树查找，如果目标值大于当前节点的值，就向右子树查找。重复这个过程，直到找到目标节点或者遇到空节点（表示目标节点不存在）为止。

查找操作的时间复杂度为O(h)，其中h是BST的高度。在平衡的BST中，h通常为O(log n)，其中n是树中节点的总数。

2. 插入操作

BST的插入操作首先执行查找操作，以找到插入位置。一旦找到合适的位置，就在该位置创建一个新节点，将其链接到父节点，并根据插入值的大小将其放在左子树或右子树中。

插入操作的平均时间复杂度也是O(h)，在平衡的BST中，通常为O(log n)。

3. 删除操作

BST的删除操作包括以下几种情况：

• 删除叶子节点： 如果要删除的节点没有子节点，直接将其从父节点中删除即可。

• 删除只有一个子节点的节点： 如果要删除的节点只有一个子节点，将其父节点的指针指向其子节点即可。

• 删除有两个子节点的节点： 这是最复杂的情况。首先，可以选择用要删除节点的左子树中的最大值节点或右子树中的最小值节点来替代要删除的节点。然后，删除选择的替代节点（通常是用它的值来覆盖要删除的节点的值，然后再删除替代节点）。

删除操作的平均时间复杂度也是O(h)，在平衡的BST中，通常为O(log n)。

需要注意的是，删除操作可能导致BST的不平衡，因此在某些情况下，需要执行平衡操作来维护BST的平衡性。如果频繁进行插入和删除操作，可能需要考虑使用自平衡二叉搜索树，如AVL树或红黑树，以确保树的高度保持在较小的范围内，从而保持高效的性能。

六、平衡二叉树 ( AVL 树 )

平衡二叉树 ( Self~Balancing Binary Search Tree 或 Hei曲t-Balanced Binary Search Tree) , 是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
平衡二叉树是一种高度平衡的二叉排序树。
二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF (Balance Factor) 。
距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，我们称为最小不平衡子树。

平衡二叉树实现原理

插入操作： 当向平衡二叉树中插入一个新节点时，首先执行标准的BST插入操作，将节点放在正确的位置上。然后，从插入点向上遍历父节点，更新每个节点的平衡因子。如果某个节点的平衡因子的绝对值大于1，表明这个子树不再平衡，需要执行平衡操作（通常是旋转操作）来恢复平衡。

删除操作： 当从平衡二叉树中删除一个节点时，首先执行标准的BST删除操作。然后，从被删除节点的父节点向上遍历，更新每个节点的平衡因子。如果某个节点的平衡因子的绝对值大于1，表明这个子树不再平衡，需要执行平衡操作来恢复平衡。

平衡操作： 平衡操作包括左旋和右旋，它们的目的是通过重新调整树的结构来恢复平衡。左旋和右旋的具体操作会根据节点的平衡因子和子节点的平衡因子进行不同的组合。一般来说，左旋用于修复右子树过重的情况，而右旋用于修复左子树过重的情况。平衡操作可以递归地向上执行，直到整棵树重新平衡为止。

平衡二叉树的主要优点是可以保持较为稳定的搜索性能，插入和删除操作的平均时间复杂度为O(log n)。然而，平衡操作会增加树的维护开销，因此在某些情况下，如果频繁进行插入和删除操作，可能会选择其他数据结构，如红黑树。但是，平衡二叉树在某些特定情况下仍然非常有用，特别是需要保持数据有序的情况下。

七、多路查找树(B 树)

多路查找树（muittwaysearch tree）, 其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。

1、2-3 树

2-3 树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（我们称它为 2 结点）或三个孩子（我们称它为 3 结点）
一个 2 结点包含一个元素和两个孩子（或没有孩子）
一个 3 结点包含一小一大两个元素和三个孩子（或没有孩子）

插入操作：

插入一个新值到2-3树时，可以按照以下步骤进行：

1. 从根节点开始，在树中找到合适的叶子节点，这个过程类似于在普通二叉搜索树中的插入操作。

2. 如果叶子节点是2节点，直接将新值插入其中，使之成为3节点。

3. 如果叶子节点是3节点，插入新值后，形成了一个4节点（包含3个值）。此时，需要进行分裂操作，将4节点分成两个2节点，其中一个2节点会被提升到父节点中。

4. 如果分裂导致父节点成为3节点，重复这个过程，向上递归分裂，直到整个树恢复平衡。

删除操作：

删除一个值时，可以按照以下步骤进行：

1. 从根节点开始，在树中找到包含要删除值的叶子节点。如果目标值不在树中，可以根据BST性质找到其应该在的位置。

2. 如果叶子节点是2节点，可以直接删除目标值，不会引起平衡问题。

3. 如果叶子节点是3节点，可以直接删除目标值，使之变成2节点。

4. 如果要删除的值在一个2节点的子树中，可以从其兄弟节点借一个值，或者如果兄弟节点也是2节点，可以合并两个2节点。

5. 如果要删除的值在一个3节点的子树中，可以从其兄弟节点或父节点中借一个值，然后递归向下删除。

6. 删除可能导致树中的2节点或3节点变少，从而破坏树的平衡。为了保持平衡，可能需要向上递归合并或重排节点。

2-3树的插入和删除操作比较复杂，需要维护树的平衡性。这些操作的时间复杂度通常为O(log n)，其中n是树中节点的总数。尽管2-3树在理论上是有效的，但实际中，它的实现复杂度高，因此更常见的自平衡二叉搜索树结构，如AVL树和红黑树，在实际应用中更受欢迎。

2、2-3-4 树

2-3 树的概念扩展，包括了 4 结点的使用。一个 4 结点包含小中大三个元素和四个孩子（或没有孩子）

3、B 树

B 树 (B-tree) 是一种平衡的多路查找树，2-3 树和 2-3-4 树都是 B 树的特例。结点最大的孩子数目称为 B 树的阶 (order)

B树（B-tree）是一种自平衡的树状数据结构，通常用于实现关系型数据库中的索引结构和文件系统中的文件索引。它的设计思想和基本原理如下：
1. 基本原理：
B树是一种多路搜索树（multi-way search tree），它具有以下特点：

• 每个节点可以包含多个键值对，通常包含至少两个键值对。
• 节点中的键值按照升序排列。
• 所有叶子节点都位于同一层，不包含数据，用于定位数据的位置。
• 非叶子节点的子节点也是B树，从而形成多级结构。

2. B树的操作：
B树支持以下基本操作：

• 查找： 从根节点开始，根据键值在B树中进行搜索，直到找到目标键值或确定目标不存在。由于B树的多级结构，查找操作是高效的，平均时间复杂度为O(log n)，其中n是节点数。
• 插入： 插入操作会按照键值的大小将数据插入到合适的叶子节点中，如果叶子节点已满，则进行分裂操作，将中间的键值提升到父节点，从而保持B树的平衡。插入操作的平均时间复杂度也是O(log n)。
• 删除： 删除操作会从叶子节点中删除目标键值，如果删除后导致节点的键值数量低于最小允许值，则进行合并操作，将父节点中的一个键值移动到合适的子节点中。删除操作的平均时间复杂度也是O(log n)。
• 范围查询： 由于B树的特性，支持范围查询非常高效。可以通过在B树上进行遍历来查找位于某一范围内的键值对。

3. B树的思想：
B树的设计思想主要包括以下几点：

• 自平衡性：B树能够自动调整结构，确保树保持平衡。通过分裂和合并节点，B树可以自适应地调整树的高度，以保持查找、插入和删除操作的高效性。
• 多路性：B树的多路性使得它可以容纳更多的键值对，减少了树的高度，从而减少了查找的时间复杂度。这对于高效处理大量数据非常重要。
• 顺序性：B树中的节点都按顺序排列，这有助于范围查询的高效执行，因为在某一范围内的键值通常都聚集在相邻的节点中。

4、B+树

B+树（B+ tree）是一种自平衡的树状数据结构，与B树有些相似，但在某些方面有不同的设计思想和特点。B+树通常用于数据库管理系统中，用于构建索引结构，以支持高效的数据检索操作。以下是B+树的基本原理、操作和思想：

基本原理：

B+树是多路搜索树，与B树不同，它具有以下主要特点：

1. 所有数据都存储在叶子节点，非叶子节点只用于导航。
2. 所有叶子节点通过指针连接成一个有序链表，用于范围查询。
3. 非叶子节点（内部节点）包含了键值和子树的引用，用于导航至叶子节点。
4. 所有叶子节点的深度相同，即树的高度是固定的。

一棵 m 阶的 B+树和 m 阶的 B 树的差异在于：

• 有 n 棵子树的结点中包含有 n 个关键字；
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字

操作：

B+树支持以下基本操作：

1. 查找： 从根节点开始，在B+树中进行搜索，直到找到目标键值或确定目标不存在。查找操作的平均时间复杂度为O(log n)，其中n是叶子节点的数量。
2. 插入： 插入操作会将新的键值对插入到合适的叶子节点中，如果叶子节点已满，则进行分裂操作，将部分键值对移动到新创建的叶子节点，并将分裂后的节点链接起来。插入操作不会改变树的高度，因此具有固定的复杂度。
3. 删除： 删除操作会从叶子节点中删除目标键值对，如果删除导致叶子节点的键值数量低于最小允许值，可以考虑合并操作，将相邻的叶子节点合并为一个节点。删除操作也不会改变树的高度。
4. 范围查询： 由于所有叶子节点之间通过指针连接成链表，范围查询非常高效，只需要遍历链表中的节点即可。

思想：
B+树的设计思想和优势包括：

• 有序性： B+树的叶子节点形成有序链表，这使得范围查询非常高效，因为相邻的数据通常在相邻的叶子节点中。
• 定位效率： B+树的非叶子节点包含键值和子树引用，这允许快速定位叶子节点，从而加速查找操作。
• 固定高度： B+树的高度是固定的，与数据量无关。这意味着查找、插入和删除操作的性能是可预测的，不受数据量的影响。
• 适用于磁盘存储： B+树的设计考虑了磁盘I/O操作的优化，因此非常适合用于数据库系统等需要大规模存储和快速检索数据的应用。

八、散列表查找（ 哈希表 ）概述

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f, 使得每个关键字 key 对应一个存储位置 f (key)。
这种对应关系 f 称为散列函数，又称为哈希 (Hash) 函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表 (Hash table)。

散列表查找步骤

• 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
• 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。
  散列技术最适合的求解问题是查找与给定值相等的记录。
  两个关键字 $key1\ne key2$, 但是却有 f (key1) =f (key2), 这种现象我们称为冲突 (collision), 并把 key1和
  key2 称为这个散列函数的同义词 (synonym)

九、散列函数的构造方法

好的散列函数:计算简单;散列地址分布均匀

1、直接定址法

取关键字的某个线性函数值为散列地址，即 $f(key)=a\ast key+b(a、b为常数)$

2、数字分析法

利用输入数据的某些数字特性，如位数、数字组合、模式等，将数据映射到散列表中的位置。目标是尽量使散列值均匀地分布在散列表的不同位置，以减少冲突（碰撞）的发生。

3、平方取中法

将输入数字的平方，然后从平方结果的中间提取一段数字作为散列值。

4、折叠法

将输入数据分成若干段，然后将这些段相加以得到最终的散列值

5、除留余数法

将输入数据除以一个合适的除数，然后取余数作为最终的散列值。
此方法为最常用的构造散列函数方法。对于散列表长为 m 的散列函数公式为：
f ( key ) = key mod p ( p≤m )
mod 是取模 (求余数) 的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

6、随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是 f (key)=random (key)。这里 random 是随机函数。

十、处理散列冲突的方法

当我们在使用散列函数后发现两个关键字 keyiHkeyz, 但是却有 f (keyl) =f(key2), 即有冲突

1、开放定址法

开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
fi ( key )= ( f ( key )+di ) MOD m ( di=1,2,3,… ,m-1 )
开放定址法（Open Addressing）是一种处理散列冲突的方法，它在散列表中寻找下一个可用的位置来存储冲突的元素，而不是将冲突的元素放入散列表中的链表或其他数据结构中。开放定址法有许多不同的变体，其中最常见的包括线性探测、二次探测和双重散列。

基本原理：

1. 开放定址法将散列表视为一个大小固定的数组，每个位置都可以存储一个元素。
2. 当发生冲突时，开放定址法尝试在散列表中的其他位置找到一个可用的空槽来存储冲突的元素。
3. 开放定址法通过一种规则来确定下一个要尝试的位置。这个规则可能是线性探测、二次探测、双重散列等。
4. 冲突的解决过程会一直持续，直到找到一个空槽来存储元素或者确定元素无法插入（表已满）。

常见的变体：

1. 线性探测（Linear Probing）： 在线性探测中，当发生冲突时，会逐个检查下一个位置，直到找到一个可用的位置或者达到散列表的末尾。线性探测的规则是 $h(k,i)=(h^{\prime }(k)+i)$ ，其中h’(k)是初始散列值，i是线性增量，m是散列表大小。
2. 二次探测（Quadratic Probing）： 在二次探测中，发生冲突时，会使用二次函数来计算下一个尝试的位置。规则是 $h(k,i)=(h^{\prime }(k)+c1\ast i+c2\ast i^2)$ ，其中 $h^{\prime }(k)$ 是初始散列值，c1和c2是常数，i是探测次数，m是散列表大小。
3. 双重散列（Double Hashing）： 在双重散列中，发生冲突时，会使用第二个散列函数来计算下一个尝试的位置。规则是 $h(k,i)=(h1(k)+i\ast h2(k))$ ，其中h1(k)是第一个散列函数，h2(k)是第二个散列函数，i是探测次数，m是散列表大小。
4. 随机探测法（Random Probing）: 随机探测法使用随机化的方式来选择下一个尝试的位置。$f(key)=(f(key))MODm(4是一个随机数列)$ 。这种方法的目标是减少冲突的发生和聚集现象，从而提高散列表的性能。

优点和注意事项：

• 开放定址法的主要优点是它节省了存储空间，因为不需要存储额外的数据结构来处理冲突。
• 开放定址法的性能取决于散列表的装载因子（存储元素数量与散列表大小的比率）以及选择的探测方法。当装载因子较低时，性能较好。
• 当装载因子较高时，开放定址法可能会导致探测次数增多，性能下降，甚至发生聚集（clustering）现象，使得冲突更频繁。因此，在实际应用中，需要谨慎选择散列表大小和探测方法，以保持较低的装载因子。\

2、再散列函数法

再散列函数法（Rehashing）是一种处理散列冲突的方法，它涉及到使用另一个散列函数来计算新的散列位置，以解决原始散列位置上的冲突。当散列表中的冲突发生时，再散列函数法将应用一个新的散列函数，将冲突的元素重新散列到新的位置上。

基本原理：

1. 在散列表中存储两个或多个不同的散列函数，通常称为"主散列函数"和"再散列函数"。
2. 当发生冲突时，使用再散列函数来计算新的散列位置。
3. 如果新位置也发生冲突，可以继续应用再散列函数，直到找到一个可用的位置为止。
4. 对散列值进行模运算，将其限制在散列表的大小范围内，以获得最终的散列位置。

步骤：

1. 初始化散列表，并设置主散列函数和再散列函数。
2. 当需要插入一个元素时，首先应用主散列函数，计算元素的初始散列位置。
3. 如果初始位置没有冲突，将元素插入到该位置。
4. 如果初始位置已经被占用，发生了冲突，此时会使用再散列函数来计算新的散列位置。
5. 如果新位置仍然被占用，可以继续应用再散列函数，直到找到一个可用的位置。
6. 最终将元素插入到找到的可用位置。

优点和注意事项：
再散列函数法的主要优点是它可以解决冲突，避免了聚集问题，并且不需要使用开放定址法的线性探测、二次探测或其他规则。
然而，需要注意的是：

• 再散列函数法可能导致额外的计算开销，因为需要计算多次散列函数来找到可用的位置。
• 选择好的散列函数对于再散列函数法至关重要，因为它会影响性能。应该选择散列函数，以尽量避免新的冲突，而不是将元素一直散列到相同的位置。

3、链地址法

链地址法（Chaining）是一种处理散列冲突的方法，它涉及将具有相同散列值的元素存储在同一个位置上，并使用链表（或其他数据结构）来存储这些冲突的元素。具体而言，每个散列槽（桶）都可以包含一个链表，链表中存储了所有散列到该槽的元素。

基本原理：

1. 初始化一个具有固定数量槽的散列表，每个槽都包含一个链表（或其他数据结构）。
2. 使用散列函数将元素映射到散列表的一个槽。
3. 如果多个元素映射到同一个槽，它们将按照顺序添加到该槽的链表中。
4. 当需要查找、插入或删除元素时，首先计算元素的散列值，然后定位到相应的槽，并在槽的链表中执行相应的操作。

步骤：

1. 初始化一个散列表，确定散列表的大小，通常是一个素数或2的幂次方，以便分布均匀。
2. 使用散列函数将元素的关键字映射到散列表的槽。这通常涉及将关键字传递给散列函数，然后使用模运算将结果映射到槽。
3. 如果多个元素映射到同一个槽，将它们添加到该槽的链表中。通常，新元素会被添加到链表的头部或尾部，具体取决于设计选择。
4. 在查找、插入或删除元素时，首先计算元素的散列值，然后定位到相应的槽。
5. 在槽的链表中执行相应的操作，例如，对于查找操作，遍历链表以查找目标元素。

优点和注意事项：
链地址法的主要优点是它可以有效地处理冲突，并且不需要计算额外的偏移量或重新散列元素。它允许在同一个槽中存储多个元素，因此适用于高装载因子的情况。

需要注意的是：

• 当链表变得很长时，性能可能会下降。因此，通常需要考虑一些策略来管理链表，例如，当链表长度超过一定阈值时，可以考虑重新散列或使用其他数据结构来代替链表。
• 选择好的散列函数对于链地址法至关重要，以确保元素均匀分布在槽中，而不会导致某些槽变得特别长。

4、公共溢出区法

公共溢出区法（Overflow Area Method）是一种处理散列冲突的方法，它涉及使用一个公共的溢出区域来存储具有相同散列值的元素。当冲突发生时，元素会被添加到溢出区域中，而不是与其他元素竞争同一个散列表槽。

十一、散列表查找实现

1、散列表查找算法实现

理解散列表（哈希表）的原理和步骤对于实现和使用它非常重要。

原理：

1. 散列函数（Hash Function）： 散列表的核心是散列函数，它将输入的键（key）映射为散列值（hash value）或散列码（hash code）。散列函数应该是确定性的，即对于相同的键，应始终返回相同的散列值。散列函数的目标是将键均匀分布在散列表的槽（buckets）中。
2. 槽（Bucket）： 散列表由多个槽组成，每个槽可以存储一个或多个键值对。槽的数量通常是固定的，但可以根据需求进行调整。
3. 冲突处理： 由于不同的键可能映射到相同的槽，因此可能发生冲突。散列表需要一种方法来处理冲突。常见的冲突处理方法包括链地址法、开放定址法和公共溢出区法等。
4. 装载因子（Load Factor）： 装载因子是指散列表中已存储键值对的数量与槽的总数之比。装载因子可以用来衡量散列表的满载程度，影响散列表的性能。通常，当装载因子超过一定阈值时，需要调整散列表的大小，以避免冲突过多。

步骤：

1. 初始化： 创建一个具有固定数量槽的散列表。通常，槽的数量选择为素数或2的幂次方以获得更好的均匀性。
2. 插入（Insertion）： 若要插入键值对，首先通过散列函数计算键的散列值。然后，根据散列值找到相应的槽，如果该槽为空，则将键值对存储在其中；如果槽已被占用，根据冲突处理方法执行相应的操作，例如将新键值对添加到链表或找到下一个可用槽。
3. 查找（Lookup）： 若要查找特定键对应的值，首先通过散列函数计算键的散列值。然后，根据散列值找到相应的槽，如果槽为空，则表明键不存在；如果槽已被占用，则根据具体的冲突处理方法查找键。
4. 删除（Deletion）： 若要删除特定键值对，首先通过散列函数计算键的散列值。然后，根据散列值找到相应的槽，如果槽为空，则表明键不存在；如果槽已被占用，则根据具体的冲突处理方法查找并删除键值对。

2、散列表查找性能分析

• 散列函数是否均匀
• 处理冲突的方法
• 散列表的装填因子