数据结构与算法分析 —— C 语言描述：散列函数

对散列函数而言，如果输入的关键字是整数，则一般合理的方法就是直接返回“Key mod TableSize” 的结果，除非 Key 碰巧具有某些不理想的性质。在这种情况下，散列函数的选择需要仔细考虑，例如，若表的大小是 10 而关键字都以 0 为个位，则此时上述标准的散列函数就是一个不好的选择。其原因我们将在后面讨论，而为了避免上述情况，好的办法通常是保证表的大小事素数。当输入的关键字是随机整数时，散列函数不仅算起来简单而且关键字的分配也很均匀。

通常，关键字是字符串；在这种情况下，散列函数需要仔细地选择。

一种选择办法是把字符串中字符的 ASCII 码值加起来。例如，设 TableSize = 10007（10007 是素数），并设所有的关键字至多 8 个字符长。由于 char 型量的值最多是 127，因此散列函数只能假设值在 0 和 1016 之间，其中 1016 = 127 * 8。显然，这不是一种均匀的分配。

另一个散列函数如下：

Index
Hash( const char *key, int TableSize)
{
    return ( Key[0] + 27 * Key[1] + 729 * Key[2]) % TableSize;
}

这个散列函数假设 Key 至少有两个字符外加 NULL 结束符。值 27 表示英文字母表的字母个数外加一个空格，而 。该函数只考察前三个字符，但是，假如它们是随机的，而表的大小像前面那样还是 10007，那么我们就会得到一个合理的均衡分配。可不巧的是，英文不是随机的。虽然三个字符（忽略空格）有 种可能的组合，但查验词汇量足够大的联机辞典却揭示： 3个字母的不同组合数只有 2851 种。即使这些组合没有冲突，也不过只有表的 被真正散列到。因此，虽然很容易计算，但是当散列表足够大的时候这个函数还是不合适的。

第三种散列函数如下：

Index
Hash(const char *key, int TableSize)
{
    unsigned int HashVal = 0;
    while ( *key != '\0')
        HashVal = ( HashVal << 5) + *Key++;

    return HashVal % TableSize;
}

这个散列函数涉及关键字种所有的字符，并且一般可以分布得很好（它计算 ，并将结果限制在适当的范围内）。程序根据 Horner 法则计算一个（32 的）多项式函数。例如，计算 的另一种方式是借助公式 进行。Horner 法则将其扩展到用于 n 次多项式。

我们之所以用 32 代替 27，是因为用 32 坐乘法不是真的去乘，而是移动二进制的 5 位，为了加速，在程序的加法可以用按位异或来代替。

上面描述的散列函数就表的分布而言未必是最好的，但是确实具有极其简单的优点（如果允许溢出，那么速度也很快）。如果关键字特别长，那么该散列函数计算起来将会花费过多的时间，不仅如此，前面的字符还会左移出最终的结果。在这种情况下，通常做的做法是不使用所有的字符。此时关键字的长度和性质将影响选择。例如，关键字可能是完整的街道地址，散列函数可以包括街道地址的几个字符，也许是城市名和邮政区码的几个字符。有些程序设计人员通过只使用奇数位置上的字符来实现他们的散列函数，这里有这么一层想法：用计算散列函数节省下的时间来补偿由此产生的对均匀分布的函数的轻微干扰。

剩下的主要变成细节是解决冲突的消除问题。如果当一个元素被插入处另一个元素已经存在（散列值相同），那么就产生一个冲突，这个冲突需要消除。解决这种冲突的方法有几种，其中最简单的两种分别为：分离链接法和开发地址法。