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

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

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

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

В основном меня интересует работа с Python, PHP, V8 Javascript, PostgreSQL и MySQL.


php hash numbers rdbms hash-collision
person Xeoncross    schedule 16.03.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

person CodesInChaos    schedule 16.03.2012
comment
Вероятность столкновения с 10 миллионами элементов составляет 0,000003%? Похоже, стоит попытаться увидеть, есть ли у меня какие-либо коллизии. Я нашел эту непроверенную функцию PHP crc64 что может сработать. Я бы использовал счетчик для увеличения числа вручную, но единственный ввод, который у меня есть, - это слово, которое мне нужно каждый раз преобразовывать в одно и то же число. Думаю, я мог бы найти слово=число и затем использовать число. - person Xeoncross; 17.03.2012