选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定的值计算地址，将给定的值与地址单元中元素关键字进行比较，确定是否查找成功，即哈希方法。

    哈希方法中使用的转换函数即为哈希函数。按照这个思想构造的表叫做哈希表。

    通常关键字的集合比哈希地址集合大得多，所以经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突。

    映射到同一哈希地址上的关键字称为同义词。

    所选函数尽可能简单，便于提高转换速度。

    所选函数对关键字计算出的地址，应该哈希地址集合中大致均匀分布，以减少空间浪费。

    Hash(key) = a * key + b (a、b为常数)

    即取关键字的某个线性函数值为地址。这类函数是一一对应的关系，不会产生冲突。

    缺点：要求地址的集合大小等于关键字集合大小，所以当关键字的集合很大时不适用。

    Hash(key) = key mod + p (p是一个整数)

    即取关键字除以p的余数作为哈希地址。选取合适的p很重要。

    若哈希表长度为m，则要求p ≤ m，且接近m或者等于m。

    Hash(key) = [b * (a * key mod 1)] (a、b均为常数，且 0 < a < 1， b为整数)

    (a * key mod 1)为取 a * key 的小数部分，这里乘余取整法以关键字 key 乘以 a 后的小数部分，再乘以整数 b的整数部分作为哈希地址。

    一般a的取值为（√5 - 1）∕ 2 ≈ 0.6180339 较为理想，b的取值并不关键。

    假设在关键字的集合中，每个关键字均由 m 位组成，每位上可能有 r 中不同的符号。

    例如，若关键是4位的十进制数，那么 m = 4，r = 10。

    数字分析法根据 r 种不同的符号在各位上的分布情况，选组某几位组合成哈希地址。所选取的位应该满足各种符号在该位上出现的频率大致相同。

    假设有一组关键字如下：

        7 5 1 0 0 3

        7 5 1 1 2 6

        7 6 0 3 0 2

        7 6 0 7 1 8

        7 5 0 4 2 1

        7 6 0 2 1 5

    上面的关键字都是6位，其中第4位和第6位分布比较均匀，可以取这两位作为哈希地址，即03、16、32、78、41、25。

    将关键字平方后，按哈希表的大小，取中间的若干位作为哈希地址。

    将关键字从左到右分成位数相等的几部分，最后一部分位数可以短一些，然后分别将这几部分叠加求和，最后按照哈希表的表长，取后几位作为哈希地址。有两种叠加方式：移位法[将各部分的最后一位对齐相加]、边界叠加法[从一端向另一端沿各部分来回折叠后，最后一位对齐相加]。

    例如，关键字253 463 587 05

    移位法：253 + 463 + 587 + 05 = 1308

    边界叠加法：253 + 364 + 587 + 50 = 1254

    当哈希表的长度为1000时，可以取后三位作为哈希地址，分别为308、254。

以上的哈希函数的举例，可以从哈希函数构造方法查看，很详细。

    一旦产生冲突，就去寻找下一个空的哈希地址。只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。

   Hi = (Hash(key) + di ) mod m (1 ≤ i < m)

    其中，Hash(key)是哈希函数，m是哈希表的长度，di 增量序列 1，2，···，m - 1, 且di = i 。

   Hi = (Hash(key) ± di) mod m

    其中，Hash(key)是哈希函数，m是哈希表的长度，di 为增量序列 1²，-1²，2²，-2²，···，q²，-q² 且 q ≤ m / 2 。

   Hi = (Hash(key) + i * ReHash(key)) mod m (i = 1, 2,··· , m - 1)   

    Hash(key) 和 ReHash(key) 是两个哈希函数，m是哈希表的长度。

    例如：Hash(key) = a时产生地址冲突，接下来计算ReHash(key) = b，

    H1= (a + b) mod m

    H2= (a + 2b) mod m

    ···

    Hm - 1= (a + (m - 1) * b) mod m     

    假设哈希函数得到的哈希地址域在区间[0, m - 1]上，建立m个空链表，由哈希函数对关键字转换后，映射到同一哈希地址 i 的同义词均加入同一个链表。

    例如，哈希函数Hash(key) = key mod 11， 关键字序列为47，29，7，16，11，92，8，22，3，50，37，89，94，21

    用拉链法处理冲突后，建表如下：

    假设哈希函数得到的哈希地址域在区间[0, m - 1]上，则分配两个表：

    base_table[m]：每个单元只能存放一个元素

    over_table[k]：如果在base_table上产生冲突，则所有的产生冲突的同义词都存放到这个表里

    查找时，先对给定的值计算出的哈希地址在base_table中查找，查找不到，再从over_base中查找。

哈希表的平均查找长度ASL = 总查找长度／关键字集合大小

注：总查找长度为所有关键字查找次数之和

哈希表的装填因子α = 填入表中的元素个数／哈希表的长度

α是哈希表装满程度的标志。当哈希表的长度一定时，α与填入表中的元素个数成正比。即α越大，填入的元素越多，产生冲突的概率越大。

哈希方法存取速度快，同时也比较节省空间，使用于动态查找和静态查找。但由于存取随机，所以不便于顺序查找。