数据结构第七章-查找

数据结构第七章查找

计算机学科基础：数据结构第七章查找的学习笔记

1.查找的基本概念

查找表：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，
可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种
- ①查询某个特定的数据元素是否在查找表中
- ②检索满足条件的某个特定的数据
- ③在查找表中插入一个数据元素
- ④从查找表中删除某个数据元素
静态查找表和动态查找表
- 若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为静态查找表。
- 与此对应，需要动态地插入或删除的查找表称为动态查找表。
  适合静态查找表的查找方法有顺序查找、折半查找、散列查找等，
  适合动态查找表的查找方法有二叉排序树的查找、散列查找等。
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
平均查找长度（ASL）：在查找过程中，一次查找的长度是指需要比较的关键字次数，
而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

2.顺序查找和折半查找（✪）

顺序查找（线性查找，适用于顺序表和链表）

一般线性表的顺序查找

加入哨兵的线性查找，算法从尾部开始查找，此时在0号位设置一个哨兵，查找失败则返回0，
无需判断是否越界，提高程序效率

代码实现

typedef struct{		//顺序表
    int *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--) //从后往前找
        return i;
}

平均查找长度：查找成功时：ASL=$\frac{n+1}{2}$，查找失败时为：ASL=$n+1$

有序表的顺序查找
- 可以设置查找判定树
  - 成功结点的关键字对比次数=结点所在层数
  - 失败结点的关键字对比次数=其父节点所在层数
  - 图片
平均查找长度：查找成功时：ASL=$\frac{n+1}{2}$，查找失败时为：ASL=$\frac{n}{n+1}+\frac{n}{2}$
顺序查找的时间复杂度：O(n)

折半查找（二分查找，仅适用于有序的顺序表✪）

此时设定中间指针(mid=(low+high)/2)，向下取整。如果较小则high=mid-1，在左边的区间再进行折半查找；
如果较大则low=mid+1,在右边的区间再进行折半查找。

代码实现（中间指针向下取整）

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
}

折半查找的判定树
- 性质（当$\operatorname{mid}{=\lfloor(} low + high ) / 2\rfloor$时）
  - 如果当前Iow和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等
  - 如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素
  - 每个结点值均大于其左子结点值，小于其右子结点值
  - 此二叉树时一颗平衡二叉树，并且有性质：右子树结点数—左子树结点数=0或1
  - 折半查找的判定树中，只有最下面一层是不满的，元素个数为${\boldsymbol{n}}$时树高${h=\left\lceil\log _{2}(n+1)\right\rceil}$
    - 折半查找不成功时的最多比较次数为树的高度，最少比较次数为树的高度减一
      - 此时由${h=\left\lceil\log _{2}(16+1>2^{4})\right\rceil}$最多需要比较5次，最少需要比较4次
  - 若有序序列有个n元素，则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点
    （失败结点的数量=成功结点所构成的树的空链域数量=n+1）
- 图片
- 关于折半查找二叉树的例题
  - 例1，已知关键字的个数，求查找成功的平均复杂长度和查找失败的平均复杂长度
    - 此时构造判定树，采用（$\operatorname{mid}{=\lfloor(} low + high ) / 2\rfloor$写出中间的点，
      再根据左小右大确定两边的范围，再某段范围里通过公式求出两边的点的中间的点）
  - 例2，判断是否能成为折半查找中关键字的比较序列
    - 此时直接写出相关的判定树，之后对各元素存在的合理性进行判断，
      A选项中200后的450说明之后的数都应该比200大，但是之后出现了180，此时不满足判定树的原理
折半查找的时间复杂度：$O ( \log _ { 2 } n )$

分块查找（索引顺序查找,了解）
- 概述
  - 将查找表分为若干块，块内的元素可以无序，但是块间的元素必须是有序的，
    前一个块中的最大关键字小于后一个块中所有记录的关键字
  - 之后建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，
    索引表按关键字有序排序。
  - 对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low>high,要在Iow所指分块中查找
- 图片
- 分块查找的平均时间复杂度分析（一般只分析分块查找的顺序查找索引表下的ASL）
  - 当每个分块内部元素的数量（s）等于元素总数开根时 $\sqrt{n}$ 时，（此时s=b=$\sqrt{n}$）此时其查找时间最小
  - 图片
