如何检查我的自定义哈希在哈希映射中是否良好?

我会通过stl::hash_map运行一个(大)数据集。完成后,我将使用以下方法收集所有bucket的结果

从 hash_map :

size_type elems_in_bucket (size_type __n) const;

最后,我会计算 标准偏差(SD) 的 元素到桶分配 .

我会为不同的散列函数执行上述操作。无论哪一个哈希函数产生的最小sd都是赢家(对于这个数据集)。

最好的办法可能是将哈希算法带到一个int数组中,并在给定真实数据的情况下计算每个哈希桶被击中的次数。(我建议把stl从等式中去掉,真的。)

如果您最终看到大量真实数据的计数出现高偏差,那么当有大量空(或空)桶可用时,哈希算法将生成大量冲突。

注意,“高偏差”是一个相对术语。一个好的散列算法是一个确定性的随机过程,任何随机过程都有可能产生奇怪的结果,所以要经常测试,测试好,并且尽可能使用实际的问题域作为测试和控件的源。