c++ - 从 0 到最大值的 uint64_t 键的最佳哈希函数是什么？

Question

假设我们有一组元素并希望将它们存储在 HashMap 中(例如 std::unordered_set )，并且每个元素都有一个 uint64_t 类型的键其值可以从 0 到其最大可能值变化，使用普通散列函数是否是最佳选择，其中键的散列值是键本身？它是否取决于使用的容器(即 Google 的稀疏哈希与来自 STL 的 std::unordered_map)？键值出现的概率未知。

Answer 1

如果您需要散列的只是具有未知概率的任何可能值的 uint64_t，并且您的输出必须是 uint64_t，那么您不会通过更改该值获得任何优势。只需使用 key 本身。

如果您对值的分布有所了解，或者您的值被限制在较小的范围内(这实际上与了解分布是一回事)，那么对键应用转换可能是有益的，但是这取决于容器的实现。当表将哈希转换为桶索引时，您只会通过减少冲突而受益，但这取决于表的算法和表的当前/平均状态(每个桶的使用频率)。