数据结构与算法分析-查找

查找的概念，顺序查找，折半查找，分块查找，散列查找[散列函数，散列冲突，拉链法，平方探测法，伪随机序列法，再散列法]

视频讲解，习题讲解，思维导图，PPT资源

链接: https://pan.baidu.com/s/1li7-h2vPr8qXzNn2oDbxmA 密码: 4r0n

1. 查找的基本概念

1.1. 基本概念

查找 —— 在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表(查找结构)—— 用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成

关键字 —— 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是 唯一的

eg:

	举例1	举例2
查找表	学生成绩信息(线性结构、可顺序可链式存储)	微信用户数据集(图结构)
数据元素(记录)	每个学生的信息	每个用户用户的信息
关键字	学号	微信号

1.2. 对查找表的常⻅操作

• 静态查找表——查找符合条件的数据元素，仅关注查找速度即可

  顺序查找，折半查找，散列查找

• 动态查找表——插入/删除某个数据元素，除了查找速度，也要关注插/删操作是否方便实现

  二叉查找树，散列查找

1.3. 查找算法的评价指标

查找⻓度——在查找运算中，需要对比关键字的次数称为查找⻓度

平均查找⻓度(ASL, Average Search Length)—— 所有查找过程中进行关键字的比较次数的平均值

ASL=$\sum_{i=1}^{n}P_{i}C_{i}$

P$_{i}$ —查找第 i 个元素的概率

C$_{i}$ —查找第 i 个元素的查找⻓度

评价一个查找算法的效率时，通常考虑查找成功。查找失败两种情况的ASL

Eg:

查找成功的平均查找长度：ASL=(1x1+2x2+3x4+4x1)/8=2.625

查找失败的平均查找长度：ASL=(3x7+4x2)/9=3.22

2. 顺序查找

顺序查找，又叫“线性查找”，通常用于线性表，对顺序表和链表都适用。

2.1. 算法思想

从头到脚挨个找(或者反过来也OK)

2.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);
  return i==ST.TableLen?-1:i;
}

//利用elem[0]当作哨兵-无需判断是否越界，效率更高
int Search_Seq(SSTable ST,ElemType key){
  ST.elem[0]=key;
  int i;
  for(i=ST.TableLen;&&ST.elem[i]!=key;--i);
  return i;
}

ASL_成功=(1+2+3+…+n)/n = (n+1)/2

ASL_失败= n+1

顺序查找缺点是n较大时，平均查找长度较大，效率低。

对于线性链表只能进行顺序查找。

2.3. 顺序查找的优化(对有序表)

查找表中元素有序存放(递增/递减)

一个成功结点的查找⻓度 = 自身所在层数

一个失败结点的查找⻓度 = 其父节点所在层数

默认情况下，各种失败情况或成功情况都等概率发生

2.4. 顺序查找的优化(被查概率不相等)

被查概率：7: 15%，13: 5%，19: 10%，29: 40%，37: 28%，43: 2%

对于 7，13，19，29，37，43

ASL_成功 = 1x0.15 + 2x0.05 + 3x0.1 + 4x0.4 + 5x0.28 + 6x0.02 = 3.67

对于 29，37，7，19，13，43

ASL_成功 = 1x0.4 + 2x0.28 + 3x0.15 + 4x0.1 + 5x0.05 + 6x0.02 = 2.18

3. 折半查找—仅对有序顺序表

3.1. 算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表

• 初始：low=0；high=TableLen-1；mid =(low+high)/2

• 若查找目标值 = elem[mid] ，则查找成功

• 若查找目标值 < elem[mid] ，则将left=mid+1

• 若查找目标值 > elem[mid] ，则将high=mid-1

• 反复mid =(low+high)/2，继续查找，直到查找成功或low>high查找失败

3.2. 算法实现

typedef struct{
  //动态数组基址
  ElemType *elem;
  int TableLen;//表长
}SSTable;//顺序表

int Binary_Search(SSTable L,ElemType key){
  int low = 0;
  int high = L.TableLen-1;
  while(low<=high){
    int mid = (low+high)/2;
    if(L.elem[mid]==key){
      return mid;
    }
    else if(L.elem[mid]<key){
      left = mid+1;
    }
    else{
      high = mid-1;
    }
  }
  return -1;
}

3.3. 查找效率分析

3.3.1. 折半查找判定树构造

7，10，13，16，19，29，32，33，37，41，43

判定树结点关键字：左**<中<**右，满足二叉排序树的定义

