欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

散列:散列函数与散列表(hash table)

程序员文章站 2022-03-15 20:40:51
...

1. 散列函数

如果输入的关键字是整数,则一般合理方法是直接返回对表大小取模(Key mod TableSize)的结果,除非 Key 碰巧具有一些不太理想的特质。如,表的大小为 10,而关键字都是 10 的倍数,显然此时都会被散列在 0 的位置。

为了避免上述情况的发生,好的方法是保证表的大小是素数(除了 1 和自身没有其他的因子)。当输入的关键字是随机整数时,散列函数不仅算起来简单而且关键字的分配也相对均匀。

考虑,关键字是字符串的情况:

typedef unsigned int Index;

Index hash(const char *key, int tableSize){
    unsigned int hashVal = 0;
    while (*key != '\0')
        hashVal += *key++;
    return hashVal % tableSize;
}

上述的散列函数实现起来简单而且能很快地算出答案。不过,如果表很大,则函数将不会很好地分配关键字。例如,TableSize = 10007(10007 是素数),并设所有的关键字至多 8 个字符长。char 型变量的 ASCII 最多为 127,因此散列函数大致只能在 0 和 127*8 = 1016,显然不是一种均匀的分配。

假设需要对这样的字符串进行散列,Key 至少有两个字符+NULL 结束符。

Index hash(const char* key, int tableSize){

    return (key[0] + 27*key[1] + 729*key[2]) % tableSize;
}
  • 27:26 个英文字符 + 空格
  • 729:27**2

涉及所有关键字字符的 hash:

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