如何测试哈希函数?

您必须使用从预期的相同(或类似)分布中提取的数据来测试散列函数。当查看64位长的散列函数时,如果输入值从所有可能的长值一致地绘制,则默认的Java哈希函数是优秀的。

但是,您提到了应用程序使用long存储两个基本上独立的32位值。尝试生成一个与实际使用的值类似的值样本,然后用它进行测试。

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

对于特定的应用程序,不要简单地将它们异或在一起,而是尝试以一个典型的好的哈希函数将两个独立的int组合在一起的方式组合32位值。即乘以素数,再加上。

首先,我认为你必须定义一个好的自我传播是什么意思。您的意思是所有可能的输入都有一个好的排列,还是只是一个可能的输入有一个好的排列?

例如,如果您正在散列表示正确完整(名字+姓氏)名称的字符串,那么您可能不会关心使用数字ASCII字符散列的情况。

至于测试,您最好的选择是获得一组您期望的巨大或随机的数据输入集,并将其推送到哈希函数中,然后查看排列是如何结束的。不太可能有一个魔法程序可以说“是的,这是一个很好的哈希函数,适合您的用例。”。但是,如果您可以编程地生成输入数据,那么您应该能够轻松地创建一个生成大量数据的单元测试,然后验证排列是否在良好定义范围内。

编辑: 在64位长的情况下,是否真的有理由使用散列图?为什么不直接使用一个平衡树,直接使用long-as键而不是重新刷新它呢?您在整体节点大小(键值的大小是键值的两倍)上支付了一点罚金,但最终可能会节省性能。

如果使用链接哈希表,您真正关心的是冲突的数量。这对于作为哈希表上的一个简单计数器实现来说是微不足道的。每次插入一个项目并且表格必须链接时,增加一个链计数器。一个更好的哈希算法将导致更少的冲突。要签出的一个好的通用表哈希函数是: djb2

根据您的澄清:

我在Java中使用了长的值,第一个32位编码了一个ID,第二个32位编码了另一个ID。不幸的是,Java的长值散列仅仅用第二个32位来表示第一个32位,在我的情况下,当在哈希表中使用时,这导致了非常差的性能。

在分配两个ID值的方式和散列映射实例的大小之间,似乎有一些不愉快的“共鸣”。

您是显式调整地图大小,还是使用默认值?QAD检查似乎表明 HashMap<Long,String> 从16个桶结构开始,溢出时加倍。这意味着只有ID值的低阶位实际参与哈希桶选择。您可以尝试使用一个接受初始大小参数并使用初始大小创建映射的构造函数。

或者,DaveL关于定义自己的长键散列的建议将允许您避免低位依赖性问题。

另一种看待这个问题的方法是,使用一个基元类型(long)作为避免定义一个真正的类的方法。我建议您通过定义业务类,然后在自己的类上实现散列编码、相等性和其他适当的方法来管理这个问题,看看您可以获得哪些好处。