知识点梳理：数据结构与算法——检索

线性表的检索

二分检索

mid-1/mid+1

成功的平均检索长度：

（画出树来，第i层的元素经过i次检索到）

ASL ⁡ = 1 n ( ∑ i = 1 j i ⋅ 2 i − 1 ) = n + 1 n log ⁡ 2 ( n + 1 ) − 1 ≈ log ⁡ 2 ( n + 1 ) − 1 \begin{aligned} \operatorname{ASL} &=\frac{1}{n}\left(\sum_{i=1}^{j} i \cdot 2^{i-1}\right) \\ &=\frac{n+1}{n} \log _{2}(n+1)-1 \\ & \approx \log _{2}(n+1)-1 \end{aligned} ASL​=n1​(i=1∑j​i⋅2i−1)=nn+1​log2​(n+1)−1≈log2​(n+1)−1​

使用条件：要排序、顺序存储；不易更新

分块检索

块内无序，块间有序

索引表：各块中最大关键码、各块起始位置、块中有效元素个数

A S L = A S L b + A S L w ASL=ASL_b+ASL_w ASL=ASLb​+ASLw​(块间+块内)

缺点：增加一个辅助索引表；初始有分块排序；元素大量增删/分布不均匀

散列表的检索（Hash)

重要概念：

负载因子： α = n / M \alpha=n/M α=n/M(n:散列表结点数，M:散列表空间大小)

冲突：将不同关键码映射到相同的散列地址

同义词：发生冲突的两个关键码

冲突解决方法：

• 开散列（拉链法）：

  同义词都链接在同一链表 α \alpha α可>1

  • 拉链方法（适用于内存）

    处理冲突简单

    缺点：同义词表中的元素可能存储在不同磁盘页中，检索一个关键码值时可能引起多次磁盘访问，从而增加检索时间（即元素数量超过了一个页块的储存空间）

  • 桶式散列（适用于外存）

    散列文件记录分为若干桶，每个桶包含若干页块

    桶内各页块用指针链接

    h(K)表示具有关键码K的记录所在的桶号

    磁盘访问：调存储桶目录表进入内存（1次访外）；逐个检查桶内各页块（平均：页块数/2次访外）【与拉链法对比，目的是尽量把同一个桶中出现的元素塞到同一个页块中】

• 闭散列（开地址法）：

  发生冲突的关键码存储在散列表中另一个空地址内

  d 0 = h ( K ) d_0=h(K) d0​=h(K)称为基地址

  当冲突发生时，使用某种方法为关键码K生成一个候选的散列地址序列，称为探查序列

  d i = d 0 + p ( K , i ) d_i=d_0+p(K,i) di​=d0​+p(K,i)是后继散列地址，p(K,i)为探查函数

  探查方法：

  • 线性探查法：缺点：对应连续的基地址，探查序列也是几乎相同的

    聚集：基地址不同的记录，争夺同一后继地址序列

    成功/失败查找ASL的计算：注意取模的散列函数基地址可能不会占整个散列表

  • 二次探查法：基本解决了不同基地址探查序列重合

    d 2 i − 1 = ( d + i 2 ) % M d_{2i-1}=(d+i^2)\%M d2i−1​=(d+i2)%M; d 2 i = ( d − i 2 ) % M d_{2i}=(d-i^2)\%M d2i​=(d−i2)%M

  • 伪随机数序列探查法：越随机越好，缺点：随机序列需要保存

  基本聚集：基地址不同的关键码，其探查序列的某些段重叠在一起【伪随机探查和二次探查可以消除基本聚集】

  二级聚集：如果两个关键码散列到同一个基地址，还是得到同样的探查序列，所产生的聚集（探查序列只是基地址的函数，与关键码无关）

  • 双散列探查法：同义词的探查序列与同义词本身关键码有关（一个基地址上有不同的探查序列）

注意%M

注意失败查找（各种树那里没找到就是失败，不用多一个，散列表区分开！！！

注意散列表非mod值基地址访问的计数！！！