失败结点：n+1个(等于成功结点的空链域数量)

3.3.2. 折半查找的查找效率

• mid = $\left \lfloor (low+high)/2 \right \rfloor$

  如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等

  如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素

  则对于任何一个结点，必有: 右子树结点数-左子树结点数=0或1

• mid = $\left \lceil (low+high)/2 \right \rceil$

  如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等

  如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分比右半部分多一个元素

  则对于任何一个结点，必有: 左子树结点数-右子树结点数=0或1

---

折半查找的判定树一定是平衡二叉树 — 完全二叉树

折半查找的判定树中，只有最下面一层是不满的

因此，元素个数为n时树高 h= $\left \lceil log_{2}(n+1) \right \rceil$

查找成功的ASL ≤ h ASL_成功=(1x1+2x2+…+hx2^h-1)=$\frac{n+1}{n}log_{2}(n+1)-1 \approx$ log₂(n+1)

查找失败的ASL ≤ h

折半查找的时间复杂度 = O(log₂n)

3.4. 折半查找的速度一定比顺序查找更快?

7，10，13，16，19，29，32，33，37，41，43

查找7时，顺序查找O(1)，折半查找 O(log₂n)

4. 分块查找—索引顺序查找

吸取了顺序查找和折半查找的优点，既有动态结构，又适于快速查找。

4.1. 算法思想

将查找表分为若干子块。块内元素可以无序，但块间是有序的，即第一块中的最大关键字小于第二块中的所有记录的关键字，第二块中的最大关键字小于第三块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的存储区间。索引表按关键字有序排列。

查找过程：

1. 在索引表中确定待查记录所属的分块(可顺序、可折半)
2. 在块内顺序查找

若索引表中不包含目标关键字，则折半查找索引表最终停在 low>high，要在low所指分块中查找

因前一步为low=high=mid，

若mid所指位置元素<key, 则low+1，low所指位置元素>mid所指位置元素

若mid所指位置元素>key, 则high-1，low所指位置元素>key

最终low左边一定小于目标关键字，high右边一定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字

4.2. 查找效率分析(ASL)

假设，⻓度为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}$ 时，ASL_最小= $\sqrt{n}$ + 1

用折半查找查索引表：

则 L_I= $\left \lceil log_{2}(b+1) \right \rceil$，L_S= $\frac{(1+2+…+s)}{s}$=$\frac{(s+1)}{2}$

则ASL=$\left \lceil log_{2}(b+1) \right \rceil$$+$$\frac{(s+1)}{2}$

4.3. 动态查找表-链式存储

原有的块内元素不易于插入/删除新元素

将索引表和块表用动态数组表示，块内可动态添加/删除元素

5. B树

5.1. 5叉查找树

5.2. 概念

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树 或为空树，或为满足如下特性的m叉树：

1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字

2. 若根结点不是终端结点，则至少有两棵子树

3. 除根结点外的所有非叶结点至少有 $\left \lceil m/2 \right \rceil$棵子树，即至少含有 $\left \lceil m/2 \right \rceil$-1 个关键字

4. 所有非叶结点的结构如下:

   n	P0	K1	P1	K2	P2	…	Kn	Pn

   其中，K_i (i = 1, 2,…, n)为结点的关键字，且满足K₁ < K₂ <…< K_n；

   P_i (i = 0, 1,…, n)为指向子树根结点的指针，且指针P_i-1所指子树中所有结点的关键字均小于K_i，P_i所指子树中所有结点的关键字均大于K_i

   n ( $\left \lceil m/2 \right \rceil$ - 1 $\leq $ n $\leq $ m - 1)为结点中关键字的个数

5. 所有的叶结点都出现在同一层次上，并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失 败结点，实际上这些结点不存在，指向这些结点的指针为空)

5.3. 特性

1. 根节点的子树数 $\epsilon $ [2, m]，关键字数 $\epsilon $ [1, m-1]

   其他结点的子树数 $\epsilon $ [ $\left \lceil m/2 \right \rceil$ , m]；关键字数 $\epsilon $ [ $\left \lceil m/2 \right \rceil$ -1, m-1]

2. 对任一结点，其所有子树高度都相同

3. 关键字的值：子树0<关键字1<子树1<关键字2<子树2<…. (类比二叉查找树 左<中<右)

5.4. B树的高度

注：大部分学校算B树的高度不包括叶子结点(失败结点)

问题：含n个关键字的m阶B树，最小高度、最大高度是多少?

