对于以上两节中讨论的各种结构，它们的平均查找长度不仅不可能为0，并且都随 n（关键字集合的大小）的增长而增长。因为无论是在表示静态查找表的顺序表和有序表中，还是动态查找树表中，数据元素在结构中的位置都是随机的，和它的关键字无关。在这样的结构中进行查找的主要操作就是将给定值和表中关键字进行依次比较，其查找效率取决于比较次数。如果希望不经过比较直接取得其关键字等于给定值的记录，只能是在确定知晓该关键字在表中位置的情况下。例如，某城市人口调查表中的关键字为"年龄"，当以表长为120的有序表表示时，查询年龄为60岁的人口数时只需要直接取表中第60项的记录即可，显然，此时的平均查找长度为0。一般情况下，可设记录在表中的位置为关键字的某个函数，通常称这种函数为"哈希函数"。
例如，对于关键字序列{ Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei }，可设关键字的哈希函数如下：
其中，CH1 表示关键字中第1个字母，Ord 为字符的次序函数。则以表长为14的顺序表表示的查找表如右所示。显然，此查找表的平均查找长度为 0，若给定值为 Qian，由上述关键字函数得到函数值为 8，即可从"地址为8"的表中取得该记录。但这样的函数并不容易设计，如果同时存在关键字 Zhou，则上述函数不可取，换句话说，为使平均查找长度等于0，必须找到一个能将查找表中所有关键字都"散列"在表中不同位置的哈希函数。
若关键字不同而函数值相同，则称这两个关键字（对于该哈希函数而言）为"同义词"，并称这种现象为"冲突"。对于动态查找表很难找到不存在同义词的哈希函数，唯一弥补的办法是，在发生冲突时设法解决之，例如将关键字Zhou存入表中地址为0的空缺中等。
综合以上所述，可如下定义哈希表：
根据设定的哈希函数 H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的"象"作为相应记录在表中的存储位置，这种表被称为哈希表，这一映象的过程亦被称为"散列"。
从以上讨论得知，平均查找长度是对查找效率的一种度量，其含义为，在查找表中进行一次查找所需进行的给定值和关键字比较次数的平均值。那么能否找到一种结构使它的平均查找长度为零呢？
|
0
|
|
||||||||||||||
|
1
|
|||||||||||||||
|
2
|
|||||||||||||||
|
3
|
|||||||||||||||
|
4
|
|||||||||||||||
|
5
|
|||||||||||||||
|
6
|
|||||||||||||||
|
7
|
|||||||||||||||
|
8
|
|||||||||||||||
|
9
|
|||||||||||||||
|
10
|
|||||||||||||||
|
11
|
|||||||||||||||
|
12
|
|||||||||||||||
|
13
|
以下将分别讨论哈希函数的构造方法和处理冲突的方法。