数据结构之查找

数据结构之查找

第七章_查找

7.1 查找的基本概念

• 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
• 查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，不一定只用于查找，还可用于增加/删除等操作。查找表并不是一个单一的数据结构，可以是图、树、线性表…
• 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
• 静态查找表： 查找表在使用期间数据元素固定不变，仅支持查找操作，不进行频繁的插入或删除。
• 动态查找表： 查找表在使用期间数据元素可以动态增加或删除，支持查找、插入和删除等操作。
• 查找长度： 在查找运算中，需要对比关键字的次数称为查找长度
• 平均查找长度（ASL, Average Search Length）： 所有查找过程中进行关键字的比较次数的平均值，ASL 是各元素查找长度与其被查找概率（默认各元素相同）的加权平均值，其数学定义为： $$ \text{ASL} = \sum_{i=1}^{n} L_i \cdot p_i $$ 默认情况为： $$ \text{ASL} = \frac{1}{n} \sum_{i=1}^{n} L_i $$ 查找表中有 n 个元素，第 i 个元素查找长度为 L_i ，查找概率为 P_i（各元素之和为 1），ASL 是衡量查找算法效率的核心指标。

7.2 线性表查找

线性表查找指 “查找表” 是线性表的查找。

7.2.1 顺序查找

所谓顺序查找，就是我们最熟悉的从头到尾去挨个匹配关键字。

7.2.1.1 一般顺序查找

普通顺序查找的实现方式很简单，代码如下：

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); //判断是否越界，判断是否查找成功
    //查找成功，则返回元素下标；查找失败，则返回-1
    return i==ST.TableLen? -1 : i;
}

7.2.1.2 哨兵模式顺序查找

我们将待查找的关键字放在数组下标为 0 的位置，数据从下标为 1 的位置开始存储，从后往前顺序查找。这样便不用每次都判断是否越界，因为遍历到下标为 0 的位置会自动停下来。我们将下标为 0 位置对应元素称之为哨兵，实现代码如下：

typedef struct{
    ElemType *elem;  //这里可以用动态数组的方式实现，省略了一些代码
    int TableLen;
}SSTable;

//顺序查找（哨兵优化版）
int Search_Seq(SSTable ST, ElemType key) {
    ST.elem[0] = key;  // "哨兵"
    int i;
    for (i = ST.TableLen; ST.elem[i] != key; --i);  // 从后往前找
    return i;  // 查找成功，则返回元素下标；查找失败，则返回0
}

实际上，哨兵模式只是对顺序查找的代码结构进行了优化，减少了边界判断的次数，但在最坏、平均以及最好情况下，其时间复杂度与普通顺序查找并无本质区别，均为 O(n)。其查找效率（ASL 与一般顺序查找一样）分析如下图所示：

7.2.1.3 有序线性表顺序查找

对于有序线性表，可以在查找过程中通过比较关键字的大小关系，一旦发现不可能再出现匹配元素，即可判定查找失败或成功。代码如下：

typedef struct {
    ElemType *elem;   // 动态数组
    int TableLen;
} SSTable;

// 有序顺序查找（升序）
int Search_Seq_Ordered(SSTable ST, ElemType key) {
    int i = 0;
    // 只要当前元素 <= key，就还有继续查找的必要
    while (i < ST.TableLen && ST.elem[i] < key) {
        i++;
    }

    // 判断是否查找成功
    if (i < ST.TableLen && ST.elem[i] == key)
        return i;      // 查找成功
    else
        return -1;     // 查找失败
}

值得注意的是，对于求取有序线性表的 ASL 我们一定要学会画查找判定树，示意图如下：

7.2.1.4 查找概率不相等的顺序查找

对于查找概率不相等的顺序查找，我们可以将概率较大的元素放在前面，这样优化了 ASL_成功 ，但是对于本来有序的线性表，将其打乱了顺序，其 ASL_失败 又回到了一般顺序查找的 n + 1 。示意图如下：

7.2.2 折半查找

7.2.2.1 折半查找实现

