1.定义

哈希函数就是将关键字和它的存储位置之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。按这个思想建立的表为哈希表。

2.哈希函数的构造方法

2.1 直接定址法

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

2.2 数字分析法

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

2.3 平方取中法

取关键字平方后的中间几位为哈希地址。

2.4 折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址，这方法称为折叠法。

2.5 除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即：             H(key) = key MOD p, p<=m

2.6 随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key)，其中random为随机函数。

3.冲突处理方法

冲突是指由关键字得到的哈希地址的位置上已存有记录。处理冲突是为该关键字的记录找到另一个“空”的哈希地址。

在处理冲突的过程中可能得到一个地址序列Hi(i=1,2,…,k)，即在处理哈希地址的冲突时，若得到的另一个哈希地址H1 仍然发生冲突，则再求下一个地址H2 ，若H2 仍然冲突，再求H3 。以此类推，直至Hk 不发生冲突为止，则Hk 为记录在表中的地址。

通常处理冲突的方法有以下几种：

3.1 开放地址法：

Hi = (H(key) + di) MOD m (i = 1, 2, … , k. k<m) 其中：H(key)为哈希函数；m为哈希表表长；di 为增量序列。 di 可有下列3中取法：

1. 线性探测再散列：di = 1, 2, 3, …, m-1;
2. 二次探测再散列：di = 12 , -12 , 22 , -22 , 32 , … , ±k2 , (k<=m/2);
3. 伪随机探测再散列：di = 伪随机数序列。

从线性探测再散列可以发现：当表中i, i+1, i+2位置上已填有记录时，下一个哈希地址为i, i+1, i+2和i+3的记录都将填入i+3的位置，这种在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象称作二次聚集，即在处理同义词的冲突过程中又添加了非同义词的冲突。

3.2 再哈希法

Hi = RHi(key) (i = 1, 2, … , k) RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。

3.3 链地址法

将所有关键字为同义词的记录存储在同一线性链表中。

4.查找长度

虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量哈希表的查找效率的量度。

在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。

哈希表的装填因子定义为    α = n m frac nm mn n为表中填入的记录数，m为哈希表的长度 采用链地址法时，α也是每个链表的平均长度。

设平均查找长度为Sn , 则   Sn ≈ - 1 α frac 1α α1ln(1-α)

因此，哈希表的平均查找长度是α的函数，而不是n的函数。不管n多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内。

如果哈希表的长度与元素的个数成比例，则n = o(m)，那么   α = n m frac nm mn = o ( m ) m {o(m) over m} mo(m) = o(1) 因此，查找都是常量时间。