performance - 用于排列的良好散列函数？

Question

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

例如一步选择 [1, 10, 3, 18]和另一个 [10, 18, 3, 1]那么第二个选择可以被丢弃，因为它是一个排列。

我需要非常快地做这个检查。现在我将所有数组放在一个哈希图中，并使用自定义哈希函数:只需将所有元素相加，即 1+10+3+18=32，也就是 10+18+3+1=32。对于 equals，我使用 bitset 来快速检查元素是否在两个集合中(使用 bitset 时我不需要排序，但它仅在数字范围已知且不太大时才有效)。

这工作正常，但会产生大量冲突，因此经常调用 equals() 方法。我想知道是否有更快的方法来检查排列？

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

更新

我做了一个小基准:生成 0 到 6 范围内的所有数字组合，以及 1 到 9 的数组长度。有 3003 种可能的排列，一个好的散列应该生成接近这么多不同的散列(我使用 32 位数字对于哈希):

只需添加 41 个不同的哈希值(因此有很多冲突)

用于异或值的 8 个不同的哈希值

286 种不同的哈希值相乘

(R + 2e) 有 3003 个不同的哈希值，并按照 abc 的建议进行乘法(对 R 使用 1779033703)

所以 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.