【数据结构】第七章：查找

本篇笔记课程来源：王道计算机考研 数据结构

一、基本概念

1. 概念

• 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
• 查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
  • 静态查找表：只查找符合条件的数据元素
  • 动态查找表：在查找元素的基础上还要插入、删除。除了查找速度，也要关注插 / 删操作是否方便实现。
• 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

2. 查找算法的效率评价

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度
• 平均查找长度（ASL，Average Search Length）：所有查找过程中进行关键字的比较次数的平均值。
  • 令数据元素个数为 $n$，查找第 i 个元素的概率为 $P_i$，查找第 i 个元素的查找长度为 $C_i$，则$$ASL=\sum _{i=1}^n{P}_i{C}_i$$
  • ASL 的数量级反应了查找算法时间复杂度
  • 评价一个查找算法的效率时，通常考虑查找成功 / 查找失败两种情况的 ASL

二、顺序查找

1. 算法思想

• 顺序查找，又叫线性查找，通常用于线性表。
• 算法思想：从头到尾依次查找。
• 时间复杂度：O(n)

2. 算法实现

• 一般方法：

  typedef struct {		// 查找表的数据结构（顺序表）ElemType *elem;		// 动态数组基址int TableLen;		// 表的长度
  } SSTable;// 顺序查找
  int Search_Seq(SSTable ST, ElemType key){int i;for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i);// 查找成功，则返回元素下标// 查找失败，则返回 -1return i == ST.TableLen ? -1 : i;
  }
  

• 哨兵方法：无需判断是否越界，效率更高。

  typedef struct {ElemType *elem;int TableLen;
  } SSTable;int Search_Seq(SSTable ST, ELemType key){ST.elem[0] = key;	// 0 号位置存 “哨兵”int i;// 从后往前查找for (i = ST.TableLen; ST.elem[i] != key; i--);// 查找成功，则返回元素下标// 查找失败，则返回 0return i;
  }
  

• $AS{L}_{成功}=\frac{1+2+3+...+n}{n}=\frac{n+1}{2}$

• $AS{L}_{失败}=n+1$

3. 算法优化

• 对有序表：
  • 当前关键字大于（或小于）目标关键字时，查找失败
  • 优点：查找失败时 ASL 更少，$AS{L}_{失败}=\frac{n}{2}+\frac{n}{n+1}$
  • 查找判定树：
    成功结点的关键字对比次数 = 结点所在层数；
    失败结点的关键字对比次数 = 其父节点所在层数。
• 若关键字被查概率不同：
  • 可按被查概率降序排列
  • 优点：查找成功时 ASL 更少

三、折半查找

1. 算法思想

• 折半查找：又称二分查找，仅适用于有序的顺序表。

2. 算法实现