- 分块矩阵的相应例题
  - 例1，利用分块矩阵顺序查找索引查找表的公式来计算查找成功的平均查找长度，$A S L = \frac { b + 1 } { 2 } + \frac { s + 1 } { 2 }$，
    b和s分别是块内的单元数和分块的数量，选B
  - 例2，分析在什么条件下的分块查找的平均查找长度最小并计算，此时需要满足：块数=块长=$\sqrt{元素总数}=255$，
    这个时候可以在索引项和索引表中都采取折半查找的方式，来计算最小的平均查找长度：${A S L=\left\lceil\log _{2}(255+1)\right\rceil + \left\lceil\log _{2}(255+1)\right\rceil}=16$

3.树形查找（✪）

二叉排序树（BST✪）

二叉排序树的定义
- 左子树上所有结点的关键字均小于根结点的关键字
- 右子树上所有结点的关键字均大于根结点的关键字
- 左子树和右子树又各是一棵二叉排序树。
- 注：空树也是二叉排序树
- 进行中序遍历，可以得到一个递增的有序序列

二叉排序树的查找

从根结点开始，沿某个分支逐层向下比较的过程
若树非空，目标值与根结点的值比较
- 若相等，则查找成功
- 若小于根结点，则在左子树上查找，否则在右子树上查找。
查找成功，返回结点指针；查找失败返回NULL

代码实现（了解）

二叉排序树的非递归算法

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;
}

二叉排序树的递归算法（空间复杂度较高，执行效率较低）

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); //在右子树中找
}

二叉排序树的插入

将二叉排序树T1的先序遍历序列依次插入初始为空的树中，所得到的二叉排序树T2和T1的形态完全相同。
在二叉排序树中插入一个结点的时间复杂度为O(n)
插入结点的过程如下：若原二叉排序树为空，则直接插入，否则，若关键字k小于根结点值，则插入到左子树，
若关键字k大于根结点值，则插入到右子树。

代码实现（了解）

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

二叉排序树的构造

从一颗空树出发，依次输入元素，并将其插入到二叉树中的合适位置

代码实现（了解）

void Creat_BST(BiTree &T,keyType str[],int n){
    T=NULL; //初始时为空树
    int i=0;
    while(i<n){
        BST_INsert(T,str[i]);
        i++;
    }
}

二叉排序树的删除
- 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
- 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
- 若结点z有左、右两棵子树，则令z的直接后继（直接前驱）替代z，然后从二叉排序树中删去这个直接后继（直接前驱）
  这里的直接后驱指的是右子树中进行中序遍历的第一个数，直接前驱指的是左子树中进行中序遍历的最后一个数）
- 图片
二叉排序树的查找效率分析
- 二叉排序树的查找效率，主要取决于树的高度。若树高h，找到最下层的一个结点需要对比h次
- 若二叉排序树的左、右子树的高度之差的绝对值不超过1(为平衡二叉树时)，它的平均查找长度为O($log_{2}n$)。
- 若二叉排序树是一个只有右（左）孩子的单支树（类似有序的单链表），则其平均查找长度为O(n)。
  - 用逐点插入法构建二叉排序树，若先后插入的关键字有序，此时二叉排序树的深度最大
- 图片

平衡二叉树（AVL树✪）
- 平衡二叉树的定义
  - 平衡二叉树可定义为或者是一棵空树，或者是具有下列性质的二叉树：
    它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。
  - 结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0或1。
