哈希法又称散列法，相应的表称为哈希表。
基本思想：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址...
哈希法又称散列法，相应的表称为哈希表。
基本思想：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。
冲突：当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2 ，但 f(k1) =f(k2)，此时称k1和k2为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。
因此哈希法需要注意两个问题：
① 如何构造哈希函数
② 如何处理冲突
构造哈希函数的原则主要有两个：
③ 函数本身便于计算；
④ 计算出来的地址分布均匀，即对任一关键字k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突。
通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。常用的解决冲突方法主要有三种：
① 开放定址法（再散列法）：
基本思想：当关键字k的哈希地址p=f(k) 出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
这种方法有一个通用的再散列函数形式：fi = (f(k) + di) % m，i = 1, 2, …, n，其中f(k)为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同，主要有以下3种：
a. 线性探测再散列：di = 1, 2, …, m - 1，冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
b. 二次探测再散列：di = 12, -12, 22, -22, …, k2, -k2(k <= m / 2)，冲突发生时，在表的左右进行跳跃式探测，比较灵活。
c. 伪随机探测再散列：di = 伪随机数序列，建立一个伪随机数发生器，如i = (i + p) % m，并给定一个随机数做起点。
② 再哈希法
同时构造多个不同的哈希函数，当哈希地址f1(k) 发生冲突时，再计算f2(k)，…，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
③ 链地址法
基本思想：将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
