数据结构知识网络尊享版（迅速相识回顾相关知识）

1、单链表、循环链表、双向链表，存储、逻辑结构

单链表、循环链表和双向链表都是线性表的链式存储结构，它们在存储和逻辑结构上有一些共同点和差别点。
存储结构

• 单链表：每个节点包含一个数据域和一个指针域，指针域指向下一个节点。末了一个节点的指针域为空（NULL），表示链表的竣事。
  
• 循环链表：与单链表雷同，每个节点包含一个数据域和一个指针域，但末了一个节点的指针域指向链表的头节点，形成一个闭环。
  
• 双向链表：每个节点包含一个数据域和两个指针域，一个指向前驱节点，一个指向后继节点。头节点的前驱指针为空，尾节点的后继指针为空。
  

逻辑结构

• 单链表：
  
  
  
  • 优点：插入和删除操纵只必要修改指针，不必要移动元素，时间复杂度为 (O(1))。
    
  • 缺点：只能重新节点开始遍历，查找某个节点必要 (O(n)) 的时间复杂度。
    
  
  
• 循环链表：
  
  
  
  • 优点：可以方便地从恣意节点开始遍历整个链表，得当某些必要循环操纵的场景（如循环队列）。
    
  • 缺点：查找某个节点的时间复杂度仍旧是 (O(n))，但可以制止链表为空时的特殊环境处置处罚。
    
  
  
• 双向链表：
  
  
  
  • 优点：可以从恣意节点向前或向后遍历，插入和删除操纵更加机动，时间复杂度为 (O(1))。
    
  • 缺点：每个节点必要额外的指针空间，占用更多的内存。
    
  
  

应用场景

• 单链表：适用于必要频繁插入和删除操纵，且不必要频繁查找的场景。
  
• 循环链表：适用于必要循环操纵的场景，如循环队列、圆形游戏等。
  
• 双向链表：适用于必要频繁双向遍历的场景，如欣赏器的前进退却功能、某些双向队列等。
  

2、栈、循环队列，元素个数判断、空/非空判断、多次收支后存储环境

栈和循环队列也都是线性数据结构，但它们在元素的收支次序和存储方式上有所差别。
栈

• 元素个数判断：栈的元素个数可以通过一个计数器来记载，每次入栈时计数器加1，出栈时计数器减1。
  
• 空/非空判断：
  
  
  
  • 空判断：如果计数器为0，则栈为空。
    
  • 非空判断：如果计数器大于0，则栈非空。
    
  
  
• 多次收支后的存储环境：
  
  
  
  • 栈遵循后进先出（LIFO）的原则，即末了进入的元素最先被取出。
    
  • 多次收支后，栈顶元素始终是最近一次入栈且未被取出的元素。
    
  • 如果栈的容量有限，多次收支时必要留意栈满的环境，防止溢出。
    
  
  

循环队列

• 元素个数判断：循环队列的元素个数可以通过队尾指针和队首指针的差值来计算，但必要留意循环的环境。
  
  
  
  • 如果队尾指针大于队首指针，元素个数为 rear - front。
    
  • 如果队尾指针小于队首指针，元素个数为 rear - front + capacity，此中 capacity 是队列的容量。
    
  
  
• 空/非空判断：
  
  
  
  • 空判断：如果队首指针即是队尾指针，则队列为空。
    
  • 非空判断：如果队首指针不即是队尾指针，则队列非空。
    
  
  
• 多次收支后的存储环境：
  
  
  
  • 循环队列遵循先进先出（FIFO）的原则，即先进入的元素最先被取出。
    
  • 多次收支后，队首指针始终指向队列的第一个元素，队尾指针指向队列末了一个元素的下一个位置。
    
  • 为了制止队列满时的判断错误，通常会牺牲一个存储空间来区分队列满和队列空的环境。比方，当 (rear + 1) % capacity == front 时，队列满。
    
  
  

应用场景

• 栈：适用于必要回溯或撤销操纵的场景，如函数调用的堆栈、欣赏器的退却功能、括号匹配等。
  
• 循环队列：适用于必要循环操纵的场景，如任务调度、缓冲区管理等。
  

留意事项

• 栈：在使用栈时，必要留意栈溢出的环境，尤其是在递归调用深度较大的环境下。
  
