数据结构与算法 - 这篇文章属于一个选集。

§ 13: 本文

搜索
#

查找
#

对于无重复的keys，找到一个record所对应的key

评价指标

平均查找长度ASL：查找若干个记录需要的平均关键字比较次数

成功查找

找得到

不成功查找

找不到（遍历完）

精确查找

specific key

模糊查找

a specific range of keys

主要方法

顺序查
二分/折半查找
直接查 哈希神教
索引查找（tree indexing）

关键字排序查找
#

折半查找

搜索频度排序记录查找
#

$ASL=\sum{ip_i}$

pi：各记录被查找的归一化频度

事先通过实验统计得到
实时动态更新

n：记录条数

ASL

频度相等：(n+1)/2
指数分布：2

80/20 rule – 二八定律

$ASL \approx 0.1n$

组织方式
#

自组织
#

搜索频度高的向前放

启发式决策

Count 历史搜索频度排序
Move to Front 找到一个记录就往前放
Transpose 交换它和它前面

无论怎么操作，（如上方式）$ASL > 1$

直接访问
#

事先知道关键字在表中的位置

$ASL = 0$

关键字与记录在表中的存储位置间有一个确定的关系hashing

哈希/散列
#

把关键词映射到表中存储位置的过程
- 一个哈希函数
  - 函数h
- 一个哈希/散列表
  - 数组HT：M个槽，槽号0~M-1

构造原则
#

MUST映射返回在区间（0~M-1）
SHOULD尽可能让记录在表中均匀分布

除留取余法

关键字取值远大于M

平方取中法

关键字为数字

折叠法

关键字为字符串/数字位数多
sum » M

ELF Hash

其它方法

直接定址法（线性函数）
随机数法（rand（key））
数字分析法
- 提取均匀分布的若干位或它们的组合作为地址

总的原则是使产生冲突的可能性降到尽可能地小

冲突
#

哈希是一个压缩映射
- key1!=key2, h(key1)=h(key2)
- 具有相同余数的关键字。。。
解决
- 构造适当的哈希函数
- 处理冲突

处理冲突
#

对于每个记录i对应其home position h(ki)

当冲突发生时，为产生地址冲突的记录寻找下一个哈希地址

闭域法（very important）/开放定址
#

对于$H_0,H_1,H_2,...,H_s, 1\leq s \leq m-1$

$H_0=h(key), H_i=(H_0+d_i) \% m, i=1,2,3,...,s$

增量序列$d_i=p(i)$

线性探测
- $d_i=i$
- 不够均匀
  - 二次聚集（存在h(k1)=h(k2)，则它们探测结果是一样的）冲突超级加倍
    - 解决办法：双哈希
    - $H_i=(H_0+P(K,i))\%m=(h(k)+d_i*h_2(k))\%m$
平方探测
- $d_i=1^2,-1^2,2^2,-2^2$
随机探测
- 伪随机数列