相关术语及概念

查找表（Search Table）:是由同一类型的数据元素构成的集合
查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记录，则查找成功，否则查找不成功
关键字（Key）：用来标识一个数据元素的数据项。
主关键字、次关键字

静态查找表（Static Search Table） ：查找过程中查找表本身不发生变化的查找表。（无插入、删除操作）
动态查找表（Dynamic Search Table）: 查找过程中查找表本身发生变化(插入或删除元素)的查找表。

9.1 静态查找表

顺序表的查找

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

顺序查找的特点：
优点：算法简单，对表中元素排列没有要求，实际应用较多，特别是记录少时较有效
缺点：ASL太长，时间效率太低

有序表查找

折半查找

查找成功时：
比较次数=路径上的结点数=结点的层数
比较次数≤树的深度=⌊log_2n⌋+1

查找不成功时：
比较次数=路径上的内部结点数
比较次数≤⌊log_2n⌋+1

分块查找

9.2 动态查找表

动态查找表的特点：表结构本身是在查找过程中动态生成的。即对给定的关键字，若在表中存在，则查找成功，否则插入该关键字的记录。

二叉排序树

平衡二叉树（Balanced Binary Tree）（又称AVL树）

B-树和B+树

一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：
(1) 树中每个结点至多有m棵子树;
(2) 若根结点不是叶子结点，则至少有两棵子树;
(3) 除根之外的所有非终端结点至少有 ⌈m/2⌉棵子树
(4) 所有非终端结点中包含下列信息数据
（n , A0，K1 , A1 , K2 ,A2，…Kn ,An ）
其中：Ki ( i=1,…,n )为关键字，且Ki＜Ki＋1(i=1,…,n－1)；Ai (i=0,…,n)为指向子树根结点的指针，且指针Ai－1所指子树中所有结点的关键字均小于Ki(i=1,…,n)，An所指子树中所有结点的关键字均大于Kn，n(⌈m/2⌉-1≤n≤m-1)为关键字的个数(或n＋1为子树个数)。
(5)所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

9.3 哈希表

基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法

哈希表：
根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表就叫做哈希表。这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址

使用哈希表要解决好两个问题
构造好的哈希函数
所选函数尽可能简单，以便提高转换速度
所选函数对关键字计算出的地址，应在哈希地址集中均匀分布，以减少空间浪费
制定好的解决冲突的方案
查找时，如果从哈希函数计算出的地址中查不到关键字，应依据解决冲突的规则，有规律地查询其他相关单元

哈希函数的构造方法

处理冲突的方法：

线性探测法特点：
优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。
缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率

哈希表的查找

给定查找值K：
根据造表时的哈希函数求哈希地址H(K)
若表中这个位置没有记录，则查找不成功
否则比较关键字，若和给定值相等，则查找成功
否则根据设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为空或者表中关键字等于给定值为止。

哈希表技术具有很好的平均性能，优于一些传统的技术
链地址法优于开放定址法
除留余数法做哈希函数优于其他类型函数、