哈希表实现的哈希算法

Question

我正在寻找一个高速哈希函数，具有良好（即近似均匀）的分布，用于哈希表实现。

哈希表将仅用于存储具有整数键的值。

我可以只使用整数的低位作为哈希吗？

例如，int key = n＆15; 并创建一个具有16个插槽的数组来存储它们。

有任何推荐吗？

- user1157123

---

没有所谓的完美哈希函数。不过，如果你想要一些对应源代码的算法，请参见这里：http://partow.net/programming/hashfunctions/index.html。 - David Brabant

只取最低位可能是最糟糕的选择。（但：这完全取决于您在int键中期望的值范围）尝试混合使用高位，或者乘以足够大的（奇数、质数）数字。了解预期并进行测量。 - wildplasser

将以下与编程有关的内容从英语翻译为中文。仅返回已翻译的文本：将您的评论发布为答案，我会接受它。 - user1157123

Answer 1

您可以在这里看到xxhash

您提到的哈希函数速度很快，但也很糟糕。 如果您想要一个“愚蠢”的哈希函数，也许可以考虑取模。

示例：

int key = item % size_of_hash_table

- Andrea Masullo

Answer 2

昨晚我写了一个多功能哈希测试（用C语言），覆盖了几个顶尖的哈希算法和38个不同的密钥。

欢迎大家在以下链接进行基准测试： http://www.overclock.net/t/1319572/benchmarking-the-fastest-hash-function/0_20#post_18495990

如果您能提供帮助，我很乐意揭示Intel与AMD以及Intel 12.1编译器与Microsoft 16（VS2010）编译器组合的表现如何。

- Georgi