Хорошая хеш-функция? (32-битный слишком маленький, 64-битный слишком большой)

Question

Мне нужно сгенерировать хеш-значение, используемое для уникальности многих миллиардов записей в Java.Проблема в том, что у меня есть только 16 цифр для игры.Исследуя это, я нашел алгоритмы для 32-битного хэша, которые возвращают целые числа Java.Но это слишком мало, так как он имеет диапазон + / 2 миллиарда и будет иметь больше записей, чем это.Я не могу перейти к 64-битному хешу, так как он вернет мне слишком большие числовые значения (+ / 4 квинтиллиона или 19 цифр).Проблема в том, что я имею дело с устаревшей системой, которая заставляет меня использовать статический ключ длиной 16 цифр.

Предложения?Я знаю, что никакая хеш-функция не гарантирует уникальность, но мне нужна хорошая, которая бы соответствовала этим ограничениям.

Спасибо

Answer 1

Если вы ограничены 16 десятичными цифрами, ваше пространство ключей содержит 10 ^ 16 значений.Даже если вы найдете хеш, который обеспечивает равномерное распределение в вашем наборе данных, из-за Birthday Paradox у вас будет 50% вероятность столкновения с ~ 10 ^ 8 элементами данных, что на порядок меньшечем ваши миллиарды записей.

Это означает, что вы не можете использовать любой вид хэша в одиночку и полагаться на уникальность.

Простое решение - использовать вместо этого глобальный счетчик.Если глобальный счетчик недопустим, можно использовать счетчики с предварительно выделенными диапазонами.Например, 6 старших значащих цифр обозначают фиксированный индекс источника данных, а 10 младших значащих цифр содержат монотонный счетчик, поддерживаемый этим источником данных.

Answer 2

Если ваш сгенерированный хеш слишком велик, вы можете просто изменить его, используя максимум пространства ключей.

myhash = hash64bitvalue % 10^16

Answer 3

То есть ваше ограничение 53 бита?

Насколько я понимаю, порядковый номер бита в хеш-коде не влияет на его значение (порядок и значение бита полностью независимы друг от друга). Таким образом, вы можете получить 64-битную хеш-функцию и использовать только последние 53 бита. И вы должны использовать двоичные операции для этого (hash64 & (1 << 54 - 1)), а не арифметика. </p>

Answer 4

Вам не нужно хранить свои хеши в удобочитаемой форме (как вы сказали, в шестнадцатеричном формате).Просто сохраните 64-битный тип данных (сгенерированный 64-битной хэш-функцией) в вашей базе данных, который составляет всего 8 байтов.И не те 19 байтов, из которых вы были напуганы.

Если это не решение, улучшите устаревшую систему.

---

Редактировать: Подождите!

64-бит: 2 ⁶⁴ =

18446744073709551616

16 шестнадцатеричных цифр: 16 ¹⁶ =

18446744073709551616

Точная посадка!Так что сделайте шестнадцатеричное представление вашего 64-битного хеша, и вот вы здесь.

Answer 5

Если вы можете сохранить 16 буквенно-цифровых символов, вы можете использовать шестнадцатеричное представление и упаковать 16 ^ 16 бит в 16 символов.16 ^ 16 - это 2 ^ 64.