Создание уникальных целочисленных / плавающих хешей из миллиона коротких строк

Question

Большинство приложений, особенно базы данных, могут сортировать и фильтровать по маленьким целым числам или плавать намного быстрее, чем они могут выполнять сравнения строк.

Поэтому мне интересно, есть ли хеш-функция, которую я могу использовать, чтобы вернуть 32-битное или 64-битное число короткой строки (около 5-40 символов), чтобы я мог сравнивать по целому, а не по строке.

Сначала я подумал о crc32, но кажется, что это слишком малое число, и приведет к возможным коллизиям с менее чем 50 000 хешей (мне нужно сделать более миллиона).

Меня больше всего интересует работа с Python, PHP, V8 Javascript, PostgreSQL и MySQL.

Answer 1

Проблема, связанная с вероятностью коллизий при 50 тыс. Записей, присуща всем 32-битным хэшам.Если вы немного прочитаете о проблеме дня рождения , вы увидите, что коллизии становятся вероятными, если у вас есть около sqrt(HashSpace) элементов, например, sqrt(2^32) = 64k для 32-битных хэшей.

---

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

Используя приближение из Википедии:

Мы получаем вероятность3 * 10 ^-8 для 1 миллиона элементов и 3 * 10-6 для 10 миллионов элементов.

Для этого можно использовать CRC64.Или просто укоротите крипто-хеш, такой как md5 или sha1, до желаемой длины.

---

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

---

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