Создание уникальных целых чисел/float из миллиона коротких строк

Question

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

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

Впервые я подумал о crc32, но он кажется слишком маленьким и would result in possible collisions in less than 50,000 hashes (мне нужно сделать более миллиона).

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

Answer 1

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

---

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

Используя аппроксимацию из Википедии:

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

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

---

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

---

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