• 循环队列：在使用循环队列时，必要留意队列满和队列空的判断条件，制止误判。
  

3、串next求取、BF及KMP模式匹配过程

串的next数组求取

KMP算法中的next数组用于记载模式串中每个字符的前缀和后缀的最大雷同长度。具体求取过程如下：

• 初始化：
  
  
  
  • next[0] = -1，表示第一个字符没有前缀和后缀可以比力。
    
  • 初始化两个指针 j 和 k，此中 j 用于遍历模式串，k 用于记载前缀的长度。
    
  
  
• 计算next数组：
  
  
  
  • 当 k == -1 大概模式串的第 j 个字符与第 k 个字符相等时，next[j] = k，然后 j 和 k 都加1。
    
  • 如果不相等，则 k 更新为 next[k]，继续比力。
    
  
  
• 循环竣事：
  
  
  
  • 当 j 遍历完备个模式串时，next数组计算完成。
    
  
  

BF模式匹配过程

BF算法（暴力匹配算法）是最简朴的字符串匹配算法：

• 初始化：
  
  
  
  • 设置两个指针 i 和 j，分别指向文本串和模式串的起始位置。
    
  
  
• 匹配过程：
  
  
  
  • 如果 text 和 pattern[j] 相等，则 i 和 j 都向后移动一位。
    
  • 如果不相等，则将模式串向后移动一位，即 j 重置为0，i 指向下一个字符。
    
  
  
• 匹配乐成：
  
  
  
  • 当 j 到达模式串的末端时，表示匹配乐成，返回 i - j 作为匹配位置的起始索引。
    
  
  
• 匹配失败：
  
  
  
  • 如果 i 遍历完文本串，则表示没有匹配到模式串。
    
  
  

KMP模式匹配过程

KMP算法使用next数组来优化匹配过程：

• 初始化：
  
  
  
  • 设置两个指针 i 和 j，分别指向文本串和模式串的起始位置。
    
  • 计算模式串的next数组。
    
  
  
• 匹配过程：
  
  
  
  • 如果 text 和 pattern[j] 相等，则 i 和 j 都向后移动一位。
    
  • 如果不相等，则 j 更新为 next[j]，i 保持不变。
    
  
  
• 匹配乐成：
  
  
  
  • 当 j 到达模式串的末端时，表示匹配乐成，返回 i - j 作为匹配位置的起始索引。
    
  
  
• 匹配失败：
  
  
  
  • 如果 i 遍历完文本串，则表示没有匹配到模式串。
    
  
  

KMP算法通过next数组减少了不必要的比力，从而进步了匹配效率。
4、二维数组存储计算

二维数组在计算机中通常以一维数组的形式存储，主要有两种存储方式：按行存储和按列存储。差别的存储方式会影响元素的访问和计算方式。以下是对这两种存储方式的详细说明：
按行存储（Row-major Order）

• 存储方式：二维数组的元素按行次序存储在一维数组中。首先存储第一行的所有元素，然后是第二行的所有元素，依此类推。
  
• 地址计算：假设二维数组 A 的巨细为 m x n，每个元素占用 size 个字节，基地址为 base，则元素 A[j] 的地址可以通过以下公式计算：
  Address(A[j])=base+(i×n+j)×size
  此中，i 是行索引，j 是列索引。
  

按列存储（Column-major Order）

• 存储方式：二维数组的元素按列次序存储在一维数组中。首先存储第一列的所有元素，然后是第二列的所有元素，依此类推。
  
• 地址计算：同样假设二维数组 A 的巨细为 m x n，每个元素占用 size 个字节，基地址为 base，则元素 A[j] 的地址可以通过以下公式计算：
  Address(A[j])=base+(j×m+i)×size
  此中，i 是行索引，j 是列索引.
  

示例

假设有一个二维数组 A，巨细为 3 x 4，每个元素占用 4 个字节，基地址为 1000。按行存储和按列存储的地址计算如下：

• 按行存储：
  
  
  
  • A[1][2] 的地址：
    Address(A[1][2])=1000+(1×4+2)×4=1000+24=1024
    
  
  
• 按列存储：
  
  
  
  • A[1][2] 的地址：
    Address(A[1][2])=1000+(2×3+1)×4=1000+28=1028
    
  
  

树的遍历