折半查找也叫做二分查找，只适用于有序的顺序表。 折半查找的概念很简单，我就不多做赘述了，看代码也能看懂。值得注意的是它查找失败的判定条件是 high < low，第一次接触可能难懂，找个例子推导一下就清晰了。

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;     // 从前半部分继续查找
        else
            low=mid+1;      // 从后半部分继续查找
    }
    return -1;  // 查找失败，返回-1
}

时间复杂度为 log₂n，效率显著高于顺序查找。

7.2.2.2 折半查找性质

对于折半查找判定树有这些性质：

1. 折半查找判定树一定是平衡二叉树，但可不是二叉排序树。
2. n 个成功结点一定有 n + 1 个失败结点（这也是所有判定树的性质，也与线索二叉树相关）。
3. 具有 n 个成功结点的查找判定数高度为 log₂(n + 1)（二叉树的性质）

7.2.2.3 折半查找判定树

对于查找有序的查找表，一定要学会画它的查找判定树用来找它的 ASL，折半查找的查找判定树示意图如下：

7.2.3 分块查找

7.2.3.1 分块查找的概念

分块查找又称索引顺序查找，它结合了顺序查找以及折半查找各自的优点。 分块查找的基本思想是：将查找表分为若干子块。块内元素可以无序，块间元素必须有序。同时建立一个索引表，其中每个元素包含对应块的最大关键字和该块的起始地址，索引表按最大关键字有序排列。查找时先通过索引表确定待查关键字所在的块，再在块内进行顺序查找。 示意图如下：

7.2.3.2 分块查找的使用

由于在考研中分块查找的代码实现基本不考，所以这里仅介绍分块查找过程。 显而易见，对于索引表我们可以使用二分查找和顺序查找，对于块内元素（无序），我们只能使用顺序查找。

那么较难理解的就是如何对索引表使用二分查找以确定下一步在哪个块内查询？其实很简单，无论什么情况 low 指针所指向的索引项对应的块包含下一步可能进行顺序查找的元素。 如果指向超出索引表范围，就说明查找失败。示意图如下：

7.2.3.4 分块查找求 ASL

对于 ASL_失败 这种情况，很复杂，考研也不考，就不介绍了。 对于 ASL_成功 这种情况，索引表使用顺序查找我们可以很轻松的算到每个元素的查找长度；而索引表使用二分查找，我们利用二分查找判定树，也能很轻松的求出每个元素的查找长度。但是对于平均查找长度（ASL)，需要求取每个元素的查找长度，貌似两种情况都有些计算量太大了，没办法只能算（考研可能会给些计算量小的）。 示意图如下： 那么分块查找的 ASL 在平均意义（各块中元素被查找的概率相同或者块大小相同、关键字分布均匀）下还有一个性质： 分块查找的 ASL = 索引查找的 ASL + 块内查找的 ASL 示意图如下：

7.3 树形查找

7.3.1 二叉排序树

7.3.1.1 二叉排序树的概念

二叉排序树（BST）又称为二叉查找树，具有左子树结点值 < 根结点值 < 右子树结点值，显然，对二叉排序树使用中序遍历就能得到一个有序的序列。示意图如下：

7.3.1.2 二叉排序树的查找

对二叉排序树进行结点的查找也是非常简单的，两种实现代码如下：

//在二叉排序树中查找值为 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;  //查找失败返回的就是 NULL
}

//数据有递归的性质，自然也能用递归来进行实现
//在二叉排序树中查找值为 key 的结点（递归实现，最坏空间复杂度O(h)，h是树的高度）
BSTNode *BSTSearch(BSTree T,int key){
    if (T==NULL)
        return NULL;    //查找失败
    if (key==T->key)
        return T;       //查找成功
    else if (key < T->key)
        return BSTSearch(T->lchild, key);  //在左子树中找
    else
        return BSTSearch(T->rchild, key);  //在右子树中找
}

7.3.1.3 二叉排序树的插入

对排序二叉树的插入操作实现代码如下：

