3

我有成对的哈希值，比如

  1. 128ecf542a35ac5270a87dc740918404;d603ac0c04b9d08974482ae7fd4cf55
  2. a1288b1c7e2257a90bad9bdfb7690fbb;f23828e312d90cb7fdadd6479236119c
  3. ……………………………………………………………………………………………………………………………………………………………………………… …………………………………………………………………………

我想让每一对都与其他对进行比较，这意味着：

128ecf542a35ac5270a87dc740918404;d603ac0c04b9d08974482ae7fd4cf55d

保持原样；

如果是

d603ac0c04b9d08974482ae7fd4cf55d;128ecf542a35ac5270a87dc74091840

4、应该变成

128ecf542a35ac5270a87dc740918404;d603ac0c04b9d08974482ae7fd4cf55d

我的主要目标是拥有一个特定的函数，它比较一对的两个哈希值并返回一对，其中的值根据某些规则在其中排序。规则本身无关紧要，唯一的要求是，它应该非常快，并且应该始终给出相同的结果，因为输入是 (unique1,unique2) 或 (unique2,unique1)

谢谢！

一种明显但低效的方法是仅对每个哈希值中包含的数字求和并进行比较，然后将总和较小的哈希值作为对中的第一个元素，将较大的哈希值放在第二个位置。

4

3 回答 3

5

只需将两个字符串与通常的字符串比较 ( compareTo) 进行比较，然后将较小的字符串放在第一位。这将保证你想要什么。我希望这非常便宜，因为实际上哈希值在前几个字符中已经不同，然后比较不需要查看其余的字符串。此外，访问和比较非常少的字节数（如您的示例）无论如何都非常便宜，以至于只有与程序执行的其他操作相比，您经常这样做才能看到性能影响。

如果您没有将值作为字符串，而是作为字节数组或类似的东西，只需自己实现一个简单的字典比较。

于 2012-06-14T12:20:36.633 回答
1

编辑：我刚刚再次阅读了您的问题和主要目标。我的答案是比较两对。

如果您想对一对中的两个散列值进行排序，请线性比较两个散列值，并且在字符的第一个不匹配时将较低的值放在第一位。前几个字节的值已经不同的可能性很大。

我不认为你可以在 Java 中做到这一点，但你可以在 C/ASM 中为它创建一个函数，然后通过 JNI 从 Java 中使用它。

让我们看看：这些是成对的 32 字节哈希值。您知道这些对在“;”处分隔的位置 字节 32。

让你的耦合哈希值作为hahsA := (hA1;hA2)和hashB := (hB1;hB2)

你拿第一对：

1) 获取 0-15 和 33-49 字节到两个 SSE 寄存器并异或

hashA[0-15] := ( hashA1[0-15] XOR hashA2[0-15] ).

2) 获取 16-31 和 50-65 字节到 SSE 寄存器并对其进行异或

hashA[16-31] := ( hashA1[16-31] XOR hashA2[16-31] ).

现在您有两个 SSE 寄存器，其中填充了这对夫妇的第一个和第二个 16 字节的 XOR：

XMM0: hashA[0-15]
XMM1: hashA[16-31]

你拿第二对做同样的事情。您有 8 个 SSE 寄存器，因此您可能不需要在 2) 之后从寄存器中获取值。

现在你有：

XMM0: hA[0-15]
XMM1: hA[16-31]
XMM2: hB[0-15]
XMM3: hB[16-31]


if( XMM0 == XMM2 AND XMM1 == XMM3 ) then hA and hB are equal.

当然，如果你的哈希码大于 32 字节，你需要做进一步的步骤，但假设你的哈希码都是相同的长度，这个算法需要：

1) 加载两个 16 字节和 xor = 3 条指令 2) 3 条指令

1) 和 2) 再次用于第二对：6 条指令最后 2 条比较指令和 1 条 AND 指令

对于每对比较的夫妇来说，这总结为 15 条指令，而不是测量函数调用。我不能说它是 O(1)，因为如果哈希值更大，那么指令的数量也会增加。

如果效率真的很重要，这是一条路要走。但无论如何，我认为你不能少于 O(n)，因为你必须比较所有字符。

于 2012-06-14T13:21:18.913 回答
0

很容易优化两个字符串不相等的情况，并且 的实现String.equals(Object)已经这样做了。

但是，两个字符串相等但不相等的情况==本质上是O(N).

现在可以在某些情况下对此进行改进：

  • 您能够向对象添加额外的私有字段，
  • 对象的状态对于equals操作员来说必须是稳定的，并且
  • 同一组对象实例需要反复比较。

在这些前提条件下，有一种算法倾向于O(1)。但是，您不能将其应用于表示为 String 值的哈希值，因为第一个和（可能）第三个条件不成立。

于 2012-06-14T13:11:06.420 回答