树的遍历主要有三种方式：先序遍历、中序遍历和后序遍历。这些遍历方式通常用于二叉树，但也可以扩展到多叉树。
先序遍历

• 界说：先访问根节点，然后递归地先序遍历左子树，末了递归地先序遍历右子树。
  
• 过程：
  
  
  • 访问根节点。
    
  • 先序遍历左子树。
    
  • 先序遍历右子树。
    
  
  

中序遍历

• 界说：先递归地中序遍历左子树，然后访问根节点，末了递归地中序遍历右子树。
  
• 过程：
  
  
  • 中序遍历左子树。
    
  • 访问根节点。
    
  • 中序遍历右子树。
    
  
  

后序遍历

• 界说：先递归地后序遍历左子树，然后递归地后序遍历右子树，末了访问根节点。
  
• 过程：
  
  
  • 后序遍历左子树。
    
  • 后序遍历右子树。
    
  • 访问根节点.
    
  
  

二叉树的次序存储

二叉树的次序存储是将二叉树的节点存储在一个一维数组中，按照从上到下、从左到右的次序分列。这种存储方式适用于完全二叉树和满二叉树，但对于一样平常的二叉树大概会浪费空间。
存储规则

• 根节点：存储在数组的第一个位置（索引为0）。
  
• 左子节点：对于索引为 i 的节点，其左子节点的索引为 2i + 1。
  
• 右子节点：对于索引为 i 的节点，其右子节点的索引为 2i + 2。
  
• 父节点：对于索引为 i 的节点，其父节点的索引为 (i - 1) / 2（向下取整）.
  

示例

假设有一个二叉树，其节点值如下：

1.         1
2.        / \
3.       2   3
4.      / \   \
5.     4   5   6

复制代码

其次序存储的数组为 [1, 2, 3, 4, 5, 6]。
应用场景

• 先序遍历：常用于复制树结构、打印树结构等。
  
• 中序遍历：对于二叉搜索树，中序遍历可以得到节点值的有序序列。
  
• 后序遍历：常用于计算树的巨细、删除树等。
  
• 次序存储：适用于完全二叉树和满二叉树，如堆的实现.
  

留意事项

• 遍历递归实现：递归实现简朴直观，但大概会导致栈溢出，尤其是在树的深度较大时。
  
• 非递归实现：可以使用栈来实现非递归遍历，制止递归调用的开销。
  
• 次序存储空间浪费：对于一样平常的二叉树，次序存储大概会浪费大量空间，因为必要为不存在的节点预留位置。
  

哈夫曼树的构建

哈夫曼树是一种用于数据压缩的无损编码方法，其构建过程如下：

• 初始化：
  
  
  
  • 将每个字符及其出现的频率视为一个节点，初始化一个优先队列（最小堆），将所有节点加入队列。
    
  
  
• 构建过程：
  
  
  
  • 从优先队列中取出两个权值最小的节点。
    
  • 创建一个新的节点，其权值为两个取出节点的权值之和。
    
  • 将新节点的左子节点和右子节点分别设置为取出的两个节点。
    
  • 将新节点重新加入优先队列。
    
  • 重复上述步骤，直到优先队列中只剩下一个节点，该节点即为哈夫曼树的根节点。
    
  
  

哈夫曼编码的求取

哈夫曼编码是通过哈夫曼树来确定每个字符的编码，具体步骤如下：

• 初始化：
  
  
  
  • 从哈夫曼树的根节点开始，初始化一个空字符串作为编码路径。
    
  
  
• 编码过程：
  
  
  
  • 从根节点向叶子节点遍历：
    
    
    
    • 如果向左子节点移动，则在编码路径上添加“0”。
      
    • 如果向右子节点移动，则在编码路径上添加“1”。
      
    
    
  • 当到达叶子节点时，该叶子节点对应的字符的编码即为当前的编码路径。
    
  
  
• 编码效果：
  
  
  
  • 每个字符的哈夫曼编码是唯一的，且通常较短的编码分配给出现频率较高的字符。
    
  
  

示例

假设有一组字符及其频率：A(5), B(9), C(12), D(13), E(16), F(45)，构建哈夫曼树并求取编码的过程如下：

• 构建哈夫曼树：
  
  
  
  • 初始优先队列：A(5), B(9), C(12), D(13), E(16), F(45)
    
  • 取出 A(5) 和 B(9)，创建新节点 AB(14)，加入队列：AB(14), C(12), D(13), E(16), F(45)
    
  • 继续归并，直到构建完备棵树。
    
  
  
