查找的基本概念

查找表是由同一类型的数据元素（或记录）构成的集合。

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。

关键字：用来标识一个数据元素（或记录）的某个数据项的值。

查找算法的评价指标：关键字的平均比较次数，也称平均查找长度。

线性表的查找：

1. 顺序查找

应用范围：顺序表或线性链表表示的静态查找表；表内元素之间无序。

优点：算法简单，逻辑次序无要求

缺点：ASL太长，时间效率太低

2. 折半查找（二分）

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

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

缺点：只适用于有序表，且限于顺序存储结构。

3. 分块查找（索引顺序查找）

查找效率：ASL=Lb+Lw（对索引表查找的ASL+对块内查找的ASL）

数表的查找：

二叉排序树

平衡二叉树（左<根<右）

散列表的查找：

基本思想：记录的存储位置与关键字之间存在对应关系

对应关系---hash函数

优点：查找效率高，O(1)

缺点：空间效率低

散列方法（杂凑法）：选取某个函数时，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。

散列函数：散列方法中使用的转换函数

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

同义词：具有相同函数值的多个关键字

构造散列函数考虑的因素：

1. 执行速度

2. 关键字的长度

3. 散列表的大小

4. 关键字的分布情况

5. 查找频率

构造方法：

直接定址法：

优点：以关键码key的某个线性函数值为散列地址，不会产生冲突

缺点：要占用连续地址空间，空间效率低

除留余数法：hash（key）=key mod p（p是一个整数）

处理冲突的方法：

1. 开放定址法：

基本思想：有冲突时就去寻找下一个空的散列地址

常用：

线性探测法

二次探测法

2. 链地址法

基本思想：相同散列地址的记录链成一单链表

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

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

链地址法优于开地址法。

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