log_m(n+1) $\leq$ h $\leq$ log$_{\left \lceil m/2 \right \rceil}$ $\frac{n+1}{2}$ + 1

5.4.1. 最小高度

让每个结点尽可能的满，有m-1个关键字，m个分叉，则有

n $\leq$ (m−1)(1+m+m²+m³+…+m^h−1)=m^h−1， 因此 h $\geq$ log_m(n+1)

5.4.2. 最大高度

让每个结点包含的关键字、分叉尽可能的少，即根节点只有2个分叉，其他结点只有 $\left \lceil m/2 \right \rceil$ 个分叉

记 k = $\left \lceil m/2 \right \rceil$

	最少结点数	最少关键字数
第一层	1	1
第二层	2	2(k-1)
第三层	2k	2k(k-1)
第四层	2k2	2k2(k-1)
…	…	…
第h层	2kh-2	2kh-2(k-1)

h层的m阶B树至少包含关键字总数 1+2(k-1)(k⁰+k¹+k²+…+k^h-2) = 1+2(k^h-1-1)

若关键字总数少于这个值，则高度一定小于h，因此 n $\geq$ 1+2(k^h−1-1)，即 h $\leq$ log$_{\left \lceil m/2 \right \rceil}$ $\frac{n+1}{2}$ + 1

第h+1层共有叶子结点(失败结点) 2($\left \lceil m/2 \right \rceil$)^h−1 个

n个关键字的B树必有n+1个叶子结点，则 n + 1 $\geq$ 2($\left \lceil m/2 \right \rceil$)^h−1，即 h $\leq$ log$_{\left \lceil m/2 \right \rceil}$$\frac{n+1}{2}$ + 1

5.5. B树的查找

查找类似于二叉查找树的查找。

B树存在磁盘中，B树找结点是在磁盘中进行的，找关键字在内存中进行。即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

B树上查找到某个结点后，先在有序表中进行查找，若找到查找成功，否则按照对应的指针信息到所指的子树中去查找。若查找到叶结点则说明树中没有对应的关键字，查找失败。

5.6. B树的插入

1. 关键字数 $\epsilon $ [ $\left \lceil m/2 \right \rceil$ -1, m-1]

2. 关键字的值：子树0<关键字1<子树1<关键字2<子树2<…. (类比二叉查找树 左<中<右)

3. 在插入key后，若导致原结点关键字数超过上限，则从中间位置($\left \lceil m/2 \right \rceil$)将其中的关键字分为两部分，左部分包 含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置($\left \lceil m/2 \right \rceil$)的结点插入原结点的父结点

4. 新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置

5. 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1

5阶B树——结点关键字个数 2 $\leq$ n $\leq$ 4

从中间位置($\left \lceil m/2 \right \rceil$)将其中的关键字分为两部分

新元素一定是插入到最底层“终端节点”

从中间位置($\left \lceil m/2 \right \rceil$)将其中的关键字分为两部分

5.7. B树的删除

1. 若被删除关键字在终端节点，则直接删除该关键字(要注意节点关键字个数是否低于下限 $\left \lceil m/2 \right \rceil$ − 1)

   删除关键字72，所在结点关键字数2=$\left \lceil m/2 \right \rceil$ − 1，直接删除关键字

2. 若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字，从而转化为对终端结点的删除操作

   直接前驱：当前关键字左侧指针所指子树中“最右下”的元素

   直接后继：当前关键字右侧指针所指子树中“最左下”的元素

   删除80，替换为77或82

判断终端节点在删除关键字后关键字数<下限情况

• 兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右(或左)兄弟结点的关键字个数还很宽裕，则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)

  

  删除38。当右兄弟很宽裕时，取当前结点的后继49、后继的后继70来填补空缺

  

  删除90。当左兄弟很宽裕时，用当前结点的前驱88、前驱的前驱87来填补空缺

  

• 兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=$\left \lceil m/2 \right \rceil$ − 1，则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并

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

  删除49。右兄弟关键字数=2，借不了了，需要将结点与右兄弟结点及双亲结点合并

  

  此时73所在结点关键字数也小于下限，需要进行合并

  

6. B+树

类似于分块查找

一棵m阶的B+树需满足下列条件:

1. 每个分支结点最多有m棵子树(孩子结点)

2. 根结点至少有两棵子树，其他每个分支结点至少有 $\left \lceil m/2 \right \rceil$ 棵子树

3. 结点的子树个数与关键字个数相等

4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来

5. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

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

   B树的查找，查找成功，可能停在任何一层

