排列的好哈希函数是什么？

Question

我有一些特定范围内的数字（通常在0到1000左右）。算法从这个范围中选择一些数字（大约3到10个数字）。这种选择经常发生，我需要检查已选择的数字的排列是否已经被选择过。

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

我需要非常快地进行此检查。现在，我将所有数组放入哈希映射表中，并使用自定义哈希函数：只需将所有元素相加，例如1+10+3+18=32，以及10+18+3+1=32。对于相等性，我使用位集来快速检查元素是否在两个集合中（使用位集时不需要排序，但仅适用于已知且不太大的数字范围）。

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

有没有好的针对排列的哈希函数？

更新

我进行了一个小型基准测试：生成范围为0到6的数字的所有组合，数组长度为1到9。有3003个可能的排列，一个好的哈希应该生成接近这么多不同的哈希（我使用32位数字进行哈希）：

• 仅添加得到41个不同的哈希（因此会产生很多冲突）
• XOR值在一起得到8个不同的哈希
• 乘法得到286个不同的哈希
• R + 2e以及乘法得到了abc建议的3003个不同的哈希（使用1779033703作为R）

因此，abc的哈希可以非常快速地计算，并且比其他哈希好得多。谢谢！

附注：当我不需要排序时，我不想对值进行排序，因为这会变得太慢。

- martinus

---

我不确定您将值相加以创建哈希的方法是否按照您的意图工作。确实，1+10+3+18 = 10+18+3+1 = 32，但是1+12+3+16也是这样。 - Paul Arnold

@Paul，这就是为什么他会在值相等时执行排序和比较的原因。 - pierrotlefou

@Paul，你不应该删除你的帖子；虽然XOR有很多冲突，但是仅仅添加一个数字也会有冲突；而且这两个哈希可以轻松地组合在一起得到更好的哈希。 - martinus

你考虑过使用以下一种或多种通用哈希函数吗：http://www.partow.net/programming/hashfunctions/index.html。 - Matthieu N.

小小的评论。标题有点误导人。我来这里是期望找到一个哈希函数，它可以为相同数字的不同排序提供不同的哈希值。 - Shiv

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。

- abc

---

不错。我一直在寻找一个数学标准来选择一个好的R，但是没有找到任何有用的东西。但我想只要任意值足够好，就没有必要做太多理论。 - abc

我认为黄金比例可能是一个不错的选择（32位值为2654435769），但这只是一个猜测。http://brpreiss.com/books/opus4/html/page214.html - martinus

对我来说，那看起来是个合理的选择。我也发现了这个哈希函数的一个小弱点。输入的最高位只会影响输出的最高位。因此，如果这个函数被用于哈希数据，其中最低有效位是恒定的，那么我们会预期有很多哈希冲突。 - abc

除以二的目的是什么？也就是说，为什么要移除一个恒定的位？只是为了减小哈希的大小吗？ - keyneom

Answer 2

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

如果在存储或计算哈希之前排序数组，每个良好的哈希函数都能胜任。

如果考虑速度：你是否记录了瓶颈出现的位置？如果哈希函数给出大量冲突并且你必须花费大部分时间逐位比较数组，则该哈希函数显然不能胜任其任务。排序 + 更好的哈希可能是解决方案。

- sellibitze

Answer 3

如果我正确理解了您的问题，您想要测试元素无序的集合之间的相等性。这正是布隆过滤器能够为您做到的。虽然会有一小部分误判（在这种情况下，您将需要进行暴力比较以确定是否相等），但通过检查它们的布隆过滤器哈希值是否相等，您将能够比较这些集合。

这个结果成立的代数原因是OR运算是可交换的。这也适用于其他半环。

- Alex Smola

Answer 4

我喜欢使用字符串的默认哈希码（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]);

字符串哈希码并不保证两个不同的字符串具有不同的哈希值，但考虑到这种建议的格式，碰撞应该极为罕见

- LiorH

---

谢谢你的投票。我试图提出另一种解决方案（这就是这个网站的目的），亲爱的投票者，如果您能详细说明我的建议有什么问题，这将使这篇文章更具生产力。 - LiorH

可能那些投票反对你的人考虑到了这个：https://dev59.com/DXM_5IYBdhLWcg3wPAjT#1465719 - Michael Foukarakis

我怀疑可能是我误点了一下。实际上，我认为你的解决方案相当不错。我是新来的，等我弄清楚之后，SO就不让我撤销了（我试过了）。如果你稍微编辑一下你的帖子，看起来我就可以修复它。抱歉。 - Paul Arnold

一旦数组排序完成，就不需要构建字符串并计算哈希值。这样做会非常慢，有很多好的哈希函数可以与排序后的数组一起使用。 - martinus

Answer 5

我建议这样做： 1. 检查排列的长度是否相同（如果不同，则它们不相等）。

2. 只对一个数组进行排序。而不是对另一个数组进行排序，遍历第一个数组的元素，并在第二个数组中搜索每个元素的存在（仅在第二个数组中的元素较小时进行比较-不要遍历整个数组）。

注意：如果您的排列中可能有相同的数字（例如[1,2,2,10]），则当第二个数组匹配第一个数组的成员时，您需要从第二个数组中删除元素。

伪代码：

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;

这个想法是，我们可以尝试在已排序的数组中匹配另一个数组的所有元素，而不是对另一个数组进行排序。

- DmitryK

Answer 6

如果你有很多碰撞（相同的哈希但不是排列），你可以在哈希它们时预先对数组进行排序。在这种情况下，您可以使用更激进的哈希方式，不仅将数字相加，还要添加一些位运算来获得非常不同的哈希。

只有在您现在执行的哈希太差时，才会对此有所益处，因为您会遇到很多不必要的碰撞。如果您几乎没有任何碰撞，则使用的方法似乎很好。

- Toad

Answer 7

通过使用项的乘积和总和，您可以大大减少碰撞。

1*10*3*18=540 和 10*18*3*1=540

因此，总和-乘积哈希将是[32,540]

但是当它们发生时，您仍然需要处理碰撞。

- John La Rooy