- 平衡二叉树的插入
  - 概述
    - 每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。
    - 若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，
      再对以A为根的子树（最小不平衡子树），在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。
      - 此时找到距离插入点最近的平衡因子的绝对值大于1的点为序号70，LL插入，此时则应该变动70的左子树68进行右上旋
      - 图片
    - 在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
  - 四种调整的情况
    - LL：在A的左孩子的左子树中插入导致不平衡
      - 进行右单旋转，将A的左孩子右上旋
      - 图片
      - 代码实现
        
        1
        2
        3
        4
        // f是双亲结点，gf是f的双亲结点
        f->lchild=p->rchild;
        p->rchild=f;
        gf->lchild/rchild=p
    - RR：在A的右孩子的右子树中插入导致不平衡
      - 进行左单旋转，将A的右孩子左上旋
      - 图片
      - 代码实现
        
        1
        2
        3
        f->rchild=p->lchild;
        p->lchild=f;
        gf->lchild/rchild=p;
    - LR：在A的左孩子的右子树中插入导致不平衡
      - 在A的左孩子的右子树插入导致A不平衡，将A的左孩子的右孩子先左上旋再右上旋（此时这里的A为66，绝对值大于1）
      - 图片
    - RL：在A的右孩子的左子树中插入导致不平衡
      - 在A的右孩子的左子树插入导致A不平衡，将A的右孩子的左孩子先右上旋再左上旋（此时这里的A为50(绝对值大于1)）
      - 图片1
      - 图片2
- 平衡二叉树的删除
  - 步骤
    - ①删除结点(方法同“二叉排序树”)
    - ②向上看是否导致存在不平衡，若没有则结束
    - ③找最小不平衡子树下，“个头”最高的儿子、孙子
    - ④根据孙子相对于最小不平衡子树的根结点的位置，使用相关方法调整平衡(LL/RR/LR/RL)
      - 孙子在LL:儿子右单旋
      - 孙子在RR:儿子左单旋
      - 孙子在LR:孙子先左旋，再右旋
      - 孙子在RL:孙子先右旋，再左旋
    - ⑤如果不平衡向上传导，继续②
      - 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）
  - 例子：此时删除32后向上找到44不平衡，向下找到44最高的儿子和孙子78、50。孙子的情况是RL，
    则此时对其先右上旋再左上旋，调整为平衡二叉树
  - 对于一个平衡二叉树如果删除一个结点后再插入（不管是叶结点还是分支结点）此时树可能会发生改变；
    对于一个二叉排序树，删除叶子结点后再插入此时树不变，删除分支结点后再插入树会发生改变。
- 平衡二叉树的查找
  - 在查找过程中，查找次数不会超过平衡二叉树的深度
  - 在平衡二叉树上，树上任一结点的左子树和右子树的高度之差不超过 1 。
  - 假设以${n_{h}}$表示深度为${h}$的平衡树中含有的最少结点数。则有${n_{0}=0, n_{1}=1, n_{2}=2}$, 并且有${n_{h}=n_{h-1}+n_{h-2}+1}$
    - 本题用此方法递推计算（1,2,4,7,12,20）构建5层平衡二叉树至少需要12个顶点，
      构建6层平衡二叉树至少需要20个顶点，因此含有15个顶点的平衡二叉树的最大深度为5
    - 平衡二叉树总结点数最小时，所有非叶节点的平衡因子都为1
  - 含有$\mathrm{n} 个结点的平衡二叉树深度最小值为 \left\lfloor\log _{2} \mathrm{n}\right\rfloor+1$
  - 平衡二叉树的平均查找长度为${O\left(\log _{2} n\right)}$
红黑树（RBT✪）
- 红黑树的定义：一种特殊的二重排序树
  - 红黑树RBT，插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。
    即便需要调整，一般都可以在常数级时间内完成
  - 平衡二叉树：适用于以查为主、很少插入/删除的场景
  - 红黑树：适用于频繁插入、删除的场景，实用性更强
  - 结点的黑高：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数
- 红黑树的五个特点（左根右，根叶黑，不红红，黑路同）
  - 每个结点或是红色，或是黑色的
  - 根节点是黑色的
  - 叶结点(这里指NULL和结点失败结点)均是黑色的
  - 不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
  - 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
- 红黑树的结论
  - 从根节点到叶结点的最长路径不大于最短路径的2倍
    - 当从根到任意一个叶结点的简单路径最短时，这条路径必然全部由黑结点构成
    - 当某条路径最长时，这条路径必然是由黑结点和红结点相间构成的，此时两者的数量相同
    - 红黑树的任意一个结点的左右子树高度（含叶结点）之比不超过2
  - 有n个内部节点的红黑树高度 h≤$2log_{2}(n+1)$
  - 根节点黑高为h的红黑树，内部结点数（关键字）至少有$2^{h}-1$个
  - 红黑树查找操作时间复杂度=O($log_{2}n$)，查找效率与AVL树同等数量级