//在二叉排序树插入关键字为k的新结点（递归实现）
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)                 //插入到T的左子树
        return BST_Insert(T->lchild,k);
    else                             //插入到T的右子树
        return BST_Insert(T->rchild,k);
}

7.3.1.4 二叉排序树的构造

构造就是不断往二叉树中插入结点的过程，实现代码如下：

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

7.3.1.5 二叉排序树的删除

二叉排序树的删除分为以下三种情况：

1. 被删除结点是叶结点，直接删除即可。
2. 被删除结点仅有一棵非空子树（左子树和右子树），则将其唯一的子树上移作为被删除结点的双亲结点的新子树。
3. 若被删除结点 z 同时具有两棵子树，则可使用 z 的直接后继或直接前驱（是中序遍历的上一个和下一个结点！）来代替 z 。替换完成之后还要删除直接前驱或者直接后继结点，由于直接前驱或者直接后继至多只会有一个子树，这样就转换成了第一或者第二种情况，

7.3.1.6 二叉排序树的查找效率

不论查找成功还是失败其 ASL 很大程度上取决于二叉排序树的高度，下面是关于 ASL_成功 和 ASL_失败 的两张示意图：

7.3.2 平衡二叉树

7.3.2.1 平衡二叉树的概念

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL 树，发明人名字缩写）—— 树上任一结点的左子树和右子树的高度之差不超过 1。平衡二叉树是为了避免二叉排序树的高度增长过快而导致性能下降而定义的一种树，所以平衡二叉树一定是二叉排序树

平衡因子的概念：平衡因子 = 左子树高度 - 右子树高度。平衡二叉树中所有结点的平衡因子只能是 -1，0，1。

最小不平衡子树：在插入操作中，每次插入都会对各结点的平衡因子造成影响，当开始存在失衡结点时。距离新结点最近且以平衡因子绝对值大于 1 的结点为根结点的子树称为最小不平衡子树，如图所示：

7.3.2.2 平衡二叉树的插入

对平衡二叉树进行插入操作可能会出现失衡现象和破坏二叉排序树的特性，那我们如何让他变得平衡呢且不破坏特性呢？其实我们只需要对最小不平衡子树进行操作，将最小不平衡子树变的平衡，那么整棵树都会变得平衡。我们把导致失衡的情况分为以下四种，对不同的情况有不同的处理方式：

• LL —— 在A的左孩子的左子树中插入导致不平衡
• RR —— 在A的右孩子的右子树中插入导致不平衡
• LR —— 在A的左孩子的右子树中插入导致不平衡
• RL —— 在A的右孩子的左子树中插入导致不平衡

这四种情况的处理方式不仅能够保持平衡，也能保持二叉排序树的特性。 下方四种情况介绍图中，我们将结点 A 作为固定的最小不平衡子树的根结点，将所有子树的高度都设置为 h （这是为了保证 A 在插入操作后必定作为根结点）。当然实际情况需具体确定根结点位置。

LL平衡旋转（右单旋转）: 其代码的指针移动顺序是这样的：

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

RR平衡旋转（左单旋转）： 其代码的指针移动顺序是这样的：

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

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

7.3.2.3 平衡二叉树的查找效率分析

具有 n 个结点的平衡二叉树的平均查找长度为log₂n，推导过程如下： 具有 n 个结点的平衡二叉树的最大高度也为log₂n，这个证明很复杂，记住就好。

7.3.2.3 平衡二叉树的删除

平衡二叉树的删除思想和插入目标是一样的，都是需要：

1. 保持二叉树的平衡
2. 保持二叉排序树的特性

插入操作在上面 7.3.1 小节已经说过三种情况了。这里将介绍如何在删除操作之后保持平衡和特性。步骤如下：

1. 删除结点。
2. 一路向北找到最小不平衡子树，找不到就完结撒花。
3. 找最小不平衡子树下，“个头” 最高（以其为根结点的树高度最高）的儿子、孙子。
4. 根据孙子的位置，调整平衡（LL/RR/LR/RL）。
5. 如果不平衡向上传导，继续步骤 2 （从被调整子树的根出发，一路向北…）

