我曾经在一个特定的范围内（通常为0〜1000）得到的数字。 一种算法从该范围（约3至10个号码）中选择一些数字。 这样的选择是经常做的，我需要的，如果选择的数字的排列已经被选定检查。
例如，一个步骤选择[1, 10, 3, 18]和另外一个[10, 18, 3, 1]则第二选择可以被丢弃，因为它是一个置换。
我需要非常快的做此项检查。 现在我把所有阵列在一个HashMap，并使用自定义的散列函数：刚总结了所有的元素，所以1 + 10 + 3 + 18 = 32，和也是10 + 18 + 3 + 1 = 32。 对于等于我用一个bitset来快速检查是否元素在两组（我不需要使用位集排序时，但当号码的范围是已知的并没有太大的它仅适用）。
该工程确定，但可以产生大量的碰撞，所以equals（）方法被调用经常。 我在想，如果有检查排列更快的方法？
是否有任何排列好的哈希函数？
UPDATE
我已经做了一些基准：产生在0到6的范围内数目的所有组合和阵列长度为1至9，有可能3003个置换，和良好的散列应该产生接近该许多不同的散列（I使用32张的数为乱码）：
- 对于只是添加41个不同的散列（所以有很多冲突的）
- 8个不同的散列为异或运算值加在一起
- 286个不同的散列的相乘
- 为（R + 2e）的和为abc乘以3003个不同的散列曾建议（使用1779033703为R）
因此，农行的哈希值，可以计算速度非常快，是比所有其他好多了。 谢谢！
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
因此，散列要
2分之3376724311= 1688362155。
Answer 2:
总结的元素已经是你可以做最简单的事情之一。 但我不认为这是一个特别好的哈希函数WRT伪随机性。
如果你将它们存储或计算哈希值之前，你的数组进行排序 ，每一个好的哈希函数就可以了。
如果它是关于速度：你的情况下测量的瓶颈是什么？ 如果您的哈希函数是给你一个很大的冲突，你必须花费大量的时间逐位比较阵列中的散列函数显然是不擅长什么它应该做的事。 排序+好的Hash可能是解决方案。
Answer 3:
如果我正确理解你的问题，你想套之间是否相等，其中项目不排序。 这正是一个布隆过滤器会为你做。 在少数误报的代价（在这种情况下，你需要做的蛮力组比较的调用），你就可以通过检查其布隆过滤器散列是否等于组这样的比较。
代数之所以这样认为是OR操作是可交换的。 这对于其他半环，太。
Answer 4:
取决于如果您有很多碰撞（所以相同的哈希值，但不置换），你可能会同时散列他们的预先分类排列。 在这种情况下，你可以做一个更积极的一种散列的地方，你不仅加起来的数字，但添加一些bitmagick也将可以得到完全不同的哈希值。
如果你不想要的碰撞的负荷，因为你现在正在做的哈希太可怜了这仅仅是有益的。 如果你很难得到任何冲突，您使用的方法似乎罚款
Answer 5:
如果置换的长度是相同1.检查（如果没有 - 他们是不相等的）：我建议这个
- 排序仅1阵列。 相反排序另一个阵列通过第一数组中的元素迭代并搜索他们每个人的第二阵列中的存在的（比较仅在第二阵列中的元件是小 - 不通过整个阵列迭代）。
注意：如果你可以在你的permutaions相同数字（如[1,2,2,10]），那么你需要时，它从第一个成员匹配，从第2个数组删除元素。
伪代码：
if length(arr1) <> length(arr2) return false;
sort(arr2);
for i=1 to length(arr1) {
elem=arr1[i];
j=1;
while (j<=length(arr2) and elem<arr2[j]) j=j+1;
if elem <> arr2[j] return false;
}
return true;
这个想法是，与其排序另一个阵列我们就可以尝试匹配排序阵列中的所有元素。
Answer 6:
您可以通过使用该产品以及条款的总和大概减少碰撞了很多。
1 * 10 * 3 * 18 = 540和10 * 18 * 3 * 1 = 540
所以和积散列将是[32540]
你仍然需要做一些冲突时，他们虽然发生
Answer 7:
我喜欢用字符串的默认哈希代码（Java，C＃不知道其他语言），它会产生相当独特的散列码。 所以，如果你第一次数组排序，然后生成使用一些分隔符的唯一字符串。
所以你可以做以下的（JAVA）：
int[] arr = selectRandomNumbers();
Arrays.sort(arr);
int hash = (arr[0] + "," + arr[1] + "," + arr[2] + "," + arr[3]).hashCode();
如果性能是一个问题，您可以更改建议的低效的字符串连接使用StringBuilder或的String.format
String.format("{0},{1},{2},{3}", arr[0],arr[1],arr[2],arr[3]);
当然字符串哈希码并不能保证两个不同的串具有不同的哈希值，但考虑到该建议的格式，碰撞应该是极为罕见
文章来源: Good hash function for permutations?
