如何测试哈希函数？

有没有办法测试哈希函数的质量？我想在哈希表中使用时有一个很好的传播,如果在单元测试中可以验证它会很好.

编辑:为了澄清,我的问题是我使用longJava中的值,使得前32位编码ID,第二位32位编码另一个ID.不幸的是,Java的长值散列只是将前32位与第二位32位异或,这在我的情况下导致在使用时的性能非常差HashMap.所以我需要一个不同的哈希,并希望有一个单元测试,以便这个问题不再蔓延.

首先,我认为你必须通过对自己的良好传播来定义你的意思.您是指对所有可能的输入进行良好的传播,还是仅为可能的输入提供良好的传播？

例如,如果您正在散列表示正确的完整(第一个+最后一个)名称的字符串,那么您可能不会关心使用数字ASCII字符散列的内容.

至于测试,你最好的选择是获得你期望的大量或随机输入数据集,并通过哈希函数推送它,看看传播是如何结束的.可能不会有一个魔术程序可以说"是的,这对你的用例来说是一个很好的哈希函数." 但是,如果您可以以编程方式生成输入数据,则应该能够轻松地创建生成大量数据的单元测试,然后验证扩展是否在您的定义中.

编辑:在64位长的情况下,是否真的有理由使用哈希映射？为什么不直接使用平衡树,直接使用long作为密钥而不是重新使用它？您在整体节点大小(键值大小的2倍)上支付一点点罚款,但最终可能会将其保存在性能上.

您必须使用从您期望它处理的相同(或类似)分发中提取的数据来测试您的哈希函数.当查看64位长的散列函数时,如果从所有可能的长值统一绘制输入值,则默认的Java散列函数非常好.

但是,您已经提到应用程序使用long来存储基本上两个独立的32位值.尝试生成与您期望实际使用的值类似的值的示例,然后使用它进行测试.

对于测试本身,获取样本输入值,对每个值进行散列并将结果放入集合中.计算结果集的大小,并将其与输入集的大小进行比较,这将告诉您哈希函数生成的冲突数.

对于您的特定应用程序,不要简单地将它们一起进行异或,而是尝试将32位值组合在一起,典型的良好散列函数将组合两个独立的int.即乘以素数,然后加上.

如果您使用链式哈希表，那么您真正关心的是冲突次数。将其实现为哈希表上的简单计数器将是微不足道的。每次插入项目并且表必须链接时，增加一个链接计数器。更好的哈希算法将导致更少的冲突。检出的通用表哈希函数很好：djb2