- 红黑树的插入
  - 插入结点的方法，注：一般插入时违背的是“不红红”
  - 例子

4.B树与B+树（✪）

B树（✪）
- B树的性质
  - m阶B树是所有结点的平衡因子均等于0的m路平衡查找树。
  - 一棵m阶B树或为空树，或为满足如下特性的m叉树
    - 树中每个结点至多有$m$棵子树，即至多含有$m-1$个关键字。
    - 若根结点不是叶结点，则至少有两棵子树。
    - 除根结点外的所有非叶结点至少有$ \lceil m / 2\rceil $棵子树，即至少含有$ \lceil m / 2\rceil-1 $个关键字。
    - 满足左<中<右的性质
    - 所有叶节点都出现在同一层次上，并且不带信息（即为查找失败结点）
    - ${\mathrm{n}}$个关键字的B树必有${\mathrm{n}+1}$个叶子结点
    - 注：判断B树的类型，需要看其中关键字最多的结点判断是几阶
    - 图片
- B树的最小高度和最大高度（此时一般不包括最后一层叶子结点的层数）
  - 对于n个关键字，m阶B树的最小高度
    - 在每一层中含有最多的结点数并且在每一个结点中含有最多的关键字数
    - 此时关键字的数量满足：$n \leqslant(m-1)\left(1+m+m^{2}+\cdots+m^{h-1}\right)=m^{h}-1$
    - 此时可算出最小的高度： $h \geqslant \log _{m}(n+1)$
  - 对于n个关键字，m阶B树的最大高度
    - 在每一层中含有最小的结点数并且在每一个结点中含有最少的关键字数
    - 此时让各层的分叉尽可能的少, 即根节点只有 2 个分叉, 其他结点只有${\lceil m / 2\rceil}$个分叉
    - 各层结点至少有：第一层 1、第二层 2、第三层${2\lceil\mathrm{m} / 2\rceil \ldots}$第h层${2(\lceil\mathrm{m} / 2\rceil)^{h-2}}$，
      则第h+1层共有叶子结点（失败结点）${2(\lceil m / 2\rceil)^{h-1}}$个
    - ${\mathrm{n}}$个关键字的B树必有${\mathrm{n}+1}$个叶子结点, 则${n+1 \geq 2(\lceil m / 2\rceil)^{h-1}}$, 即${h \leq \log _{\lceil m / 2\rceil} \frac{n+1}{2}+1}$
    - 此时可算出最大的高度：$h \leq \log _{\lceil m / 2\rceil} \frac{n+1}{2}+1$
  - 含$\mathrm{n}$个关键字的$\mathrm{m叉B} 树, 满足 \log _{m}(n+1) \leq h \leq \log _{\lceil m / 2\rceil} \frac{n+1}{2}+1$
- B树的插入
  - 首先定位元素插入的位置，新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置
  - 如果再插入关键字后，结点中的关键字数量没有超过上限，此时直接插入即可
    （如阶为5的B树的关键字范围为2—4，在一个结点中最多有4个，最少有2个关键字）
  - 在插入key后, 若导致原结点关键字数超过上限, 则从中间位置${(\lceil\mathrm{m} / 2\rceil)}$将其中的关键字分为两部分,
    左部分包含的关键字放在原结点中, 右部分包含的关键字放到新结点中, 中间位置${(\lceil{m} / 2\rceil)}$的结点插入原结点的父结点
  - 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，
    进而导致B树高度增1。
  - 图片
    - 图1
    - 图2
