3

我有一个 AcccAA 类型的键，其中 A-[A...Z]（大写字母），c 是 [1..9]。我有 1500 段。现在我的临时哈希函数

int HashFunc(string key){   
    int Adress = ((key[0] +  key[1] + key[2] + key[3] + key[4] + key[5]) - 339) * 14;
    return  Adress;
}

和 Excel 在中心显示很多碰撞（从 400 到 900）

请告诉我散列函数更均匀。

4

2 回答 2

3

在这种情况下，构建散列函数的一种常用方法是评估一些具有素数系数的多项式，如下所示：

int address = key[0] + 
              31 * key[1] + 
              137 * key[2] + 
              1571 * key[3] + 
              11047 * key[4] + 
              77813 * key[5];
return address % kNumBuckets;

这在关键空间上产生了更大的分散。现在，你会遇到很多冲突，因为字谜喜欢AB000A并且BA000A会发生冲突，但是使用上面的哈希函数，哈希对输入中的微小变化更加敏感。

对于更复杂但（可能）更好的散列函数，考虑使用像shift-add-XOR hash 这样的字符串散列函数，它也有很好的分散性，但不太直观。

希望这可以帮助！

于 2013-10-27T21:37:43.203 回答
1

一种方法是构造一个保证无冲突的数字（当然这不会使您的哈希表无冲突），只要可能的键适合整数类型（例如int）：

int number = (key[0] - 'A') + 26 * (
              (key[1] - '0') + 10 * (
               (key[2] - '0') + 10 * (
                (key[3] - '0') + 10 * (
                 (key[4] - 'A') + 26 * (
                  (key[5] - 'A')
             )))));

这很有效，因为26 * 10 * 10 * 10 * 26 * 26 = 17576000它适合int罚款。

最后简单地散列这个整数。

于 2013-10-27T21:41:52.410 回答