Генерация уникального идентификатора для заданного списка / набора / массива уникальных номеров

Question

У меня есть массивы, содержащие случайные уникальные числа от 0 до значения integer.max.

Как я могу сгенерировать уникальный идентификатор / подпись (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.

Каждый массив может иметь разную длину, но числа не повторяются в массиве и могут повторяться в других массивах. Назначение уникального идентификатора для каждого массива - идентифицировать его по идентификатору, чтобы можно было быстро выполнить поиск. Массивы содержат идентификаторы компонентов, и уникальная сигнатура / идентификатор для массива будет идентифицировать содержащиеся в нем компоненты.

Кроме того, сгенерированный идентификатор может быть одинаковым независимо от порядка значений в массиве. Подобно тому, как {1,5} и {5,1} должны генерировать один и тот же идентификатор.

Я искал разные методы обработки чисел, но результирующее число увеличивается с увеличением длины массива до такой степени, что оно может не вписывается в int.

Answer 1

Это можно приблизительно решить с помощью функции ha sh h() с функцией нормализации порядка (например, sort()). Функция ha sh с потерями, поскольку число уникальных хэшей (2 ^ 32 или 2 ^ 64) меньше, чем число возможных наборов целых чисел переменной длины, что приводит к малой вероятности того, что два разных набора имеют одинаковый идентификатор (ха sh столкновение). Как правило, это не будет проблемой, если

• вы используете хорошую функцию ha sh, а
• ваш набор данных не слишком большой.

Функция нормализации порядка гарантирует, что наборы {x, y} и {y, x} будут хэшированы с одним и тем же значением.

Для функции ha sh у вас есть много вариантов, но вы выбираете ha sh, который сводит к минимуму вероятность столкновения, например, криптографию c га sh (SHA-256, MD5) или, если вам нужна новейшая производительность, используйте MurmurHash3 или другое ha sh du jour. MurmurHash3 может выдавать целое число в качестве вывода, в то время как криптографические хеши c требуют дополнительного шага извлечения 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
}

Answer 2

Вы хотите, чтобы {1, 5} и {5, 1} имели одинаковый идентификатор. Это исключает стандартные функции ha sh, которые в этой ситуации дают разные результаты. Одним из вариантов является сортировка массива перед хэшированием. Имейте в виду, что криптографические c хэши работают медленно; Вы можете обнаружить, что не крипто-ха sh, как FNV, достаточно. Это, безусловно, будет быстрее.

Чтобы избежать сортировки, просто добавьте все числа мод 2 ^ 32 или мод 2 ^ 64, как подсказывает @ruakh, и примите, что у вас будет доля коллизий. Добавление длины массива позволит избежать некоторых коллизий: {5, 1} не будет совпадать с {1, 2, 3} в этом случае как (2+ (5 + 1))! = (3+ (1 + 2 + 3) ). Возможно, вы захотите проверить свои реальные данные, чтобы убедиться, что это дает достаточно преимуществ.

Answer 3

Строго говоря, то, что вы просите, невозможно: даже для массивов, состоящих только из двух элементов, существует гораздо больше возможных массивов (примерно через 2 ⁶¹ после игнорирования порядка), чем возможных сигнатур (2 ³² ). И ваши массивы не ограничены двумя элементами, поэтому ваша ситуация экспоненциально хуже.

Однако, если вы можете принять низкий уровень дубликатов и ложных совпадений, простой подход состоит в том, чтобы просто сложить вместе все элементы с оператором + (который по существу вычисляет сумму по модулю 2 ³² ). Такой подход используется методом java .util.Set hashCode (). Это не полностью устраняет необходимость сравнивать целые массивы (потому что вам нужно будет обнаруживать ложные совпадения), но радикально сократит количество таких сравнений (потому что очень немногие массивы будут соответствовать любому данному массиву).