性能用ASL（查找成功时的平均查找长度）来衡量

线性表检索

顺序检索

• 逐个比较
• 优点：插入元素可以直接加在表尾
• 缺点：检索时间太长

二分检索法

• 条件：序列必须有序
• 实现：

   1 template <class Type> int BinSearch (vector<Item<Type>*>& dataList, int length, Type k){
   2     int low=1, high=length, mid;
   3     while (low<=high) { //结束条件！！
   4         mid = (low+high)/2;
   5         if (k<dataList[mid]->getKey())
   6             high = mid-1; //右缩检索区间
   7         else if (k>dataList[mid]->getKey())
   8             low = mid+1; //左缩检索区间
   9         else return mid; //成功返回位置
  10     }
  11     return 0;
  12 } //检索失败，返回0

• 性能分析：最大检索长度（完全二叉树的高度）：$log_2^{n+1}$；失败的检索长度$log_2^{n+1}$向上或向下取整；平均的检索长度和最大检索长度接近：$log_2^{n+1}-1$
• 优点：快
• 缺点：要排序，不易更新

分块检索

• 思想：两级检索。将元素分为多块，块内的关键码不一定有序，但块间有序（前块中最大关键码<后块中最小关键码）；索引表中包含每个块最大的关键码和起始位置，以及每个块里元素的个数。
• 性能：查找长度是两级检索的查找长度总和
• 优点：更新容易
• 缺点：
• 需要一个辅助索引表
• 分块需要排序
• 元素分布不均匀、大量插入或删除时性能下降

散列表检索（HASH）

基本概念

• 带检索的关键码K
• 散列函数h(K)：关键码K的存储位置
• 负载（装填）因子：$α=\frac{n}{M}$（n，散列表中已有结点数；M，散列表空间大小）
• 冲突：将不同关键码映射到相同散列地址
• 同义词：发生冲突的两个关键码

各类方法

除余法

• $h(x)=x mod M$
• M值通常选择质数，有利于均匀分布
• 潜在缺点：连续的关键码映射为连续的散列值，散列性能降低

乘余取整法

• $h(x)=n*(A*key\% 1)$

平方取中法

• 求关键码的平方，再取其中的几位或其组合作为散列地址
• 最接近随机化

数字分析法

• 分析每一位上不同符号出现频率，选取其中各种符号均匀分布的若干位作为散列地址

基数转换法

• 把关键码看成是另一进制上的数后，再把它转换成原来进制上的数。取其中若干位作为散列地址
• 一般取大于原来基数的数作为转换的基数，并且两个基数要互素。

折叠法

• 将关键码分割为位数相同的几部分，取这几部分的叠加和（舍去进位）作为散列地址。
• 两种叠加方法：移位叠加（各部分以最后一位对齐）；分界叠加（沿各部分的分界来回折叠，对齐相加）

冲突的解决方法

开散列方法

拉链法（适用于内存）

• 思路：所有同义词链接在同一链表，以拉链状拉开。每个槽定义为一个链表的表头。
• 这时候α可以大于1，但一般还是取小于1
• 优点：适合表长不确定的情况，增删结点容易。
• 缺点：如果散列表元素在磁盘里，拉链法不适用。
  • 同义词表中的元素元素在不同的磁盘页中的话，检索一个特定关键码时将引起多次磁盘访问，增加检索时间

桶式散列（适合存储于磁盘的散列表）

• 思想：散列文件记录分为若干桶，每个桶包含几个页块，每个页块有若干记录，各页块用指针链接。h(k)表示具有关键码K的记录所在桶号。
• 性能：桶目录表最多一次访外，逐个检查桶内页块，平均访外次数为桶内页块数一半。修改、插入等需另1次访外写外存。

闭散列方法（开地址法）

基本聚集：堆积，散列地址不同的记录，争夺同一后继散列地址，导致很长的探查序列，伪随机探查和二次探查可以消除基本聚集

二级聚集：如果两个关键码散列到同一基地址还是得到同一探查序列。

• 把发生冲突的关键码存储在散列表中另一个空地址内
• $d_0=h(K)$为K的基地址
• $d_i=d_0+p(K,i)$是后继散列地址，p(K,i)是探查函数
• 搜索空位时，若基地址结点已被占用，逐个寻找探查序列中的空闲位置。如果找遍了都没有，说明列表满了，报告溢出。

线性探查法

• 思想：逐个逐个往后找……$p(K,i)=i$
• 优点：所有的存储位置都可以作为插入记录的候选
• 缺点：聚集
• 改进：每次跳过c个槽而不是1个
  • 第i个槽是$(h(K)+ic)mod M$，探查函数是$p(K,i)=i*c$
  • 基位置相邻点记录不会进入同一个探查序列
  • 但相隔c的还是纠缠在一起

二次探查

• 地址公式：$d_{2i-1}=(d+i^2)%M;d_{2i}=(d-i^2)%M$
• 探查函数：$p(K,2i-1)=i*i;p(K,2i)=-i*i$
• 基本聚集消失

伪随机数序列探查

• 探查函数$p(K,i)=perm[i-1]$
  
  • perm是一个长度为M-1的数组，一个值在[1,M-1]的随机序列
• 基本聚集消失

双散列探查法

• 思想：使用两个散列函数$h_1$和$h_2$
• 若在$h_1(K)=d$发生冲突，计算h_2(K)得到的探查序列为探查序列：$d_i=(d+i*h_2(key))%M$
  • $(d+h_2(K))\% M$
  • $(d+2h_2(K))\% M$
  • $(d+3h_2(K))\% M$…
• 探查函数：$p(K,i)=i*h_2(K)$
• $h_2(K)$必须与M互素（否则可能会发生同义词地址的循环计算）
• 优点：不易产生聚集
• 缺点：计算量增大（也不是很大）

闭散列的算法设计

• 插入
  • 找到基地址空间
  • 基地址空间不空，循环找下一个探查序列直到关键码值相同或找到空位
• 检索
  • 基地址空间未被占用，检索失败，否则将在基地址中的值和K比较，相等则成功。
  • 否则查找探查序列循环。直到找到相等关键码或未被占用的地址空间。
• 删除
  • 开散列可以随意删除
  • 闭散列只能作标记，不能真正删除，除非之后再次分配空间。不然会影响检索操作
    • 设置一特殊的标记位（墓碑）：单元被占用\空单元\已删除
    • 插入时遇到墓碑，要继续沿着探查序列找到真正空位，为了防止插入两个相同的关键码
    • 效率分析：不依赖于n，与α有关。α小时性能高。$α\leq 0.5$时，大部分操作的分析预期代价都小于2。负载因子的临界值是0.5，超过性能就会急剧下降。
    • 

       

【复习笔记】数据结构-检索

原文：https://www.cnblogs.com/yalphait/p/10085526.html