查找的基本概念

• 查找表是由同一个类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。

• 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）
• 关键字：用来标识一个数据元素（或记录）某个数据项的值
1. 主关键字：可唯一地标识一个记录的关键字是主关键字；
2. 次关键字：反之，用来识别若干记录的关键字是次关键字。

若查找表中存在这样一个记录，则”查找成功”。 查找结果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”。 查找结果出“空记录”或“空指针”。

• 对查找表经常进行的操作
1. 查询某个“特定的”数据元素是否在查找表中；
2. 检索某个“特定的”数据元素的各种属性；
3. 在查找表中插入一个数据元素；
4. 删除查找表中的某个数据元素。

• 查找表可分为两类
1. 静态茶渣表：仅作“查询”（检索）操作的查找表
2. 动态查找表：作“插入”和“删除”操作的查找表
• 有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素，此类表位动态查找表。

• 查找算法的评价指标：关键字的平均比较次数，也称平均查找长度ASL(Average Search Length)

• 查找过程中我们要研究什么？

线性表的查找

顺序查找（线性查找）

应用范围

1. 顺序表或线性链表表示的静态查找表

2. 表内元素之间无序

• 数据元素类型定义

• 顺序表的定义

• 在顺序表ST中查找值为key的数据元素

• 把待查关键字key存入表头（“哨兵”、“监视哨”），从后往前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

当 ST.length 较大时，能使进行一次查找所需的平均时间几乎减少一半。

时间效率分析

• 顺序查找的性能分析
1. 时间复杂度：O(n)
• 查找成功时的平均查找长度，设表中各记录查找概率相等，
2. 空间复杂度：一个辅助空间——O(1)

讨论

1. 记录的查找概率不相等时如何提高查找效率？

• 查找表存储记录原则——按查找概率高低存储；
1. 查找概率越高，比较次数越少；
2. 查找概率越低，比较次数较多。

1. 记录的查找概率无法测定时如何提高查找效率？

• 方法——按查找概率动态调整记录顺序；
1. 在每个记录中设一个访问频度域；
2. 始终保持记录按非递增有序的次序排列；
3. 每次查找后均将刚查到的记录直接移至表头。

顺序查找的特点

• 优点：算法简单，逻辑次序无要求，且不同存储结构均适用。

• 缺点ASL太长，时间效率太低。

折半查找（二分或对分查找）

折半查找

• 每次将待查记录所在区间缩小一半。

折半查找算法：（非递归算法）

1. 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值

2. 初始时，令low=1，high=n，mid=(low+high)/2

3. 让k与mid指向的记录比较
• 若key==R[mid].key，查找成功
• 若key<R[mid].key，则high=mid—1
• 若key>R[mid].key，则low=mid+1

4. 重复上述操作，直到low>high时，则查找失败

折半查找的特点

• 优点：效率比顺序查找高。

• 缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）。

分块查找

索引顺序查找

分块查找性能分析

• 查找效率

分块查找的特点

• 优点：插入和删除比较容易，无需进行大量移动。

• 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算

• 适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

查找方法比较

散列表（哈希表）的查找

散列表的基本概念

• 基本思想：记录的存储位置与关键字之间存在对应关系，对应关系——hash函数，

• 如何查找

优点：查找效率高 缺点：空间效率低

• 散列表的若干术语
• 散列方法（杂凑法）：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行对比，确定查找是否成功。
• 散列函数（杂凑函数）：散列方法中使用的转换函数。
• 冲突：不同的关键码映射到同一个散列地址。，但是

散列函数的构造方法

• 散列存储：选取某个函数，依该函数按关键字计算元素的存储位置。

• 冲突：不同的关键码映射到同一个散列地址

在散列查找方法中，冲突是不可能避免的，只能尽可能减少。

• 使用散列表要解决好两个问题

• 构造散列函数考虑的因素
1. 执行速度（即计算散列函数所需时间）
2. 关键字的长度
3. 散列表的大小
4. 关键字的分布情况
5. 查找频率

• 直接定址法

• 除留余数法

处理冲突的方法

开放定址法（开地址法）

• 基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

链地址法（拉链法）

• 基本思想：相同散列地址的记录链成一单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

• 链地址法建立散列表步骤

• 优点
1. 非同义词不会冲突，无“聚集”现象
2. 链表上结点空间动态申请，更适合于表长不确定的情况

散列表的查找过程

• 给定值查找值k

散列表的查找效率分析

• 使用平均查找长度ASL来衡量查找算法，ASL取决于

1. 散列函数

2. 处理冲突的方法

3. 散列表的装填因子

越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

结论

1. 散列表技术具有很好的平均性能，优于一些传统的技术

2. 链地址法优于开地址法

3. 除留余数法作散列函数优于其他类型函数