散列：散列函数与散列表（hash,table）.docx（全文完整）

下面是小编为大家整理的散列：散列函数与散列表（hash,table）.docx（全文完整）,供大家参考。

　散列：散列函数与散列表（hash table ）

　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;

　}

推荐访问:散列：散列函数与散列表（hash 函数 完整 全文