数据结构 哈希表(Hash Table)_哈希概述

哈希表支持一种最有效的检索方法：散列。

从根来上说，一个哈希表包含一个数组，通过特殊的索引值（键）来访问数组中的元素。

哈希表的主要思想是通过一个哈希函数，在所有可能的键与槽位之间建立一张映射表。哈希函数每次接受一个键将返回与键相对应的哈希编码或哈希值。键的数据类型可能多种多样，但哈希值的类型只能是整型。

计算哈希值和在数组中进行索引都只消耗固定的时间，因此哈希表的最大亮点在于它是一种运行时间在常量级的检索方法。当哈希函数能够保证不同的键生成的哈希值互不相同时，就说哈希表能直接寻址想要的结果。但这只是理想状态，在实际运用过程中，能够直接寻址结果的情况非常少。

通常与各种各样的键相比，哈希表的条目数相应较少。因此，绝大多数的哈希函数会将一些不同的键映射到表中相同的槽位上。当两个键映射到一个相同的槽位上时，它们就产生了冲突。一个好的哈希函数能最大限度的减少冲突，但冲突不能完全消除，我们仍要想办法处理这些冲突。

链式哈希表的描述

链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”，我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时，首先将其键传入一个哈希函数（该过程称为哈希键），函数通过散列的方式告知元素属于哪个“桶”，然后在相应的链表头插入元素。查找或删除元素时，用同们的方式先找到元素的“桶”，然后遍历相应的链表，直到发现我们想要的元素。因为每个“桶”都是一个链表，所以链式哈希表并不限制包含元素的个数。然而，如果表变得太大，它的性能将会降低。

解决冲突

当哈希表中两个键散列到一个相同的槽位时，这两个键之间将会产生冲突。链式哈希表解决冲突的方法非常简单：当冲突发生时，它就将元素放到已经准备好的“桶”中。但这同样会带来一个问题，当过多的冲突发生在同一槽位时，此位置的“桶”将会变得越来越深，从而造成访问这个位置的元素所需要的时间越来越多。

在理想情况下，我们希望所有的“桶"以几乎同样的速度增长，这样它们就可以尽可能的保持小的容量和相同的大小。换句话说，我们的目标就是尽可能的均匀和随机地分配表中的元素，这种情况在理论上称为 均匀散列，而在实际中，我们只能尽可能近似达到这种状态。

如果想插入表中的元素数量远大于表中的“桶‘的数量，那么即使是在一个均匀散列的过程中，表的性能也会迅速下降。在这种情况下，表中所有的”桶“都变得越来越深。因此，我们必须要特别注意一个哈希表的负载因子，其定义为：

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=2^p ,那么h仅仅是k的p个最低阶位。通常我们选择的m会是一个素数，且不要太接近于2的幂，同时还要考虑存储空间的限制和负载因子。

例如，如果我们想往一个链式哈希表中插入n=4500个左右的元素，会选择m=1699（m是一个介于2¹⁰~2¹¹之间的素数）。由此可以计算出它的负载因子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=0;
    ptr=key;
    
    while(*ptr != '\0')
    {
        unsigned int tmp;
        val = (val << 4) + (*ptr);
        
        if(tmp = (val & oxf0000000))
        {
            val = val ^ (tmp >> 24);
            val = val ^ tmp;
        }
        
        ptr++;
    }
    /*在实际操作中，使用实际大小代替PRIME_TBLSIZ*/
    return val % PRIME_TBLSIZ;
}

另外一篇文章中，我们将详细讨论链式哈希表的接口定义与实现分析。