典型应用：关系型数据库的“索引”(如 MySQL)

在B+树中，非叶结点不含有该关键字对应记录的存储地址。

可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，读磁盘次数更少，查找更快

7. B树 vs B+树

	m阶B树	m阶B+树
类比	二叉查找树的进化 ——m叉查找树	分块查找的进化——多级分块查找
关键字与分叉	n个关键字对应n+1个分叉(子树)	n个关键字对应n个分叉(子树)
结点关键字数范围	根节点 [1,m-1] 其他结点 [ $\left \lceil m/2 \right \rceil$-1,m-1]	根节点 [2,m] 其他结点 [ $\left \lceil m/2 \right \rceil$ ,m]
结点存储地址?	结点中包含了关键字对应的记录的存储地址 但叶结点中不包含任何信息	叶结点包含信息，所有非叶结点仅起索引作用， 非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针， 不含有该关键字对应记录的存储地址
关键字重复?	各结点中包含的关键字是不重复的	叶结点包含全部关键字， 非叶结点中出现过的关键字也会出现在叶结点中
查找方式	不支持顺序查找。 查找成功时，可能停在任何一层结点，查找速度“不稳定”	支持顺序查找。 查找成功或失败都会到达最下一层结点，查找速度“稳定”
相同点	除根节点外，最少 $\left \lceil m/2 \right \rceil$ 个分叉(确保结点不要太“空”) 任何一个结点的子树都要一样高(确保“绝对平衡”)

8. 散列查找

8.1. 概念

散列表(Hash Table)，又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关

如何建立“关键字”与“存储地址” 的联系? —— 通过“散列函数(哈希函数)”：Addr=H(key)

eg：有一堆数据元素，关键字分别为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 H(key)=key%13

19%13=6，14%13=1，23%13=10，1%13=1，68%13=3，20%13=7，84%13=6，27%13=1，55%13=3，11%13=11，10%13=10，79%13=1

若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”

通过散列函数确定的位置已经存放了其他元素，则称这种情况为 “冲突”

用拉链法(又称链接法、链地址法)处理“冲突”：把所有“同义词”存储在一个链表中

0	1	2	3	4	5	6	7	8	9	10	11	12
	14		68			19	20			23	11
	1		55			84				10
	27
	79

通过散列函数计算目标元素存储地址：Addr=H(Key)

27%13=1，27的查找⻓度=3

20%13=7，20的查找⻓度=1

21%13=8，21的查找⻓度=0(大多数学校的计算方法)，21的查找⻓度=1(有的教材也会把“空指针” 的判定算作一次比较)

66%13=1，66的查找⻓度=4

查找⻓度——在查找运算中，需要对比关键字的次数称为查找⻓度

ASL_成功= (1x6+2x4+3+4)/12= 1.75

ASL_成功=(1+2+3+4+1+2+1+2+1+1+2+1)/12 =1.75，“冲突”越多，查找效率越低

ASL_失败=(0+4+0+2+0+0+2+1+0+0+2+1+0)/13=0.92

装填因子$\alpha$=表中记录数/散列表⻓度

装填因子会直接影响散列表的查找效率

8.2. 常⻅的散列函数

设计目标——让不同关键 字的冲突尽可能地少

8.2.1. 除留余数法

H(key) = key % p

散列表表⻓为m，取一个不大于m但最接近或等于m的质数p

质数又称素数。指除了1和此整数自身外,不能被其他自然数整除的数

Why?——用质数取模，分布更均匀，冲突更少。参⻅《数论》

Tips：散列函数的设计要结合实际的关键字分布特点来考虑，不要教条化

8.2.2. 直接定址法

H(key) = key 或 H(key) = a*key + b

其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

eg：

存储同一个班级的学生信息，班内学生学号为(1120112176~1120112205)

H(key) = key - 1120112176

8.2.3. 数字分析法

选取数码分布较为均匀的若干位作为散列地址