typedef struct {		// 查找表的数据结构（顺序表）ElemType *elem;		// 动态数组基址int TableLen;		// 表的长度
} SSTable;// 折半查找
int Binary_Search(SSTable L, ElemType key){int low = 0, high = L.TableLen - 1, mid;while (low <= high) {mid = (low + high) / 2;		// 取中间位置if (L.elem[mid] == key)return mid;				// 查找成功则返回所在位置else if (L.elem[mid] > key)high = mid - 1;			// 从前半部分继续查找elselow = mid + 1;			// 从后半部分继续查找}return -1;						// 查找失败，返回 -1
}

3. 查找判定树

• 构造判定树：
  • 如果当前 low 和 high 之间有奇数个元素，则 mid 分割后，左右两部分元素个数相等
  • 如果当前 low 和 high 之间有偶数个元素，则 mid 分割后，左半部分比右半部分少一个元素
  • 若 $mid=\lfloor (low+high)/2\rfloor$，则对于任何一个结点，必有：右子树节点数 - 左子树节点数 = 0 或 1
  • 若 $mid=\lceil (low+high)/2\rceil$，则对于任何一个结点，必有：左子树节点数 - 右子树节点数 = 0 或 1
• 折半查找的判定树性质：
  1. 右子树节点数 - 左子树节点数 = 0 或 1
  2. 折半查找的判定树只有最下面一层是不满的，且一定是平衡二叉树，因此元素个数为 n 时树高 $h=\lceil lo{g}_2(n+1)\rceil$
  3. 判定树结点关键字：左 < 中 < 右，满足二叉排序树的定义。失败结点数量为 n+1 个（等于成功结点的空链域数量）

4. 折半查找效率

• 若有 n 个元素，则树高 $h=\lceil lo{g}_2(n+1)\rceil$
• 时间复杂度为 $O(lo{g}_{2}n)$

四、分块查找

1. 算法思想

• 分块查找，又称 索引顺序查找，算法过程如下：
  1. “索引表” 中保存每个分块的最大关键字和分块的存储区间，在索引表中确定待查记录所属的分块（可顺序、可折半）
     • 若采用折半查找索引表，索引表中不包含目标关键字，当 low > high 时，要在 low 所指分块中查找
     • 若采用折半查找索引表，low 超出索引表范围，则查找失败
  2. 在块内顺序查找
• 特点：块内无序，块间有序

2. 数据结构

• 顺序存储：

  typedef struct {		// 索引表ElemType maxValue;	// 分块最大关键字int low, high;		// 区间左右索引号
  } Index;ElemType List[100];		// 顺序表存储实际元素
  

• 若查找表是 “动态查找表”，则可以采用链式存储。

3. 查找效率分析

假设，长度为 n 的查找表被均匀地分为 b 块，每块 s 个元素。设索引查找和块内查找的平均查找长度分别为 $L_I、L_S$，则分块查找的平均查找长度为：$$ASL=L_I+L_S$$

• 用顺序查找查索引表，则 $L_I=\frac{1+2+...+b}{b}=\frac{b+1}{2}$，$L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2}$，则 $ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}$，当 $s=\sqrt{n}时$，$AS{L}_{最小}=\sqrt{n}+1$
• 用折半查找查索引表，则 $L_I=\lceil lo{g}_2(b+1)\rceil ，L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2}$，则 $ASL=\lceil lo{g}_2(b+1)\rceil +\frac{s+1}{2}$

五、二叉排序树

1. 定义

• 二叉排序树，又称二叉查找树（BST，Binary Search Tree），具有以下性质：
  • 左子树上所有结点的关键字均小于根结点的关键字
  • 右子树上所有结点的关键字均大于根结点的关键字
  • 左子树和右子树又各是一颗二叉排序树
• 二叉排序树可用于元素的有序组织、搜索，对一个二叉排序树进行中序遍历，可以得到一个递增的有序序列。
• 二叉排序树结点

  typedef struct BSTNode {int key;BSTNode *lchild, *rchild;
  } BSTNode, *BSTree;
  

2. 查找操作

• 若树非空，目标值与根结点的值比较：

  1. 若相等，则查找成功，返回结点指针
  2. 若小于根结点，则在左子树上查找，否则在右子树上查找
  3. 查找失败返回 NULL

