查找的基本概念
查找表是由同一类型的数据元素（或记录）构成的集合。
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。
关键字：用来标识一个数据元素（或记录）的某个数据项的值。
查找算法的评价指标：关键字的平均比较次数，也称平均查找长度。
线性表的查找：
顺序查找
应用范围：顺序表或线性链表表示的静态查找表；表内元素之间无序。
优点：算法简单，逻辑次序无要求
缺点：ASL太长，时间效率太低
折半查找（二分）
每次将待查记录所在区间缩小一半。
优点：效率比顺序查找高。
缺点：只适用于有序表，且限于顺序存储结构。
分块查找（索引顺序查找）
查找效率：ASL=Lb+Lw（对索引表查找的ASL+对块内查找的ASL）
数表的查找：
二叉排序树
平衡二叉树（左<根<右）
散列表的查找：
基本思想：记录的存储位置与关键字之间存在对应关系
对应关系---hash函数
优点：查找效率高，O(1)
缺点：空间效率低
散列方法（杂凑法）：选取某个函数时，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。
散列函数：散列方法中使用的转换函数
冲突：不同的关键码映射到同一个散列地址
同义词：具有相同函数值的多个关键字
构造散列函数考虑的因素：
执行速度
关键字的长度
散列表的大小
关键字的分布情况
查找频率
构造方法：
直接定址法：
优点：以关键码key的某个线性函数值为散列地址，不会产生冲突
缺点：要占用连续地址空间，空间效率低
除留余数法：hash（key）=key mod p（p是一个整数）
处理冲突的方法：
开放定址法：
基本思想：有冲突时就去寻找下一个空的散列地址
常用：
线性探测法
二次探测法
链地址法
基本思想：相同散列地址的记录链成一单链表
优点：非同义词不会冲突，无“聚集”现象，链表上结点空间动态申请，更适合于表长不确定的情况
散列表技术具有很好的平均性能，优于一些传统的技术。
链地址法优于开地址法。
除留余数法作散列函数优于其他类型函数。