为给定的唯一编号列表/集合/数组生成唯一id

Question

我的数组包含从0到整数的随机唯一数。最大值。

如何生成唯一的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。

我查找了不同的数字配对方法，但结果数字随着数组长度的增加而增加，达到了整数无法容纳的程度。

分配给组件的IDS可以调整，只要有一个良好的数字范围，它们不必是整数序列。唯一的要求是，一旦为数组（组件id的集合）生成id，它们就不应该冲突。如果数组中的集合更改，则可以在运行时生成。

Answer 1

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

为了避免排序，只需按照@ruakh的建议，将mod 2^32或mod 2^64的所有数字相加，并接受一定比例的冲突。添加数组长度将避免一些冲突：{5，1}将不匹配{1，2，3}，在这种情况下为（2（5 1））！=(3 (1 2 3)). 您可能希望使用真实数据进行测试，看看这是否提供了足够的优势。

Answer 2

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

但是，如果您可以接受低重复率和错误匹配，一种简单的方法是使用运算符将所有元素相加（这实际上是计算模2的和³²）。这是java采用的方法。util。设置

Answer 3

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

• 你使用一个很好的散列函数，并且
• 你的数据集不是大得离谱。

顺序规范化函数将确保集合{x， y}和{y， x}被哈希为相同的值。

对于哈希函数，您有许多选项，但是选择一个最小化冲突概率的哈希，例如密码哈希（SHA-256，MD5），或者如果您需要前沿性能，请使用MurmurHash3或其他当前的哈希。MurmurHash3可以产生一个整数作为输出，而加密散列需要额外的步骤，从二进制输出中提取4或8个字节，并将其解压缩为整数。（使用任何一致的字节选择，如first或last。）

在伪代码中：

int getId(setOfInts) {
    intList = convert setOfInts to integer list
    sortedIntList = sort(intList)
    ilBytes = cast sortedIntList to byte array
    hashdigest = hash(ilBytes)
    leadingBytes = extract 4 or 8 leading bytes of hashdigest
    idInt = cast leadingBytes to integer
    return idInt
}