光看文字有点懵，这里我举一个完整的例子：

7.3.3 红黑树

7.3.3.1 为什么要引入红黑树

平衡二叉树 AVL： 1962 年提出，插入 / 删除很容易破坏 “平衡” 特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行 LL/RR/LR/RL 调整。 红黑树 RBT： 1972 年被提出，插入 / 删除很多时候不会破坏 “红黑” 特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成。

因此，AVL 树适用于以查为主，很少增 / 删的场景。红黑树 RBT 适用于频繁增 / 删的场景，实用性更强。也条件更加宽松（左右子树最大高度差不同）。

7.3.3.2 红黑树的概念

红黑树肯定是一个二叉排序树，相较于 BST， 红黑树有这些要求（左根右，根叶黑，不红红，黑路同）：

1. 每个结点或是红色，或是黑色的
2. 根节点是黑色的
3. 叶结点（或叫做：外部结点、NULL 结点、失败结点）均是黑色的
4. 不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色的）
5. 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

红黑树的示意图和每个结点的实现代码如下：

struct RBnode {    // 红黑树的结点定义
    int key;       // 关键字的值
    RBnode* parent; // 父节点指针
    RBnode* lchild; // 左孩子指针
    RBnode* rchild; // 右孩子指针
    int color;      // 结点颜色，如：可用 0/1 表示黑/红，也可使用枚举型enum表示颜色
};

7.3.3.3 红黑树的查找

红黑树的查找很简单，和 AVL，BST 是一样的。因为内部有 n 个结点的红黑树高度 h <= 2 log₂ (n + 1)，自然其查找的时间复杂度也是 O(log₂n) ，示意图如下：

7.3.3.4 红黑树的插入

为了维持红黑树的特性，红黑树中结点进行插入的规则如下：

• 先查找，确定插入位置（原理同二叉排序树），插入新结点
  • 新结点是根 —— 染为黑色
  • 新结点非根 —— 染为红色（防止破坏“黑路同”）
    • 若插入新结点后依然满足红黑树定义（一般就判断一下“不红红”），则插入结束
    • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义，如何调整：看新结点叔叔的脸色
      • 黑叔： 旋转 + 染色
        • LL 型：右单旋，父换爷 + 父爷染色
        • RR 型：左单旋，父换爷 + 父爷染色
        • LR 型：左、右双旋，儿换爷 + 儿爷染色
        • RL 型：右、左双旋，儿换爷 + 儿爷染色
      • 红叔： 染色 + 变新
        • 叔父爷染色，爷变为新结点（再回到上面新结点的判断）

如果从一棵空的红黑树依次插入如下结点，基本就能覆盖所有情况：20,10,5,30,40,57,3,2,4,35,25,18,22,23,24,19,18。这里举例过程中几个易错过程。

7.3.3.5 红黑树的删除

红黑树的删除比插入还要难，作者不管了嘿嘿。 重要考点：

1. 红黑树删除操作的时间复杂度 = $O(\log_2 n)$
2. 在红黑树中删除结点的处理方式和“二叉排序树的删除”一样
3. 按步骤二删除结点后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满足“红黑树特性”。

7.4 B 树 和 B+ 树

7.4.1 B 树

7.4.1.1 B 树的概念

m 阶 B 树是一种自平衡的 m 路查找树，其所有叶结点都位于同一层次。示意图如下： 那么为什么 B 树要规定这么多特性？这些特性的规定有什么原因？

• 性质 1 ： m 阶树中么个结点至多有 m 棵子树，即至多含有 m-1 个关键字。 m 阶就是最多能是 m 叉树，m-1 能划分出 m 个区间。这里以 5 叉树举例示意如下：

• 性质 2 ： 若根结点不是终端结点则至少有两棵子树。 这个简单，由于 B 树是要求绝对平衡的树，那若根结点只有一棵子树怎么保持平衡呢。性质 5 也同理。

