为给定列表/集合/唯一数字数组生成唯一ID

Question

我的数组包含从0到integer.max值的随机唯一数字。

我如何生成唯一的ID /签名（int）来唯一标识每个数组，而不是搜索每个数组并检查每个数字。

例如

int[] x = {2,4,8,1,88,12....};
int[] y = {123,456,64,87,1,12...};
int[] z = {2,4,8,1...};
int[] xx = {213,3534,778,1,2,234....};
..................
..................
and so on.

每个数组的长度可以不同，但​​是数字在数组内不重复，可以在其他数组中重复。每个数组的唯一ID的目的是通过ID进行标识，以便快速进行搜索。数组包含组件的ID，数组的唯一签名/ ID将标识其中包含的组件。

此外，无论数组中值的顺序如何，生成的id都应相同。像{1,5}和{5,1}应该生成相同的ID。

我查找了不同的数字解析方法，但是结果数随着数组的长度增加到无法容纳int的程度而增长。

Answer 1

严格来说，您所要求的是不可能的：即使只有两个元素的数组，比可能的签名（2 ³²）可能的数组（忽略顺序后约2 ⁶¹）要多得多。而且您的数组不限于两个元素，因此您的情况呈指数级恶化。

但是，如果您可以接受低比率的重复和错误匹配，则一种简单的方法是使用+运算符将所有元素加在一起（本质上计算出模2和[32]的和）。这是java.util.Set 的hashCode（）方法采用的方法。并不能完全消除比较整个数组的需要（因为您需要检测错误的匹配项），但是它将从根本上减少此类比较的次数（因为很少有数组可以匹配任何给定的数组）。

Answer 2

这可以通过带有阶数归一化函数的哈希函数h()（例如sort()）来近似解决。哈希函数是有损的，因为唯一哈希（2 ^ 32或2 ^ 64）的数量小于整数的可能可变长度集的数量，从而导致两个具有相同ID的不同集合的可能性很小（哈希冲突） ）。通常，如果

Answer 3

您希望{1，5}和{5，1}具有相同的ID。这就排除了标准的哈希函数，在这种情况下将给出不同的结果。一种选择是在散列之前对数组进行排序。请注意，加密哈希很慢；您可能会发现像FNV这样的非加密哈希就足够了。它肯定会更快。