时间戳

首页 > 解决方案 > 为给定的唯一数字列表/集合/数组生成唯一 ID

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

问题描述

我有包含从 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，它们就不应发生冲突。如果该数组中的集合发生更改，则可以在运行时生成。

标签： javaencryptioncryptographywolfram-mathematica

解决方案

这可以通过h()具有顺序归一化函数（例如sort()）的散列函数来近似解决。散列函数是有损的，因为唯一散列（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
}

推荐阅读