这个例子中最好的字符串哈希函数是什么？

Question

我有一个类型为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）。

请告诉我如何使哈希函数更加均匀。

- user2872568

Answer 1

在这种情况下构建哈希函数的常见方法是使用一些具有质数系数的多项式，就像下面这个例子一样：

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哈希，这也可以获得良好的分散性，但不太直观。

希望这能有所帮助！

- templatetypedef

---

这太棒了。你是怎么得到那些数字的？31 137 1517。获取它们的算法是什么？ - user2872568

仅仅是大质数。小质数更容易产生冲突。 - leemes

@user2872568- 这里强烈推荐使用质数；它们具有更好的分散特性。我建议避免使用漂亮的十的倍数。 - templatetypedef

Answer 2

一种方法是构建一个保证无冲突的数字（当然，这不会使您的哈希表无碰撞），只要可能的键适合整数类型（例如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。最后只需对这个整数进行哈希处理即可。

- leemes