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

Question

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

如何生成唯一的 id/signature(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 的程度而增长。

分配给组件的IDS可以调整，它们不必是整数序列，只要有一个合适的数字范围即可。唯一的要求是，一旦为数组(组件 id 的集合)生成了 id，它们就不应该发生冲突。如果该数组中的集合发生变化，则可以在运行时生成。

Answer 1

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

• 您使用了良好的哈希函数，并且
• 您的数据集并没有大得离谱。

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

对于哈希函数，您有多种选择，但请选择能够最大限度降低冲突概率的哈希，例如加密哈希(SHA-256、MD5)，或者如果您需要前沿性能，请使用 MurmurHash3 或其他流行的哈希。 MurmurHash3 可以生成一个整数作为输出，而加密哈希需要额外的步骤，从二进制输出中提取 4 或 8 个字节并解包为整数。 (使用任何一致的字节选择，例如第一个或最后一个。)

伪代码:

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
}