- B树的删除
  - 若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字
    - 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
    - 直接后继：当前关键字右侧指针所指子树中“最左下”的元素
  - 若被删除关键字在终端节点，此时分为下列三种情况
    - 删除后的结点中的关键字的数量不低于低于下限${\lceil m / 2\rceil-1}$时，则直接删除该关键字
    - （兄弟够借）
      - 删除后结点的关键字数量将低于下限${\lceil m / 2\rceil-1}$，且与结点相邻的右（或左）兄弟结点的关键字个数还很宽裕，
      - 此时删除该结点后，将其对应的一个父节点的关键字转移到此处，并将右兄弟或左兄弟的一个关键字转移到此父节点
      - 去借右兄弟：
        
        此时删除38，此时其右兄弟够用，将父结点关键字49下移来替换38，
        并且将右兄弟关键字70上移到原来的父节点关键字处
        
        图片
      - 去借左兄弟
        
        此时删除90，其左兄弟够用，使父结点关键字88下移，再将左兄弟结点关键字87上移
        
        图片1
        
        图片2
    - (兄弟不够借)
      - 若被删除关键字所在结点删除关键字后少于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均${\lceil m / 2\rceil-1}$,
      - 则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并
      - 在合并过程中, 双亲结点中的关键字个数会减 1，此时可能需要对双亲结点进行相关操作
        
        若双亲结点不是根结点, 且关键字个数减少到${\lceil m / 2\rceil-2}$, 则又要与它自己的兄弟结点进行调整或合并操作,
        并重复上述步骤, 直至符合${B}$树的要求为止。
        
        若其双亲结点是根结点且关键字个数减少至 0 (根结点关键字个数为 1 时, 有 2 棵子树) , 则直接将根结点删除,
        合并后的新结点成为根
      - 流程
        
        此时删除49，但是其右兄弟的关键字数量已经不够借，
        此时删除49之后将父结点关键字70下移以及和其右兄弟结点的两个关键字合并到一起
        
        此时合并之后，上方的父结点中的关键字数量已经少于下限，此时也需要合并，
        可将父结点82与其右兄弟结点中的87,93关键字合并到一起，此时根节点为空，删除根结点即可
B+树（适用于数据库）
- B+树的性质
  - 每个分支结点最多有m棵子树（孩子结点）
  - 非叶根结点至少有两棵子树，其他每个分支结点至少有${\lceil\mathrm{m} / 2\rceil}$棵子树。
  - 结点的子树个数与关键字个数相等。
  - 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，
    并且相邻叶结点按大小顺序相互链接起来。（支持顺序查找）
  - 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
  - B+树含有两个头指针，一个指向根结点，一个指向关键字最小的叶结点，
    可以进行从最小关键字开始的顺序查找以及从根结点开始的多路查找
    - 在B+树中进行的多路查找，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，
      直到叶结点上的该关键字为止。在B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。
  - 图片
- B+树与B树的区别
  - 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；
    而在B树中，具有n个关键字的结点含有n+1棵子树。
  - 在B+树中，每个结点（非根内部结点）的关键字个数n的范围是 ${\lceil\mathrm{m} / 2\rceil} ≤n≤m$ (而根结点：$1≤n≤m$)；
    而在B树中，每个结点（非根内部结点）的关键字个数n的范围是${\lceil\mathrm{m} / 2\rceil}-1≤n≤m-1$ (根结点：$1≤n≤m-1$)
  - 在B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中；
    而在B树中，最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
  - 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，
    非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
    B树的结点中都包含了关键字对应的记录的存储地址

5.散列表（✪）

散列表的基本概念
- 散列表 (哈希表，Hash Table)：是一种数据结构。根据关键字而直接进行访问的数据结构。
  散列表建立了关键字和存储地址之间的一种直接映射关系。
- 散列函数（哈希函数）：一个把查找表中的关键字映射成该关键字对应的地址的函数，
  记为Hash(key)=Addr (这里的地址可以是数组下标、索引或内存地址等)
- 冲突和同义词：散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，
  这些发生碰撞的不同关键字称为同义词
散列表的构造
- 进行构造的要点
  - 定义域必须涵盖所有可能出现的关键字，值域不能超出散列表的地址范围
  - 尽可能减少冲突。散列函数计算出来的地址应尽可能均匀分布在整个地址空间。
  - 散列函数应尽量简单，能够快速计算出任意一个关键字对应的散列地址