• 在二叉排序树中查找值为 key 的结点，最坏空间复杂度 O(1)

  BSTnode *BST_Search(BSTree T, int key){while (T != NULL && key != T->key){		// 若树空或等于根节点值，则结束循环if (key < T->key)					//小于，在左子树上查找T = T->lchild;else								// 大于，在右子树上查找T = T->rchild;	}return T;
  }
  

• 递归实现，最坏空间复杂度 O(h)

  BSTNode *BST_Search(BSTree T, int key){if (T == NULL)return NuLL;						// 查找失败if (key == T->key)return T;							// 查找成功else if (key < T->key)return BST_Search(T->lchild, key);	// 在左子树上查找elsereturn BST_Search(T->rchild, key);	// 在右子树上查找
  }
  

3. 插入操作

• 插入：
  1. 若原二叉排序树为空，则直接插入结点
  2. 若非空，当关键字 k 小于根结点值，则插入到左子树；当关键字 k 大于根结点值，则插入到右子树
• 递归实现，最坏时间复杂度 O(h)

  int BST_Insert(BSTree &T, int k){if (T == NULL){						// 原树为空，插入新节点T = (BSTree)malloc(sizeof(BSTNode));T->key = k;T->lchild = T->rchild = NULL;return 1;						// 插入成功，返回 1}else if (k == T->key)return 0;						// 存在相同关键字的结点，插入失败else if (k < T->key)return BST_Insert(T->lchild, k);// 插入到 T 的左子树elsereturn BST_Insert(T->rchild, k);// 插入到 T 的右子树
  }
  

• 构造二叉排序树，实际上就是一直插入

  void Creat_BST(BSTree &T, int str[], int n){T == NULL;			// 初始时 T 为空树int i = 0;while (i < n) {		// 依次将每个关键字插入到二叉排序树中BST_Insert(T, str[i]);i++;	}
  }
  

• 不同的关键字序列可能得到相同的二叉排序树，也可能得到不同的二叉排序树。

4. 删除操作

删除操作，三种情况：

1. 若被删除结点 z 是叶子结点，则直接删除，不会破坏二叉排序树的性质
2. 若结点 z 只有一颗左子树或右子树，则让 z 的子树成为 z 父节点的子树，替代 z 的位置。
3. 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个后继（或直接前驱），这样就转换成了第一或第二种情况。
   • z 的后继：z 的右子树最左下结点（该节点一定没有左子树）
   • z 的前驱：z 的左子树最右下结点（该节点一定没有右子树）

5. 查找效率分析

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
• 最好情况：n 个结点的二叉树最小高度为 $\lfloor lo{g}_{2}n\rfloor +1$，平均查找长度 = $O(lo{g}_{2}n)$
• 最坏情况：每个结点只有一个分支，树高 h = 节点数 n。平均查找长度 = $O(n)$

六、平衡二叉树

1. 定义

• 平衡二叉树（Balanced Binary Tree），简称平衡树（AVL 树）：树上任一结点的左子树和右子树的高度之差不超过 1（只可能是 -1、0、1）。
  • 结点的平衡因子 = 左子树高 - 右子树高。
• 平衡二叉树结点

  typedef struct AVLNode{int key;		// 数据域int balance;	// 平衡因子AVLNode *lchild, *rchild;
  } AVLNode, *AVLTree;
  

2. 插入操作

• 在二叉排序树中插入新节点后，查找路径上的所有节点都有可能受到影响。
• 最小不平衡子树：从插入点往回找到的第一个不平衡结点，以该节点为根的子树。
• 在插入操作后，只要将不平衡子树调整平衡，则其他祖先节点都会回复平衡。

3. 调整不平衡问题

• 四种情况：
  1. LL：在 A 的左节点的左子树中插入导致不平衡
  2. RR：在 A 的右节点的右子树中插入导致不平衡
  3. LR：在 A 的左节点的右子树中插入导致不平衡
  4. RL：在 A 的右节点的左子树中插入导致不平衡

---

1. LL 平衡旋转（右单旋转）：
   

   • 由于在结点 A 的左节点（L）的左子树（L）上插入新节点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。
   • 将 A 的左孩子 B 向右上旋转代替 A 称为根结点，将 A 结点向右下旋转称为 B 的右子树的根结点，B 的原右子树则作为 A 结点的左子树。

   f->lchild = p->rchild;
   p->rchild = f;
   gf->lchild/rchild = p;
   

---

2. RR 平衡旋转（左单旋转）：
   

   • 由于在结点 A 的右节点（R）的右子树（R）上插入新节点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。
   • 将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，B 的原左子树则作为 A 结点的右子树。

   f->rchild = p->lchild;
   p->lchild = f;
   gf->lchild/rchild = p;
   

---

3. LR 平衡旋转（先左后右双旋转）：
   

   • 由于在 A 的左节点（L）的右子树（R）上插入新节点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
   • 先将 A 结点的左节点 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置。

---

4. RL 平衡旋转（先右后左双旋转）：
   
   • 由于在 A 的右节点（R）的左子树（L）上插入新节点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
   • 先将 A 结点的右节点 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置。

4. 查找效率分析

• 假设以 $n_h$ 表示深度为 h 的平衡树中含有的最少节点数，则有$$n_0=0,n_1=1,n_2=2$$并且有 $$n_h=n_{h-1}+n_{h-2}+1$$可以证明含有 n 个结点的平衡二叉树的最大深度为 $O(lo{g}_{2}n)$，平衡二叉树的平均查找长度为 $O(lo{g}_{2}n)$

5. 删除操作

1. 删除结点（方法同 “二叉排序树”）
   • 若删除的结点是叶子结点，直接删除
   • 若删除的结点只有一个子树，用子树顶替删除位置
   • 若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除
2. 一路向北找到最小不平衡子树，找不到就完结撒花
3. 找最小不平衡子树下，“个头” 最高的儿子、孙子
4. 根据孙子的位置，调整平衡（LL、RR、LR、RL）
   • 孙子在 LL：儿子右单旋
   • 孙子在 RR：儿子左单旋
   • 孙子在 LR：孙子先左旋，再右旋
   • 孙子再 RL：孙子先右旋，再左旋
5. 如果不平衡向上传导，继续 ②
   • 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）

七、红黑树

1. 定义和性质

• 红黑树（RBT）是一种二叉排序树（左根右），和普通的二叉排序树相比：
  1. 每个结点或是红色，或是黑色
  2. 根结点是黑色的
  3. 叶节点（外部节点、NULL结点、失败节点）均是黑色的（根叶黑）
  4. 不存在两个相邻的红节点（即红节点的父节点和孩子结点均是黑色）（不红红）
  5. 对每个结点，从该节点到任一叶节点的简单路径上，所含黑节点的数目相同（黑路同）
     • 结点的黑高 bh：从某节点出发（不含该节点）到达任一空叶节点的路径上黑节点总数
     • 若根结点黑高为 h，则内部节点数（关键字）最少有 $2^h-1$ 个（满树状态）
• 红黑树的性质：
  1. 从根结点到叶节点的最长路径不大于最短路径的 2 倍
  2. 有 n 个内部结点的红黑树高度 $h\le 2lo{g}_2(n+1)$
• 红黑树的结点定义

  struct RBNode {int key;		// 关键字的值RBNode *parent;	// 父节点指针RBNode *lchild;	// 左孩子指针RBNode *rchild;	// 右孩子指针int color;		// 结点颜色
  }
  

2. 插入操作

1. 先查找，确定插入位置（原理同二叉排序树），插入新节点
2. 新节点是根，染为 黑色
3. 新节点非根，染为 红色
   • 若插入新节点后依然满足红黑树定义，则插入结束
   • 若插入新节点后不满足红黑树定义（违反不红红），则需要看新节点叔叔的颜色：
     • 叔叔是黑色：旋转+染色
       1. LL：右单旋，父换爷 + 染色
       2. RR：左单旋，父换爷 + 染色
       3. LR：左、右双旋，儿换爷 + 染色
       4. RL：右、左双旋，儿换爷 + 染色
     • 叔叔是红色：染色+变新
       1. 叔父爷染色，爷变为新节点

3. 删除操作

• 红黑树的删除操作时间复杂度为 $O(lo{g}_{2}n)$
• 在红黑树中删除结点的操作方式和 “二叉排序树的删除” 一样
• 按 ② 删除节点后，可能破坏红黑树特性，此时需要调整结点颜色、位置，使其再次满足红黑树特性。

八、B 树

1. 定义和性质

• B 树（Balance Tree），又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。一颗 m 阶 B 树或为空树，或为满足如下特性的 m 叉树：
  1. 树中每个结点最多有 $m$ 颗子树，即最多含有 $m-1$ 个关键字
  2. 若根结点不是终端结点，则至少有两颗子树。
  3. 除根结点外的所有非叶节点至少有 $\lceil m/2\rceil$ 颗子树，即至少含有 $\lceil m/2\rceil -1$ 个关键字
  4. 所有非叶节点的结构如下：$$n,P_0,K_1,P_1,K_2,P_2,...,K_n,P_n$$其中，$K_i(i=1,2,...,n)$ 为结点的关键字，且满足 $K_1<K_2<...<K_n$；$P_i(i=1,2,...,n)$ 为指向子树根结点的指针，且指针$P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$，$P_i$ 所指子树中所有的关键字均大于 $K_i$，$n（\lceil m/2\rceil -1\le n\le m-1）$为结点中关键字的个数。
  5. 所有的叶节点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
• m 阶 B 树的核心特性：
  1. 根结点的子树数 $\in [2,m]$，关键字数 $\in [1,m-1]$
     其他结点的子树数 $\in [\lceil m/2\rceil ,m]$，关键字数 $\in [\lceil m/1\rceil -1,m-1]$
  2. 对任一结点，其所有子树高度都相同
  3. 关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < …（类比二叉查找树 左 < 中 < 右）
• 含 n 个关键字的 m 阶 B 树
  • 最小高度：让每个结点尽可能的满，有 m-1 个关键字，m 个分叉，则有$$n\le (m-1)(1+m+m^2+m^3+...+m^{h-1})=m^h-1$$因此 $$h\ge lo{g}_m(n+1)$$
  • 最大高度：让各层的分叉尽可能的少，即根结点只有 2 个分叉，其他结点只有 $\lceil m/2\rceil$ 个分叉，n 个关键字的 B 树必有 n+1 个叶子结点，则 $$n+1\ge 2(\lceil m/2\rceil {)}^{h-1}$$即$$h\le lo{g}_{\lceil m/2\rceil }\frac{n+1}{2}+1$$
• n 阶 B 树的结点定义

  #define n 5struct Node {ElemType keys[n - 1];	// 最多 n-1 个关键字Node * child[n];		// 最多 n 个孩子int num;				// 结点中有几个关键字
  }
  

2. 插入操作

• 核心要求：
  1. 对 m 阶 B 树 —— 除根节点外，结点关键字个数为 $\lceil m/2\rceil -1\le n\le m-1$
  2. 子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < …
• 插入步骤：
  1. 新元素一定是插入到最底层 “终端结点”，用 “查找” 来确定插入位置
  2. 在插入 key 后，若导致原结点关键字树超过上限，则从中间位置（$\lceil m/2\rceil$）将其中的关键字分为两部分：
     • 左部分包含的关键字放在原结点中
     • 右部分包含的关键字放在新节点中
     • 中间位置（$\lceil m/2\rceil$）的结点插入原结点的父节点
  3. 若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直到这个过程传到根结点位置，进而导致 B 树高度增 1。

3. 删除操作

• 核心要求和插入操作一样
• 删除的情况：
  1. 如果是非终端结点关键字：
     • 用其直接前驱（后继）代替其位置，转化为对 “终端结点” 的删除
  2. 如果是终端结点关键字：
     • 删除后结点关键字数未低于下限（$\lceil m/2\rceil -1$），无需任何处理
     • 删除后如果低于下限：
       1. 右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
       2. 左兄弟够借，则用当前节点的前驱、前驱的前驱依次顶替空缺
       3. 左（右）兄弟都不够借，则需要与父节点内的关键字、左（右）兄弟进行合并。合并后导致父节点关键字数量 -1，可能需要继续合并。

九、B+树

1. 定义

• 一颗 m 阶的 B+ 树需满足下列条件：
  1. 每个分支结点最多有 m 颗子树（孩子结点）
  2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 $\lceil m/2\rceil$ 颗子树
  3. 结点的子树个数和关键字个数相等（与 B 树的区别）
  4. 所有叶结点包含全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）
  5. 所有分支结点中仅包含它的各个子节点中关键字的最大值及指向其子节点的指针（类似于分块查找）

2. 查找

• 在 B+ 树中，无论查找成功与否，最终一定都要走到最下面一层结点

3. 与 B 树对比

	m 阶 B 树	m 阶 B+ 树
类比	二叉查找树的进化 → m 叉查找树	分块查找的进化 → 多级分块查找
关键字与分叉	n 个关键字对应 n+1 个分叉（子树）	n 个关键字对应 n 个分叉
结点包含的信息	所有结点中都包含记录的信息	只有最下层叶子结点才包含记录的信息（可使树变矮）
查找方式	不支持顺序查找。查找成功时，可能停在任何一层结点，查找速度 “不稳定”	支持顺序查找。查找成功或失败都会到达最下一层结点，查找速度 “稳定”
相同点	除根结点外，最少 ⌈m/2⌉ 个分叉（确保结点不要太 "空"） 任何一个结点的子树都要一样高（确保 "绝对平衡"）

十、散列表

1. 定义和基本概念

• 散列表（哈希表，Hash Table）：是一种数据结构，特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址
• 散列函数（哈希函数）：Addr=H(Key) 建立了 “关键字”→“存储地址” 的映射关系
• 冲突（碰撞）：在散列表中插入一个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为冲突（碰撞）
• 同义词：若不同的关键字通过散列函数映射到同一个存储地址，则称它们为“同义词”

2. 构造散列函数

• 核心目标：散列函数要尽可能地减少 “冲突”
• 应注意的问题：
  1. 定义域必须涵盖所有可能出现的关键字
  2. 值域不能超出散列表的地址范围
  3. 尽可能减少冲突，散列函数计算出来的地址应尽可能均匀分布在整个地址空间
  4. 散列函数应尽量简单，能够快速计算出任意一个关键字对应的散列地址
• 常用散列函数构造方法
  1. 除留余数法
  2. 直接定址法
  3. 数字分析法
  4. 平方取中法

---

• 除留余数法：
  • 散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p。对质数取余，可以分布更均匀，从而减少冲突。
  • 适用场景：较为通用，只要关键字是整数即可
  • $H(key)=key$ % $p$
• 直接定址法
  • 计算最简单，且不会产生冲突
  • 若关键字分布不连续，空位较多，则会造成存储空间的浪费
  • 适用场景：关键字分布基本连续
  • $H(key)=key$ 或 $H(key)=a\times key+b$（$a$ 和 $b$ 是常数）
• 数字分析法
  • 设关键字是 r 进制数（如十进制数），而 r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。
  • 适用场景：关键字集合已知，且关键字的某几个数码位分布均匀
• 平方取中法
  • 具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀
  • 适用场景：关键字的每位取值都不够均匀

3. 处理冲突的方法

• 拉链法：
  • 又称链接法、链地址法，把所有同义词存储在一个链表中
  • 插入操作：
    1. 结合散列函数计算新元素的散列地址
    2. 将新元素插入散列地址对应的链表（默认头插法）
  • 查找操作：
    1. 结合散列函数计算新元素的散列地址
    2. 顺序查找链表，查找长度为在查找运算中，需要对比关键字的次数
  • 删除操作：
    1. 结合散列函数计算新元素的散列地址
    2. 顺序查找链表，删除目标元素
• 开放定址法
  • 开放定址：一个散列地址，既对同义词开放，也对非同义词开放
  • 基本思想：如果发生冲突，就给新元素找另一个空闲位置
  • 思路：需确定一个探测的顺序，从初始散列地址出发，取寻找下一个空闲位置
  • $H_i$ 表示第 $i$ 次冲突时的散列地址；
    $H(key)$ 表示初始散列地址；
    $d_i$ 表示第 $i$ 次发生冲突时，下一个探测地址与初始散列地址的相对偏移量，$d_0=0$；
    $m$ 表示散列表表长$$H_i=(H(key)+d_i)\%m\text{\hspace{1em}(0≤i≤m−1)}$$
  • 四种常用方法构造探测序列 $d_i$：
    1. 线性探测法：$d_i=0,1,2,3,...,m-1$
    2. 平方探测法：$d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2$
    3. 双散列法：$d_i=i\times has{h}_2(key)$
    4. 伪随机序列法：$d_i$ 是一个伪随机序列，假设 $d_i=0,5,3,11,...$
  • 查找操作：
    • 根据探测序列依次对比各存储单元内的关键字。
    • 若探测到目标关键字，则查找成功
    • 若探测到空单元，则查找失败
  • 删除操作：
    • 先根据散列函数算出散列地址，并对比关键字是否匹配。若匹配，则查找成功
    • 若关键字不匹配，则根据探测序列对比下一个地址的关键字，直至查找成功或查找失败
    • 若查找成功，则删除找到的元素
    • 注意：删除元素不能简单地删元素的空间置为空，否则将截断在它之后的探测路径，可以做一个 “已删除” 标记，进行逻辑删除