哈希表

哈 希 表

传统上，在表中查找一个指定记录的方法都是遍历表中的所有记录直到出现一个匹配的关键字为止，可以顺序查找，也可以二分法查找，但这种查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中的一个惟一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此，可以直接取得所查记录。这个对应关系f称为哈希（Hash）函数，按这个思想建立的表为哈希表。

哈希表的规范化定义：根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像（mapping）到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置。这一映像过程成为哈希表或散列，所得存储位置称为哈希地址或散列地址。

哈希函数是从关键字集合到地址集合的映像，因此哈希函数的设定很灵活。只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。对不同关键字可能得到同一哈希地址，即key1 != key2，而Hash(key1) == Hash(key2)，这种现象称为冲突（collision），具有相同函数值的关键字对该哈希函数来说称作同义词（synonym）。

在一般情况下，冲突只能尽可能地少，而不能完全避免。选择一个恰当的哈希函数可以减少冲突的发生，那么什么是好的哈希函数呢？若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的（uniform）哈希函数。换句话说，就是使关键字经过哈希函数后得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

常用的构造哈希函数的方法有：
(1) 直接定址法：取关键字或关键字的线性函数值为哈希地址，即Hash(key)=key 或 Hash(key)=a*key+b，其中a和b为常数。直接定址法不会产生冲突。
(2) 数字分析法：取关键字的若干位组合为哈希地址，选取位的原则是该位上的数字分布大致均匀。
(3) 平方取中法：取关键字平方后的中间几位为哈希地址，
(4) 折叠法(folding)：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到哈希地址。
(5) 除留余数法：H(key)=key%p，p<=n（表长），p的选择很重要，若p选的不好，容易产生同义词。一般情况下，可以选p为质数或不包含小于20的质因素的合数。
(6) 随机数法：H(key)=random(key)，随机数法比较适合关键字长度不等时的情况。

常用的处理冲突的方法有：
假设哈希表的地址集合为0~(n-1)，冲突是指由关键字得到的哈希地址为j (0<=j<=n-1)的位置上已经存有记录，则处理冲突就是为该关键字的记录找到另一个空的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi (i=1,2,...k)，即在处理哈希地址的冲突时，若得到的另一个哈希地址H1仍然发生冲突，则再求下一个地址H2，直至Hk不发生冲突为止，则Hk为记录在表中的地址。

(1) 开放定址法：Hi=(H(key)+di)%n，di为增量序列，可以有3种取法，

a、线性探测再散列：di=1,2,3,...,n-1.  即依次取冲突位置的下一位置。
b、二次探测再散列：di=1^2,-1^2,2^2,-2^2,3^2,...,k^2,-k^2.
c、伪随机探测再散列：di=伪随机数序列.

(2) 再哈希法：Hi=RHi(key)，RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不容易产生聚焦，但增加了计算时间。
(3) 链地址法：将所有关键字为同义词的记录存储在同一线性链表中。
(4) 建立一个公共溢出区：假设哈希函数的值域为[0, n-1]，则该向量HashTable[0,1,...,n-1]为基本表，每个分量存放一个记录；另设立向量OverTable[0,1,...,v]为溢出表，所有关键字和基本表中关键字为同义词的记录，一旦发生冲突，都填入溢出表。


哈希表的查找：