- 四种构造的方法
  - 除留余数法：H(key)=key%p
    - 散列表表长为m，取一个不大于m但最接近或等于m的质数p
    - 如表长为13，16，p可以均选13
    - 只要关键字为整数就适用
  - 直接定址法：H(key)=key或H(key)=a*key+b
    - 其中，和b是常数。这种方法计算最简单，且不会产生冲突。
      若关键字分布不连续，空位较多，则会造成存储空间的浪费。
    - 适用场景：关键字分布基本连续
  - 数字分析法：选取数码分布较为均匀的若干位作为散列地址
    - 每个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；
      而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。
    - 适用场景：关键字集合已知，且关键字的某几个数码位分布均匀
  - 平方取中法：取关键字的平方值的中间几位作为散列地址
    - 这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀。
    - 适用场景：关键字的每位取值都不够均匀。
处理冲突的方法
- 开放定址法：如果发生冲突，就给新元素找另一个空闲的位置
  - 数学递推公式为：$H _ { i } = ( H ( k e y ) + d _ { i } ) \% m$（m为散列表表长）
  - 其中$d_{i}$为增量序列（偏移量），通过四种方法可以进行选择
  - 采用“开放定址法”时，删除元素不能简单地将被删元素的空间置为空，
    否则将截断在它之后的探测路径，可以做一个“已删除”标记，进行逻辑删除。
  - 理想情况下，若散列表表长=m,则最多发生m-1次冲突即可“探测”完整个散列表。
  - 线性探测法
    - $d_{i}=0,1,2,3……m-1$
    - 可以探测到散列表的每一个地址，但是容易造成大量元素在相邻的散列地址上聚集，大大降低查找效率
    - 堆积问题是由于同义词之间或非同义词之间发生冲突导致的
    - 当从散列表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响后面的查找，逻辑删除即可
  - 平方探测法（又称为二次探测法）
    - ${d_{i}=0^{2}, 1^{2},-1^{2}, 2^{2},-2^{2}, \ldots, k^{2},-k^{2}}$。其中${k \leq m / 2}$
    - 采用平方探测法，至少可以探测到散列表中一半的位置，即便散列表中有空闲位置，也未必能插入成功
    - 若散列表长度m是一个可以表示成4k+3的素数(如7、11、19)，平方探测法就能探测到所有位置
    - 可以有效避免堆积的问题
  - 双散列法
    - ${d_{i}=\mathbf{i} \times \operatorname{hash}_{2}(k e y)}$
    - 双散列法未必能探测到散列表的所有位置。双散列法的探测覆盖率取决于第二个散列函数hash2(key)设计的是否合理。
    - 若hash2(key)计算得到的值与散列表表长m互质，就能保证双散列发可以探测所有单元
    - 令表长m本身就是质数，hash2(key)=m-(key%m)，此时无论key值是多少，hash2(key)和m一定互质
  - 伪随机序列法：d是一个伪随机序列，由程序员人为设计
- 拉链法（链地址法）
  - 适用于经常进行插入和删除的情况
  - 查找长度是指的查找时与相应关键字的对比次数
  - 如此时要找40，此时需要在1处的链表查找4次，未能找到
散列查找及性能分析
- 先求得散列地址，在散列地址上已有关键字且与查找的关键字不同时，使用相关方法进行冲突处理。
  若散列地址上没有关键字此时查找失败。若散列地址上的关键字与被查找关键字相等，此时查找成功，返回相应的地址
- 散列表的查找效率主要取决于：散列函数，处理冲突的方法和装填因子
- 装填因子a，定义为一个表的装满程度：$a=\frac{表中记录数n}{散列表长度m}$
- 散列表的平均查找长度依赖于散列表的装填因子$a$，而不直接依赖于n或m。
  直观地看，$a$越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。
- 例题：求查找失败的平均查找长度就是查到表中的空地址时，即查找失败，此时虽然表中有序号为7的元素，
  但是由于散列为7的余数，此时只会在0-6的范围内有相对应的地址，但是查询的时候会查到序号为8的地方。

数据结构第七章 查找

1.查找的基本概念

2.顺序查找和折半查找（✪）

3.树形查找（✪）

4.B树与B+树（✪）

5.散列表（✪）

数据结构第七章查找