0

给定一个数字列表，例如一些唯一的整数或长 ID，计算可重现的“签名”（最好不考虑元素顺序）的最佳方法是什么？

用例是检测是否从（对象）列表中添加或删除了任何 ID。

Javaarray.hashCode()不符合要求，因为即使它在 JVM 调用之间显然是一致的，如果元素的顺序发生变化或创建具有相同元素的另一个实例，它也会返回不同的哈希：

int[] ids1 = {1, 2, 3};
System.out.println(ids1.hashCode());
// output: 980546781

int[] ids1Copy = {1, 2, 3};
System.out.println(ids1Copy.hashCode());
// output: 2061475679

int[] ids2 = {2, 1, 3};
System.out.println(ids2.hashCode());
// output: 140435067

我的理解是ids1.hashCode()计算数组内存地址的哈希值，而不是数组中原始元素的累积哈希码。

除了单独散列每个元素之外，在这种情况下还可以使用哪些其他方法？

4

5 回答 5

2

您可以首先创建一个数字哈希图与其在数组中的计数。然后你可以只使用哈希图的哈希码。

但是，请记住，正如@khelwood 所建议的那样，2 个不同的哈希图可能（尽管很少见）返回相同的哈希码。

因此，如果您想可靠地检查 2 个数字列表是否相同，您可以如上所述创建它们的频率哈希图，然后进行以下检查：

  • hashmap2.size() == hashmap1.size()
  • 对于 hashmap2 中的每个 (key, value) { hashmap1[key] == value }

它的算法时间复杂度与计算和比较哈希码一样有效。

编辑：

我刚刚意识到上述算法是 Java HashMap 内部使用的算法equals()。

所以我们可以创建频率哈希图并使用hashmap2.equals(hashmap1).

编辑2：

如果数组中的所有数字都是不同的，那么您可以从它们创建一个哈希集，然后检查 if set2.equals(set1)。

于 2020-08-10T19:01:08.213 回答
1

约束

可重现的“签名”（最好不考虑元素顺序）

使这个问题具有挑战性。

以下是我想到的两种方法：

方法1：

一个。及时对整数列表进行排序O(N lg N)。

湾。将您的整数列表视为基M整数中的数字，其中M是列表中的最大数字。假设您有一个整数列表，例如[A, B, C]. 然后，您可以将该列表散列为：hash = A*M^0 + B*M^1 + C*M^2。M如果值很小，这种方法是合理的。您也可以选择一个小M的作为 2 的幂（例如 2^8），然后对于任何大于此的整数，将整数分成 8 位的块并使用相同的算法。

总时间：O(N lg N) + O(N). 空格：O(1)long int 累加器。

方法2：

一个。及时对整数列表进行排序O(N lg N)。

湾。构建整数列表的字符串表示形式，然后对字符串进行哈希处理。例如，对于像 的整数列表[1, 2, 3]，创建一个字符串1_2_3并对其进行哈希处理。

总时间：O(N lg N) + O(N). 空格：O(N lg N)大小字符串。

于 2020-08-10T20:23:44.610 回答
0

请注意，所有基于哈希的解决方案都不可靠。也就是说，有可能发生碰撞。

假设没问题，这里有一个简单的方法。

首先，为整数对构建哈希函数。有很多可用的。

接下来，让我们做一个思维练习。

想象一下将所有整数排列到 2^64 个桶中。然后看看数。所以一个数组就像[2, 0, 2]一个频率计数列表一样，..., 0, 0 0, 1, 0, 2, 0, 0, 0, ....

现在将这些频率计数与他们的下一个邻居配对。所以我们得到..., (0, 0), (1, 0), (2, 0), (0, 0), .... 现在用它的哈希替换每一对。重复。在 64 个级别之后，我们将得到一个表示整个频率计数的哈希值。

现在我们实际上不能执行这个操作。然而，在每个级别上，大多数条目都以0、then hash(0, 0)、thenhash(hash(0,0), hash(0,0))等开头。都是一样的。因此，如果数据结构是一个带有值和两个指针的链表，则大多数指针将仅指向通用的 0 填充块数据结构。

所以我们可以写出一个“树”，其中所有 0 块的指针都指向相同的规范值。当我们拥有这棵树时，插入一个元素就是将路径向下导航到适当的根，创建一个具有正确值的新节点，然后返回树上插入新值。这需要O(64)时间来做。插入所有值，我们得到值的精确频率计数的表示，用哈希签名，在 time 中O(64 n)。（创建相同数量的数据，然后能够丢弃大部分数据。）

但它会变得更好。如果您创建了两个具有此数据结构的列表，您不仅可以判断它们是否可能不同，而且您实际上可以找到差异！（rsync 实用程序使用类似的技巧来确定远程文件之间的变化，以便它可以限制复制的数量。）

于 2020-08-10T19:40:37.420 回答
0

根据评论和反馈，已经确定了以下方法（由于btilly概述的潜在哈希冲突，可能不可靠）：

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NumberHash {

    public static void main(String[] args) {

        // ######## Arrays.deepHashCode() ########

        Integer[] ids1Sorted = {1, 2, 3};
        Integer[] ids1Unsorted = {3, 1, 2};
        
        System.out.println(Arrays.deepHashCode(ids1Sorted));
        // 30817

        Arrays.sort(ids1Unsorted);
        System.out.println(Arrays.deepHashCode(ids1Unsorted));
        // 30817


        // ######## toString() based ########

        int[] idsSorted = {1, 2, 3};
        System.out.println(Arrays.toString(idsSorted).hashCode());
        // -412129978

        int[] idsUnsorted = {3, 2, 1};
        Arrays.sort(idsUnsorted);
        System.out.println(Arrays.toString(idsUnsorted).hashCode());
        // -412129978

        List<Integer> oids = Arrays.asList(2, 3, 1);
        Collections.sort(oids);
        System.out.println(oids.toString().hashCode());
        // -412129978
    }
}
于 2020-08-11T16:02:03.113 回答
0

我将使用CRC32或Adler32之类的校验和作为 包装在准备使用的 lambda 中的唯一标识符：

int[] yourArray = {1, 2, 3};
long checksum = Arrays.stream(yourArray).boxed().collect(Collector.of(
    CRC32::new, CRC32::update, (l, r) -> {return l;})).getValue();

{1, 2, 3}: 0x55bc801d
{1, 3, 2}: 0x3ba081ca
{2, 1, 3}: 0x7cd76d87

于 2021-03-03T13:44:40.150 回答