• 性质 3 ： 除根结点外所有非叶结点至少有 (向上取整)[m/2] 棵子树，即至少含有 (向上取整)[m/2] - 1 个关键字。 这其实就是种策略，为了保证查找效率，那为什么要把根结点除外呢，其实是做不到，因为若整棵树只有一个元素，那么根结点必然只有两个分支，不就没法满足了吗。示意图如下：

我们将 B 树的核心特质提取如下：

1. 根节点的子树数$\in[2, m]$，关键字数$\in[1, m-1]$。 其他结点的子树数$\in[\lceil m/2 \rceil, m]$；关键字数$\in[\lceil m/2 \rceil-1, m-1]$
2. 对任一结点，其所有子树高度都相同
3. 关键字的值：子树0<关键字1<子树1<关键字2<子树2<…（类比二叉查找树 左<中<右）
4. B 树的高度（磁盘存取次数）： 证明看书，含 (n) 个关键字的 (m) 叉B树，其高度 (h) 满足： $$ \log_m(n+1) \le h \le \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1 $$

7.4.1.2 B 树的查找

B 树的查找和二叉排序树的查找很类似，只是每个节点都是有很多个关键字的有序表。 B 树的查找包含两个基本操作：

1. 在 B 树中向下导航（磁盘 I/O 级别）： 根据关键字区间，决定下一次读哪个块。
2. 在结点内查找关键字（内存）： 在一个有序数组里做顺序/折半查找。

每次磁盘 I/O 读取一个结点，在内存中通过关键字区间比较，唯一确定下一子树指针，并继续向下，直到命中或到达叶子结点（失败）。

7.4.1.3 B 树的插入

将关键字 key 插入 B树的过程如下：

1. 定位： 利用查找算法，沿着路径向下查找，最终指向一个外部叶结点（表示查找失败），找到其父结点（终端结点）。最终插入位置一定是终端结点！！
2. 插入与分裂： 每个非跟结点的个数必须维持在区间$[\lceil m/2 \rceil-1, m-1]$，若插入之后的关键字个数不超过 m - 1 可直接插入；若插入后关键字个数超过 m - 1，则必须进行分裂。

分裂方法： 创建一个新结点，并将插入 key 后的原结点中的关键字从中间位置（第 ⌈m/2⌉ （向上取整）个关键字）处分成左右两部分：左半部分的关键字保留在原结点中；右半部分的关键字移至新结点中；中间的关键字（注意，是关键字而非结点）被提升并插入原结点的父结点。若父结点因接收该关键字而超出上限（关键字数大于 m−1），则对父结点递归执行分裂操作。这一过程可能向上传播，直至根结点。若根结点也被分裂，则 B 树高度增 1。

以一个例子作为说明： 依次向空 B 树中插入 25,38,49,60,80,90,99,88,83,87,70。

7.4.1.4 B 树的删除

B 树的删除比插入操作更复杂，因为删除之后需保证每个结点的关键字字数不少于下限（向上取整）⌈m/2⌉ - 1 ，可能需要通过 “借位” 或 “合并” 来恢复平衡。

• 当删除之后，结点关键字没有低于下限：

  • 终端结点： 直接删除。
  • 非终端结点： 将被删除元素 k 用直接前驱或者直接后继 k1 替换，将 k1 结点删除，从而转换成终端结点的删除。

• 当删除之后，结点的关键字低于下限：

  • 兄弟够借： 兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）。这里以 5 阶 B 树为例说明：

  • 兄弟不够借： 兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均为 ⌈m/2⌉−1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。
    

    在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少至 0（根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 ⌈m/2⌉−2，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。

7.4.2 B⁺ 树

考研中 B⁺ 树一般只考概念，示意图如下： 和 B 树的不同点如下，考研题目一般对比考，仔细阅读：

7.5 散列（Hash）表

逻辑结构是集合，存储结构是散列存储，底层依托是数组。

7.5.1 散列表的基本概念

