哈希查找

Java 中有HashMap，了解哈希的原理，不仅有助于用好HashMap，也有助于理解其它开源产品，甚至自己可以编写效率更高的哈希算法，例如在MemCached（著名的Cache开源产品）中，客户端根据key值定位到哪台server上，用的是求模哈希函数，进行哈希表的地址定位。

 

哈希最主要是用在查找上，可以说是查找效率最高的算法，但是用好哈希，还是需要了解原理，因为好的哈希实现，首先要解决哈希地址的冲突问题，为什么会造成冲突，请看下面的原理：

 

哈希表是用来查找元素的，在多种类型的查找中，例如顺序查找时，比较的结果为“=”与“<>”两种可能，在折半查找、二叉排序树查找和B-树插好时，比较的结果为“<”、“=”和“>”三种可能，查找的效率依赖于查找过程中所进行的比较次数。

 

理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的key之间建立一种确定的对应关系f，似的每个关键字和结构中一个唯一的存储位置相对应，因而在查找时，只要根据这个对应关系f找到给定值K的像f（K）。若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上，由此，不需要进行比较便可以直接存取所查记录。在此，我们称这种对应关系f为哈希函数，按这个思想建立的表为哈希表。

 

哈希函数是一个映像，因此哈希函数的设定很灵活，只要使得任何关键字由此所得到的哈希函数值都落在表长允许范围之内即可；

 

对不同的关键字可能得到同一个哈希地址，即key1<>key2,而f（key1）=f（key2），这种现象称“冲突”。在一般情况下，冲突只能进可能地少，而不能完全避免。因为，哈希函数是从关键字集合到地址集合的映像。通常，关键字集合比较大，它的元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。

 

一。哈希函数

 

哈希函数的构造方法很多，好的哈希函数对哈希表的查找性能有直接影响：

 

若对于关键字集合中的任意一个关键字 ，经哈希函数映像到地址集合中的任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，一遍使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

1.直接定址法：

 

取关键字或者关键字的某个线性函数值为哈希地址。即：H（key）=a.key+b

其中a和b为常数

 

直接定址所得地址集合和关键字集合的大小相同。因此，对于不同的关键字会发生冲突，但实际中能使用这种哈希函数的情况很少。

2.数字分析法

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

事先知道数据的特点，比较少见，可适用的场合比较少。在此不再赘述。

 

3.平方取中法

取关键字的平方后的中间几位为哈希地址。这是一种较常见的构造哈希函数的方法。通常在选择哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数的平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

4.折叠法

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

 

5.求模法

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

 

H(key)=key MOD p p<=m

这是一种最简单，也是最常用的构造哈希函数的方法，它不仅可以对关键字直接取模（MOD），也可在折迭、平方取中等运算之后取模。

 

注意，在使用求模发时，对p的选择很重要。若p选的不好，容易生成相同的哈希地址。

 

由众人的经验得知：一般情况下，可以选p为质数或者不包含小于20的质因素的合数。

注：质数为除了1或者自身整除的数称为质数。例如2是最小的质数。

6.随机数法：

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H（key）=random（key），其中random为随机函数。通常当关键字长度不等时采用此法构造哈希函数较恰当。

二、处理冲突的方法

上面讲到均匀的哈希函数可以减少冲突，但不能避免，因此，如何处理冲突是哈希造表不可缺少的另一方面。

 

假设哈希表的地址集0-(n-1),冲突是指由关键字得到的哈希地址为j(0<=j<=n-1)的位置上已存有记录，则处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。

 

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

1.开放定址法