排列的好哈希函数？

Question

我有特定范围内的数字(通常从0到1000左右).算法从该范围中选择一些数字(大约3到10个数字).这种选择经常进行,我需要检查是否已经选择了所选数字的排列.

例如,一步选择[1, 10, 3, 18]另一步,[10, 18, 3, 1]然后第二选择可以被丢弃,因为它是一种置换.

我需要非常快速地进行检查.现在我把所有数组都放在一个hashmap中,并使用一个自定义哈希函数:只需要总结所有元素,所以1 + 10 + 3 + 18 = 32,还有10 + 18 + 3 + 1 = 32.对于equals,我使用bitset来快速检查元素是否在两个集合中(我在使用bitset时不需要排序,但它只在数字范围已知且不太大时才有效).

这样可以正常工作,但是可以产生大量冲突,因此很常调用equals()方法.我想知道是否有更快的方法来检查排列？

排列是否有任何好的哈希函数？

UPDATE

我做了一个基准测试:生成0到6范围内的所有数字组合,以及数组长度1到9.有3003种可能的排列,并且应该在这么多不同的哈希值附近生成一个好的哈希值(我使用32位数字)对于哈希):

• 仅添加41种不同的哈希(因此存在大量冲突)
• 8个不同的哈希值用于XOR'ing值
• 用于乘法的286种不同的哈希值
• (R + 2e)3003个不同的哈希值和abc建议的乘法值(使用1779033703表示R)

所以abc的哈希值可以非常快速地计算出来并且比其他所有哈希值都要好得多.谢谢!

PS:我不想在不需要时对值进行排序,因为这会变得太慢.

Answer 1

一个潜在的候选人可能是这个.修复一个奇数整数R.对于每个要散列的元素e计算因子(R + 2*e).然后计算所有这些因素的乘积.最后将产品除以2得到哈希值.

(R + 2e)中的因子2保证所有因子都是奇数,因此避免产品将变为0.最后除以2是因为乘积总是奇数,因此除法只是去除了一个常数位.

例如,我选择R = 1779033703.这是一个随意的选择,做一些实验应该表明给定的R是好还是坏.假设你的值是[1,10,3,18].该产品(使用32位整数计算)是

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311

因此哈希就是

3376724311/2 = 1688362155.

Answer 2

总结元素已经是你可以做的最简单的事情之一.但我不认为这是一个特别好的哈希函数和伪随机性.

如果在存储数组或计算哈希值之前对数组进行排序,那么每个好的哈希函数都可以.

如果是关于速度:你有没有测量瓶颈在哪里？如果你的哈希函数给你带来了很多冲突,并且你必须花费大部分时间来逐位比较数组,那么哈希函数显然不擅长它应该做的事情.排序+更好的哈希可能是解决方案.