对于线性表、队列、树这些数据结构，它们的记录在结构中是随机的，而且和记录的关键字之间并不存在确定关系，查找某个元素时需要进行一系列与关键字的比较，即这种查找是建立在“比较”的基础上。所以查找的效率依赖于比较的次数，那么如何才能不经过比较直接找到记录所在位置呢？刚才说到上述数据结构的关键字与记录位置之间是不存在确定关系的，那么我们可以让这两者之间建立一种确定关系，也就是我们所说的对应关系f，使得每个关键字都与结构中一个唯一存储位置相对应。在查找时，通过给定值k以及对应关系f，便可以找到k值所对应的像f(k)。所以，在查找某个记录时，不需要比较便可以直接取得所查记录。那么这种对应关系f就是哈希函数，通过这个思想建立的表称为哈希表。

哈希函数是从关键字集合到地址集合的映像。通常，关键字集合比较大，它的元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。哈希函数其实是一个压缩映像，那么这种情况就不可避免的产生冲突，那么在建造哈希表时不仅要设定一个好的哈希函数，还要设定一种处理冲突的方法。（设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表就是哈希表，映像的过程为哈希造表或散列，所得的存储位置称哈希地址或散列地址）

取关键字或关键字的某个线性函数值为哈希地址。即H(key)=key 或 H(key)=a*key+b   (a,b为常数)。

举例1：统计1-100岁的人口，其中年龄作为关键字，哈希函数取关键字自身。查找年龄25岁的人口有多少，则直接查表中第25项。

举例2：统计解放以后出生人口，其中年份作为关键字，哈希函数取关键字自身加一个常数H(key)=key+(-1948).查找1970年出生的人数，则直接查(1970-1948)=22项即可。

若关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

举例：有80个记录，其关键字为8位十进制数，假设哈希表长，则可取两位十进制数组成哈希地址，为了尽量避免冲突，可先分析关键字。

经分析，发现第一位、第二位都是8,1，第三位只可能取3或4，第八位只可能取2,5或7，所以这四位不可取，那么对于第四、五、六、七位可看成是随机的，因此，可取其中任意两位，或取其中两位与另外两位的叠加求和舍去进位作为哈希地址。

取关键字平方后的中间几位为哈希地址。（较常用的一种）

举例：为BASIC源程序中的标识符键一个哈希表（假设BASIC语言允许的标识符为一个字母或者一个字母和一个数字两种情况，在计算机内可用两位八进制数表示字母和数字），假设表长为512=，则可取关键字平方后的中间9位二进制数为哈希地址。（每3个二进制位可表示1位八进制位，即3个八进制位为9个二进制位）

A ：01 （A的ASCII码值为65,65的八进制为101，取后两位表示关键字）

B：02 （B的ASCII码值为66,66的八进制为102，取后两位表示关键字）

...

Z：32（Z的ASCII码值为90,90的八进制为132，取后两位表示关键字）

...

0：60（0的ASCII码值为48,48的八进制为60，取后两位表示关键字）

...

9：71（9的ASCII码值为57,57的八进制为71，取后两位表示关键字）

0010000

将关键字分割成位数相同的几部分（最后一部分的位数可不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。适用于关键字位数比较多，且关键字中每一位上数字分布大致均匀时。

举例：根据国际标准图书编号（ISBN）建立一个哈希表。如一个国际标准图书编号  0-442-20586-4的哈希地址为：

      5864                                                                                                                5864

      4220                                                                                                                0224

+        04                                                                                                             +      04

                 10088                                                                                                               6092

                移位叠加                                                                                                          间接叠加

H（key）=0088（将分割后的每一部分的最低位对齐）                       H（key）=6092（从一端向另一端沿分割界来回叠加）

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址（p为素数）

H（key）=key  MOD  p，p