• 散列表： 又称哈希表，可以根据数据元素的关键字计算出它在散列表中的存储地址。
• 散列函数： 建立了 “关键字”→“存储地址” 的映射关系。散列函数构建的越好，发生冲突的概率越小。
• 同义词： 若不同的关键字通过散列函数映射到同一个存储地址，则称它们为 “同义词”。
• 冲突（碰撞）： 在散列表中插入一个数据元素时，若插入的位置已经存储了其他元素，则称这种情况为 “冲突（碰撞）”。

示意图如下：

7.5.2 散列函数的构造方法

在构造散列函数时，必须注意以下三点：

1. 定义域必须涵盖所有可能出现的关键字，值域不能超出散列表的地址范围。
2. 尽可能减少冲突。散列函数计算出来的地址应尽可能均匀分布在整个地址空间。
3. 散列函数应尽量简单，能够快速计算出任意一个关键字对应的散列地址。

对于构造散列函数，我们有如下四个方法：

• 除留余数法（考研，现实都用的最多）： 一定注意要质数。 适用场景：比较通用，只要关键字是整数就行。
  

• 直接定址法： 严格来说不属于散列函数，但是考研把他放一起了。 适用场景：关键字分布基本连续。

• 数字分析法： 适用场景：关键字集合已知，且关键字的某几个数码位分布均匀。

• 平方取中法： 适用场景：关键字每位都不够均匀。

7.5.3 处理冲突的方法

任何散列函数都无法绝对避免冲突，因此，必须设计有效的冲突处理机制。

7.5.3.1 拉链法（链接法，chaining）

将散列到同一地址的所有同义词组织成一个链表，因此查找、插入和删除操作都主要在响应的同义词链表中进行。 插入使用头插法（默认）或尾插法都行，示意图如下： 查找也是在各个链表中查找，先计算哈希值，再进行关键字比对。示例如下： 删除没啥好说的，查到了删除就行，没查到就没法删。

7.5.3.2 开放定址法

简单来说，就是发生冲突，就给新元素找另外一个空闲位置。那么如何找到空闲位置，这里给出一个递推公式： $$ H_i = (H(\text{key}) + d_i)\ %\ m $$ H(key) 为散列函数，H_i 为发生第 i 次冲突时的散列地址，m 为散列表表长，d_i 为第 i 次探测的增量（偏移量）。那么只需要确定增量序列，对应的冲突处理办法就被确定了，常见的增量序列取法有以下四种：

线性探测法： 平方探测法： 双散列法： 伪随机序列法：

那使用开放定址法如何进行元素的查找和删除？首先题目肯定会给你 key 值，也肯定会告诉你使用的是哪种增量序列。那进行查找和删除的方法自然就不言而喻。

但是使用这种按不同增量序列顺序挨个遍历过去的方法会有一个坑！！如下图所示： 因为我们将上图 3 这个位置的元素删除的时候使用的是直接将其物理删除，那我们可以将其换成逻辑删除，用一个标识位 flag 表示这个元素是删除了还是没有。

对于散列表中有太多逻辑删除的位置，会导致 “看起来很满，其实很空” 查找效率降低，那我们可以定期对这些位置进行清理。如下图所示：

7.5.4 散列查找的性能分析

7.5.4.1 ASL 计算（线性探测法）

所谓查找的性能分析，自然就是计算其 ASL ，这里用考研中出现最多的开放定址法中的线性探测法举例。示意图如下： 注意计算 ASL _成功 和 ASL _失败 时的其分母含义是不同的！！！ 当删除了一个元素之后再计算，这种情况易错，要注意哦，示意图如下：

7.5.4.2 影响查找效率的因素

散列表的查找效率主要取决于三个因素：散列函数、冲突处理方法、装填因子。 装填因子： $$ \alpha = \frac{表中记录数 n}{散列表长度 m} $$ 显然，$\alpha$ 越大，发生冲突的可能性越高，反之越小。

7.5.4.3 聚集现象

聚集现象是在处理冲突的过程中，几个初始散列地址不同的元素争夺同一个后继地址的现象。使用线性探测法时，这种现象高发。 那么怎么解决这个问题呢，不用线性探测法，用其他的增量序列不就行了吗。如下图所示：

附言

查找好难 :(