15

我有一个特定范围内的数字（通常从 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 的 hash 可以计算得非常快，而且比其他的都好很多。谢谢！

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

4

7 回答 7

7

一个潜在的候选人可能是这个。修复一个奇数整数 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。

于 2009-10-08T11:22:51.153 回答
5

对元素求和已经是您可以做的最简单的事情之一。但我不认为这是一个特别好的散列函数 wrt 伪随机性。

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

如果是关于速度：您是否测量过瓶颈在哪里？如果您的哈希函数给您带来很多冲突，并且您必须花费大部分时间逐位比较数组，那么哈希函数显然不擅长它应该做的事情。Sorting + Better Hash 可能是解决方案。

于 2009-10-08T08:28:59.193 回答
3

如果我正确理解您的问题，您想测试未订购项目的集合之间的相等性。这正是布隆过滤器将为您做的事情。以少量误报为代价（在这种情况下，您需要调用蛮力集合比较），您将能够通过检查它们的布隆过滤器哈希是否相等来比较这些集合。

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

于 2011-03-31T05:48:05.977 回答
0

取决于您是否有很多冲突（因此相同的哈希但不是排列），您可能会在对数组进行哈希处理时对它们进行预排序。在这种情况下，您可以进行更激进的散列，您不仅可以将数字相加，还可以添加一些 bitmagick 以获得完全不同的散列。

这仅在您遇到大量不需要的冲突时才有用，因为您现在正在执行的哈希太差了。如果您几乎没有遇到任何碰撞，那么您使用的方法似乎很好

于 2009-10-08T08:31:58.837 回答
0

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

字符串哈希码当然不能保证两个不同的字符串具有不同的哈希，但是考虑到这种建议的格式，冲突应该是非常罕见的

于 2009-10-08T09:07:04.873 回答
0

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

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

注意：如果您的排列中有相同的数字（例如 [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;

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

于 2009-10-08T09:51:42.773 回答
0

您可能可以通过使用产品以及条款的总和来大大减少冲突。

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

所以 sum-product hash 将是 [32,540]

当它们发生时，你仍然需要对碰撞做一些事情

于 2009-10-08T10:58:11.427 回答