查找

 查找表

　　查找表是由同一类型的数据元素组成的集合。

　　对查找表通常有4种操作：

　　(1)    查询某个“特定的”数据元素是否在查找表中；

　　(2)    检索某个数据元素的各种属性；

　　(3)    在查找表中插入一个数据元素；

　　(4)    在查找表中删除某个元素。

　　前两种统称为“查找”操作。

　　若只对查找表进行查找操作，这种查找表称为静态查找表；还有其余操作，则为动态查找表。

　　关键字：是数据元素中某个数据项的值，用它可标识一个数据元素。

　　查找表的效率，通过平均查找长度ASL进行衡量。

 

静态表的查找

　　1、  顺序查找

　　查找过程是从第一个记录开始逐个对记录的关键字的值进行比较。

　　顺序查找与其他查找方法比，查找成功的平均查找长度较长，但对表没什么特别的要求，并且线性链表只能进行顺序查找。

　　2、  有序表的查找

　　指查找表的元素按关键字有序。

　　有序表的查找一般采用折半查找实现。

 

动态查找表

　　动态查找表是在查找过程中动态生成的。如果在查找表中没有查找成功，就插入给定元素。常用的3种实现方法：

　　1、  二叉排序树

　　2、  二叉平衡树AVL

　　3、  B树

哈希表

　　前面讨论的数据结构（线性表、树）中，记录在结构中相对位置是随机的，和记录的关键字之间不存在确定关系，因此，在结构中查找记录时需要进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上。

　　顺序查找时，比较的结果为“=”与“!=”两种可能；在折半查找、二叉排序树查找和B-树查找时，比较结果为“<”、"="、">"三种可能。查找的效率依赖于查找过程中所进行的比较次数。

　　理想的情况是，不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f(k)。若结构中存在关键字和K相等的记录，则必定在f(k)的存储位置上，由此，不需要进行比较便可取得所查记录。

　　我们称这个对应关系f为哈希（Hash）函数，按这个思想建立的表为哈希表（Hash Table）。

 

　　哈希函数是一个映像，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长的允许范围之内即可；

　　对不同的关键字key，可能得到同一哈希地址。这种现象称为冲突（collision）。具有相同函数值的关键字对哈希函数来说称作同义词

 

　　一般情况下，冲突只能尽可能少，而不能完全避免。因为一般情况下，哈希函数是一个压缩映像，这就不可避免产生冲突。

　　

　　一、哈希表的定义

　　综上，可以如下定义哈希表：

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

　　

　　二、哈希函数的构造方法

　　首先清楚什么是好的哈希函数？

　　若对于关键字集合中的任意个关键字，经哈希函数映射到地址及集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数。换句话说，就是使关键字经过哈希函数得到一个随机的地址，以便使一组关键字的哈希地址均匀分布地在整个地址区间，从而减少冲突。

　　常用的构造哈希函数的方法有多种，如等关键字的一次函数等。

　　实际工作中考虑的因素有：

　　(1) 计算哈希函数所需时间（包括硬件指令的因素）；

　　(2) 关键字的长度；

　　(3) 哈希表的大小；

　　(4)关键字的分布情况；

　　(5)记录的查找频率；　　　　

 

　　三、处理冲突的方法

　　均匀的哈希函数可以减少冲突，但是不能完全避免。

　　处理冲突的基本思想：若一个关键字的哈希地址冲突了，则为关键字的记录找到另一个空的哈希地址。在处理冲突时，可能得到一个地址序列H(i)（在哈希地址范围内）。依次取这些地址，直到不冲突。

　　1、开放定址法

　　2、再哈希法

　　3、链地址法

　　4、建立一个公共溢出区

 

　　四、哈希表的查找及其分析

　　在哈希表上查找的过程和哈希比造表的过程基本一致。由key值根据哈希函数求得哈希地址，若此位置没有记录，查找失败；否则比较关键字，若和给定值相等，则查找成功；否则根据设定的处理冲突的方法查找下一地址，直到某个位置为空or查找成功。