c++ - 如何检查 hash_map 中我的自定义哈希是否良好？

Question

我已经在 stdext::hash_map 中为我的自定义键编写了自定义哈希，并想检查哈希器是否良好。我使用的是 VS 2008 提供的 STL。据我所知，典型的检查是检查存储桶之间分布的均匀性。

我应该如何正确组织这样的检查？我想到的一个解决方案是修改 STL 源代码，向 hash_map 添加一个方法，该方法可以遍历存储桶并完成主题。有没有更好的方法？

也许，从 hash_map 派生并创建这样的方法？

Answer 1

您最好的选择可能是将哈希算法应用于整数数组，并在给定实际数据的情况下计算每个哈希桶被命中的次数。 (我真的建议将 STL 排除在外。)

如果您最终发现大量实际数据的计数存在很大偏差，则当有大量可用的空(或更空)存储桶时，您的哈希算法会产生大量冲突。

请注意，“高偏差”是一个相对术语。一个好的哈希算法是一个确定性的随机过程，任何随机过程都有可能产生奇怪的结果，因此经常测试，好好测试，并尽可能使用您的实际问题域作为测试和控制的来源。