• 求取编码：
  
  
  
  • 从根节点开始遍历，终极得到每个字符的编码：
    
    
    
    • F: 0
      
    • C: 100
      
    • D: 101
      
    • A: 1100
      
    • B: 1101
      
    • E: 111
      
    
    
  
  

邻接矩阵和邻接表

邻接矩阵

• 界说：邻接矩阵是一个二维数组，用于表示图中极点之间的毗连关系。
  
• 存储方式：
  
  
  
  • 对于无向图，邻接矩阵是对称的。A[j] 表示极点 i 和极点 j 之间的边的权重。如果 i 和 j 之间没有边，则 A[j] 为无穷大或一个特定的值（如0）。
    
  • 对于有向图，邻接矩阵不肯定对称。A[j] 表示从极点 i 到极点 j 的边的权重。
    
  
  
• 优点：
  
  
  
  • 可以快速判断两个极点之间是否存在边。
    
  
  
• 缺点：
  
  
  
  • 空间复杂度高，尤其是对于奇怪图，会浪费大量空间。
    
  
  

邻接表

• 界说：邻接表是一个数组，每个数组元素是一个链表，用于存储与该极点相邻的所有极点。
  
• 存储方式：
  
  
  
  • 对于无向图，每个极点的邻接表中存储与其相连的所有极点。
    
  • 对于有向图，每个极点的邻接表中存储其所有出边的目标极点。
    
  
  
• 优点：
  
  
  
  • 空间复杂度低，得当奇怪图。
    
  
  
• 缺点：
  
  
  
  • 判断两个极点之间是否存在边必要遍历链表，时间复杂度较高。
    
  
  

深度优先遍历（DFS）和广度优先遍历（BFS）

深度优先遍历（DFS）

• 过程：
  
  
  
  • 从一个极点开始，沿着一条路径尽大概深地搜索，直到无法继续前进。
    
  • 回溯到上一个极点，继续搜索其他未访问的路径。
    
  
  
• 实现：
  
  
  
  • 使用递归或栈来实现。
    
  • 标记已访问的极点，制止重复访问。
    
  
  
• 应用：
  
  
  
  • 用于寻找路径、检测图的连通性等。
    
  
  

广度优先遍历（BFS）

• 过程：
  
  
  
  • 从一个极点开始，逐层访问其所有邻接极点。
    
  • 访问完一层的所有极点后，再访问下一层的极点。
    
  
  
• 实现：
  
  
  
  • 使用队列来实现。
    
  • 标记已访问的极点，制止重复访问。
    
  
  
• 应用：
  
  
  
  • 用于寻找最短路径、检测图的连通性等。
    
  
  

最小天生树求取

Prim算法

• 过程：
  
  
  
  • 从恣意一个极点开始，将其加入天生树。
    
  • 在天生树的极点聚集中，选择一条毗连天生树和非天生树极点的最小权值边，将该边的非天生树极点加入天生树。
    
  • 重复上述步骤，直到所有极点都加入天生树。
    
  
  
• 实现：
  
  
  
  • 使用优先队列（最小堆）来优化选择最小权值边的过程。
    
  
  
• 应用：
  
  
  
  • 适用于稠密图，因为每次只必要选择一个极点。
    
  
  

Kruskal算法

• 过程：
  
  
  
  • 将图中的所有边按权值从小到大排序。
    
  • 依次选择权值最小的边，如果该边的两个极点不在同一个连通分量中，则将其加入天生树。
    
  • 重复上述步骤，直到天生树包含所有极点。
    
  
  
• 实现：
  
  
  
  • 使用并查集来检测连通分量。
    
  
  
• 应用：
  
  
  
  • 适用于奇怪图，因为每次只必要选择一条边.
    
  
  

这两种算法都可以有效地求取无向图的最小天生树，选择哪种算法取决于图的稠密程度和具体的应用场景。
二叉排序树（也称为二叉查找树或二叉搜索树）是一种特殊的二叉树，此中每个节点的值大于其左子树中所有节点的值，小于其右子树中所有节点的值。以下是关于二叉排序树的天生和查找的详细说明：
二叉排序树的天生

插入过程