设关键字是r进制数(如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合， 若更换了关键字，则需要重新构造新的散列函数

eg：以“手机号码”作为关键字设计散列函数

138XXXX2875，138XXXX1682，138XXXX9125， ….. ，199XXXX1684，199XXXX1236

设计⻓度为10000的散列表，以 手机号后四位作为散列地址

8.2.4. 平方取中法

取关键字的平方值的中间几位作为散列地址

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得

散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

eg：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数

身份证号码规则:

前1、2位数字表示：所在省份的代码;

第3、4位数字表示：所在城市的代码;

第5、6位数字表示：所在区县的代码;

第7-14位数字表示：出生年、月、日;

第15、16位数字表示：所在地的派出所的代码;

第17位数字表示性别：奇数表示男性，偶数表示女性;

第18位数字是校检码。

假设学生不超过十万人，身份证号平方取中间5位

若散列表的⻓度为1000000000000000000(别数了，有18个0) 则可以直接用身份证号作为散列地址，且不可能有冲突，查找时间复杂度为O(1)

散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越⻓，冲突的概率越低。

8.3. 处理冲突的方法

8.3.1. 拉链法

用拉链法(又称链接法、链地址法)处理“冲突”：把所有“同义词”存储在一个链表中

关键字分别为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 H(key)=key%13

优化：在插入新元素时，保持 关键字有序，可微微提高查找效率

8.3.2. 开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为:

H_i = (H(key) + d_i) % m，i = 0, 1, 2,…, k(k $\leq$ m - 1)；m表示散列表表⻓；d_i为增量序列；i可理解为“第i次发生冲突”

8.3.2.1. 线性探测法

d_i= 0, 1, 2, 3, …, m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空

线性探测法很容易造成同义词、非同义词的“聚集(堆积)”现象，严重影响查找效率

产生原因——冲突后再探测一定是放在某个连续的位置

关键字分别为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数 H(key)=key%13

插入1：

H(key)=1%13=1

发生第1次冲突后重新计算得到的哈希地址：H₀=(1+d₀)%16=1 —> H₁=(1+d₁)%16=2

查找27：

H(key)=27%13=1 —> H₁=2 —> H₂=3 —> H₃=4，则27的查找⻓度=4

同义词、非同义词都需要被检查

查找11:

H(key)=11%13=11， 则11的查找⻓度=1

查找21:

H(key)=21%13=8 —> H₁=9 —> H₂=10 —> H₃=11 —> H₄=12 —> H₅=13，则21的查找⻓度=6

空位置的判断也要算作一次比较

越早遇到空位置，就可以越早确定查找失败

删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除

查找效率分析(ASL)

19%13=6——1次 27%13=1——4次 55%13=3——3次

14%13=1——1次 68%13=3——1次 11%13=11——1次

23%13=10——1次 20%13=7——1次 10%13=10——3次 12

1%13=1——2次 84%13=6——3次 79%13=1——9次

ASL_成功=$\frac{1+1+1+2+4+1+1+3+3+1+3+9}{12}$ =2.5

ASL_失败=$\frac{1+13+12+11+10+9+8+7+6+5+4+3+2}{13}$ =7

8.3.2.2. 平方探测法

平方探测法。当 d_i = 0², 1², -1², 2², -2², …, k², -k²时，称为平方探测法，又称二次探测法其中 k$\leq$m/2

散列表⻓度m必须是一个可以表示成4j + 3的素数，才能探测到所有位置

平方探测法：比起线性探测法更不易产生“聚集(堆积)”问题

注意负数的模运算，(-3)%27 = 24，而不是3

《数论》中模运算的规则：a MOD m == (a+km) MOD m 其中，k为任意整数

8.3.2.3. 伪随机序列法

伪随机序列法。d_i是一个伪随机序列，如 d_i= 0, 5, 24, 11, …

8.3.3. 再散列法

严蔚敏《数据结构》—— 再散列法(再哈希法)：除了原始的散列函数 H(key) 之外，多准备几个散列函数， 当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：H_i = RH_i(Key) i=1,2,3….,k

王道《数据结构》—— 再散列法。当d_i=Hash₂(key)时，称为再散列法，又称双散列法。需要适用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash₂(key)计算该关键字的地址增量。它的具体散列函数形式如下：H_i=(H(key)+i*Hash₂(key))%m。初始探测位置H₀ = H(key)%m。i是冲突的次数，初始为0。在散列法中，最多经过m-1次探测就会遍历表中所有位置，回到H₀位置。

8.4. 散列性能分析

虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。

散列表的查找效率取决于三个因素：散列函数，处理冲突的方法，装填因子

装填因子 $\alpha=\frac{表中记录数}{散列表⻓度}$

散列表的平均查找长度依赖于散列表的装填因子，不直接依赖于n或m。直观地看，$\alpha$ 越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。

8.4.1. 查找成功的平均查找长度

ASL_成功 = 查找次数 / 元素个数

eg：1，13，12，34，38，33，27，22，H(key)=key%11

8.4.2. 查找失败的平均查找长度

ASL_失败 = 查找次数 / 散列后的地址个数