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;
}