• 步骤：
  
  
  • 初始化：从根节点开始。
    
  • 比力：将要插入的值与当前节点的值进行比力。
    
    
    
    • 如果要插入的值小于当前节点的值，则移动到当前节点的左子节点。
      
    • 如果要插入的值大于当前节点的值，则移动到当前节点的右子节点。
      
    
    
  • 递归：重复上述比力和移动过程，直到找到一个空的子节点位置。
    
  • 插入：在找到的空位置插入新节点。
    
  
  

示例

假设我们要将以下值依次插入到一个空的二叉排序树中：50, 30, 20, 40, 70, 60, 80。

• 插入 50：作为根节点。
  
• 插入 30：小于 50，插入到 50 的左子节点。
  
• 插入 20：小于 30，插入到 30 的左子节点。
  
• 插入 40：大于 30，插入到 30 的右子节点。
  
• 插入 70：大于 50，插入到 50 的右子节点。
  
• 插入 60：小于 70，插入到 70 的左子节点。
  
• 插入 80：大于 70，插入到 70 的右子节点。
  

终极天生的二叉排序树如下：

1.         50
2.        /  \
3.      30    70
4.     /  \  /  \
5.    20  40 60  80

复制代码

二叉排序树的查找

查找过程

• 步骤：
  
  
  • 初始化：从根节点开始。
    
  • 比力：将要查找的值与当前节点的值进行比力。
    
    
    
    • 如果要查找的值即是当前节点的值，则查找乐成，返回当前节点。
      
    • 如果要查找的值小于当前节点的值，则移动到当前节点的左子节点。
      
    • 如果要查找的值大于当前节点的值，则移动到当前节点的右子节点。
      
    
    
  • 递归：重复上述比力和移动过程，直到找到目标节点或到达空节点。
    
  • 查找失败：如果到达空节点，则表示查找失败，返回空。
    
  
  

示例

假设我们要在上述天生的二叉排序树中查找值 40。

• 从根节点 50 开始。
  
• 40 小于 50，移动到左子节点 30。
  
• 40 大于 30，移动到右子节点 40。
  
• 找到目标节点 40，查找乐成。
  

如果要查找值 45，则：

• 从根节点 50 开始。
  
• 45 小于 50，移动到左子节点 30。
  
• 45 大于 30，移动到右子节点 40。
  
• 45 大于 40，但 40 的右子节点为空，查找失败.
  

冒泡排序（Bubble Sort）

• 过程：
  
  
  • 比力相邻的元素，如果第一个元素大于第二个元素，就交换它们两个。
    
  • 对每一对相邻元素做同样的工作，从开始第一对到末端的末了一对，这步做完后，末了的元素会是最大的数。
    
  • 针对所有的元素重复以上的步骤，除了末了一个。
    
  • 连续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字必要比力。
    
  
  

选择排序（Selection Sort）

• 过程：
  
  
  • 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
    
  • 从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末端。
    
  • 重复第二步，直到所有元素均排序完毕。
    
  
  

插入排序（Insertion Sort）

• 过程：
  
  
  • 从第一个元素开始，该元素可以认为已经被排序。
    
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描。
    
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置。
    
  • 重复步骤3，直到找到已排序的元素小于大概即是新元素的位置。
    
  • 将新元素插入到该位置后。
    
  • 重复步骤2~5。
    
  
  

希尔排序（Shell Sort）

• 过程：
  1.选择一个增量序列 t1,t2,….,tk，此中 t> ti+1，且 tk =1。
  2.按增量序列个数 k，对序列进行 k 趟插入排序。
  3.每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处置处罚，表长度即为整个序列的长度
  

快速排序（Quick Sort）

• 过程：
  
  
  • 选择一个基准值（pivot），通常选择序列的第一个元素或末了一个元素。
    
  • 将所有比基准值小的元素放到基准前面，所有比基准值大的元素放到基准后面（雷同的数可以到任一边）。在这个分区退出之后，该基准就处于数组的中间位置。
    
  • 递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。
    
  
  

归并排序（Merge Sort）

• 过程：
  
  
  • 将序列每相邻两个数字进行归并操纵，形成 [n/2] 个序列，排序后每个序列包含两个元素。
    
  • 将上述序列再次归并，形成[n/4]个序列，每个序列大概包含四个元素。
    
  • 重复上述操纵，直到所有元素排序完毕。
    
  
  

