哈希表支持一种最有效的检索方法:散列。
从根来上说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中的元素。
哈希表的主要思想是通过一个哈希函数,在所有可能的键与槽位之间建立一张映射表。哈希函数每次接受一个键将返回与键相对应的哈希编码或哈希值。键的数据类型可能多种多样,但哈希值的类型只能是整型。
计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是一种运行时间在常量级的检索方法。当哈希函数能够保证不同的键生成的哈希值互不相同时,就说哈希表能直接寻址想要的结果。但这只是理想状态,在实际运用过程中,能够直接寻址结果的情况非常少。
通常与各种各样的键相比,哈希表的条目数相应较少。因此,绝大多数的哈希函数会将一些不同的键映射到表中相同的槽位上。当两个键映射到一个相同的槽位上时,它们就产生了冲突。一个好的哈希函数能最大限度的减少冲突,但冲突不能完全消除,我们仍要想办法处理这些冲突。
链式哈希表的描述
链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”,我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时,首先将其键传入一个哈希函数(该过程称为哈希键),函数通过散列的方式告知元素属于哪个“桶”,然后在相应的链表头插入元素。查找或删除元素时,用同们的方式先找到元素的“桶”,然后遍历相应的链表,直到发现我们想要的元素。因为每个“桶”都是一个链表,所以链式哈希表并不限制包含元素的个数。然而,如果表变得太大,它的性能将会降低。
解决冲突
当哈希表中两个键散列到一个相同的槽位时,这两个键之间将会产生冲突。链式哈希表解决冲突的方法非常简单:当冲突发生时,它就将元素放到已经准备好的“桶”中。但这同样会带来一个问题,当过多的冲突发生在同一槽位时,此位置的“桶”将会变得越来越深,从而造成访问这个位置的元素所需要的时间越来越多。
在理想情况下,我们希望所有的“桶"以几乎同样的速度增长,这样它们就可以尽可能的保持小的容量和相同的大小。换句话说,我们的目标就是尽可能的均匀和随机地分配表中的元素,这种情况在理论上称为 均匀散列,而在实际中,我们只能尽可能近似达到这种状态。
如果想插入表中的元素数量远大于表中的“桶‘的数量,那么即使是在一个均匀散列的过程中,表的性能也会迅速下降。在这种情况下,表中所有的”桶“都变得越来越深。因此,我们必须要特别注意一个哈希表的负载因子,其定义为:
a=n / m
其中n是表中的元素的个数,m是桶的个数。在均匀散列的情况下,链式哈希表的负载因子告诉我们表中的”桶“能装下元素个数的最大值。
例如,有一个链式哈希表,其”桶“的数量是m=1699,元素的数量n=3198,其负载因子a=3198/1699=2。所以在这种情况下,当查找元素时,可能每个”桶“里面的元素个数不超过两个。当有一个表的负载因子小于1时,这个表每个位置所包含的元素不超过1个。当然,由于均匀散列是一个理想的近似的情况,因此在实际情况中我们往往会检索超过负载因子建议的数值。如何达到更接近于均匀散列的情况,最终取决于如何选择哈希函数。
选择哈希函数
一个好的哈希函数旨在均匀散列,也就是,尽可能以均匀和随机的方式散布一个哈希表中的元素。定义一个哈希函数,它将键k映射到哈希表中的位置x。x称为k的哈希编码,正式的表述为:
h(k) = x
一般来说,大多数的散列方法都假设k为整数,这样k能够很容易地以数学方式修改,从而使得h能够更均匀地将元素分布在表中。当k不是一个整数时,我们也可以很容易的将它强制置转换为整型。
如何强制转换一组键,很大程度上取决于键本身的特点。所以,在一个特定的应用中,尽可能地获取键的特性尤为重要。例如,如果我们想对程序中的标识符进行散列,会发现程序中有很多相似的前缀和后缀,因为开发人员倾向于将变量声明为类似sampleptr、simpleptr和sentryptr的名字。我们可以将键严格按照键的开头和结尾字符来强制转换,但这显然不是一个好办法,因为对于一个k会有多个整数与之对应。另一方面,我们不妨随机地从4个位置来选择字符,然后随机地改变它们的顺序,并将它们封装到一个4字节的整数中。要记住,无论用什么样的方法来强制转换键,目的都是尽可能选择一个能将键均匀、随机地分布到表中的哈希函数。
取余法
一种简单地将整型k映射到m槽位的散列方法是计算k除以m所得到的余数。我们称之为取余法,正式的表述为:
h(k) = k mod m
如果有m=1699个位置,而要散列的键k = 25657,通过这种方法得到哈希编码为25657 mod 1699 = 172。通常情况下,要避免m的值为2的幂。这是因为假如m=2p ,那么h仅仅是k的p个最低阶位。通常我们选择的m会是一个素数,且不要太接近于2的幂,同时还要考虑存储空间的限制和负载因子。
例如,如果我们想往一个链式哈希表中插入n=4500个左右的元素,会选择m=1699(m是一个介于210~211之间的素数)。由此可以计算出它的负载因子a=4500/1699约等于2.6,根据均匀散列表述,这说明表中每个“桶”大概能容纳2~3个元素。
乘法
与取余法不同的是乘法。它将整型k乘以一个常数A(0<A<1);取结果的小数部分;然后再乘以m取结果的整数部分。通常情况下,A取0.618,它由5的开平方减1再除以2得到。这个方法称为乘法,正式的表述为:
h(k) = m(kA mod 1), 其中A约等于0.618
这个方法有个优点是,对于表中槽位个数m的选择并不需要像取余法中那么慎重。例如:如果表有m=2000个位置,散列的键k=6341,那么得到的哈希编码为2000X(6341X0.618 mod 1) = 2000X(3918.738 mod 1)=2000X0.738=1476。
在链式哈希表中,如果期待插入的元素个数n不超过4500个,可以让m=2250。这样得到的负载因子a=4500/2250=2,根据均匀散列的规则,在每个“桶”中存储的元素个数一般不超过两个。同时,这个散列方法可以让我们更加灵活地选择m,以便获取我们可以接受的最大“桶”深。
示例1列举了一个能够较好的处理字符串的哈希函数。它通过一系列的位操作将键强制转换为整数。所有这些整数都是通过取余法得到的。这个哈希函数针对哈希字符串执行的很好。
示例1:一个适用于处理字符串的哈希函数
/*hashpjw.c*/
#include "hashpjw.h" unsigned int hashpjw(const void *key)
{
const char *ptr;
unsigned int val;
/*通过一系列的位操作,将键强制转换为整数*/
val=;
ptr=key; while(*ptr != '\0')
{
unsigned int tmp;
val = (val << ) + (*ptr); if(tmp = (val & oxf0000000))
{
val = val ^ (tmp >> );
val = val ^ tmp;
} ptr++;
}
/*在实际操作中,使用实际大小代替PRIME_TBLSIZ*/
return val % PRIME_TBLSIZ;
}
另外一篇文章中,我们将详细讨论链式哈希表的接口定义与实现分析。