堆排序（Heap Sort）

• 过程：
  
  
  • 将待排序序列构建成一个大顶堆，此时，整个序列的最大值就是堆顶元素。
    
  • 将堆顶元素与末端元素交换，将最大元素“沉”到数组末端。
    
  • 重新调整结构，使其满足堆界说，然后继续交换堆顶元素与当前末端元素，反复实行，直至整个序列有序。
    
  
  

基数排序（Radix Sort）

• 过程：
  
  
  • 将所有待比力数值同一为同样的数位长度，数位较短的数前面补零。
    
  • 从最低位开始，依次进行稳定排序（通常使用计数排序）。
    
  • 重复上述过程，直到最高位排序完成。
    
  
  

桶排序（Bucket Sort）

• 过程：
  
  
  • 设置一个定量的数组当作空桶。
    
  • 遍历输入数据，并且把数据根据其特征值放入对应的桶中。
    
  • 对每个不为空的桶进行排序，可以使用其他排序算法，大概递归地使用桶排序。
    
  • 按次序把桶中的数据拼起来。
    
  
  

哈希表是一种通过哈希函数将键（key）映射到值（value）的数据结构，具有高效的查找、插入和删除操纵。当哈希冲突发生时，必要采取肯定的解决方法。线性探测法和二次探测法是两种常用的解决哈希冲突的方法。
哈希表求取

• 选择哈希函数：
  
  
  
  • 哈希函数将键映射到哈希表中的一个索引位置。常见的哈希函数包括除法哈希、乘法哈希等。
    
  • 比方，除法哈希函数：hash(key) = key % table_size，此中 table_size 是哈希表的巨细。
    
  
  
• 处置处罚哈希冲突：
  
  
  
  • 当两个差别的键映射到同一个索引位置时，发生哈希冲突。必要采取肯定的方法解决冲突，如链表法、线性探测法、二次探测法等。
    
  
  

线性探测法

• 基本思想：
  
  
  
  • 当发生哈希冲突时，线性探测法从冲突位置开始，线性地向后探测，直到找到一个空的槽位。
    
  • 探测序列是线性的，即 h(key) + i，此中 i 是探测次数，从0开始递增。
    
  
  
• 插入过程：
  
  
  
  • 计算键的哈希值 h(key)。
    
  • 如果 h(key) 位置为空，则直接插入。
    
  • 如果 h(key) 位置已被占用，则从 h(key) 开始线性探测，直到找到一个空的槽位插入。
    
  
  
• 查找过程：
  
  
  
  • 计算键的哈希值 h(key)。
    
  • 从 h(key) 开始线性探测，直到找到目标键或探测到一个空槽位（表示查找失败）。
    
  
  

二次探测法

• 基本思想：
  
  
  
  • 当发生哈希冲突时，二次探测法从冲突位置开始，按照二次方的步长进行探测，直到找到一个空的槽位。
    
  • 探测序列是二次的，即 h(key) + i^2，此中 i 是探测次数，从1开始递增。
    
  
  
• 插入过程：
  
  
  
  • 计算键的哈希值 h(key)。
    
  • 如果 h(key) 位置为空，则直接插入。
    
  • 如果 h(key) 位置已被占用，则从 h(key) 开始二次探测，直到找到一个空的槽位插入。
    
  
  
• 查找过程：
  
  
  
  • 计算键的哈希值 h(key)。
    
  • 从 h(key) 开始二次探测，直到找到目标键或探测到一个空槽位（表示查找失败）。
    
  
  

优缺点比力

• 线性探测法：
  
  
  
  • 优点：实现简朴。
    
  • 缺点：轻易产生聚集现象，即多个键聚集在连续的槽位中，导致探测长度增长，性能降落。
    
  
  
• 二次探测法：
  
  
  
  • 优点：可以减少聚集现象，探测序列更加分散。
    
  • 缺点：实现相对复杂，且在某些环境下大概会探测到重复的位置（如当 i 和 j 的平方模 table_size 相等时）。
    
  
  

应用场景

• 线性探测法：适用于哈希表较小且负载因子较低的环境，因为聚集现象对性能的影响较小。
  
• 二次探测法：适用于哈希表较大且负载因子较高的环境，可以更好地分散键的分布，进步性能。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。