Сколько строковых символов я должен прочитать, чтобы получить хороший хеш?
Вот небольшая загадка для вас: если вы используете алгоритм хеширования, такой как CRC-64, то сколько байтов в строке необходимо будет прочитать, чтобы вычислить хороший хеш? Допустим, все ваши строки имеют длину не менее 2 КБ, тогда кажется, что вы тратите впустую или ресурсы, используя всю строку для вычисления кэша, но сколько символов, по вашему мнению, достаточно? Достаточно ли будет всего 8 ASCII-символов, поскольку он равен 64-битным? Не будете ли использовать более 8 символов ASCII просто бессмысленно? Я хочу знать ваше мнение об этом.
Обновление: Под "хорошим хешем" я подразумеваю момент, когда вероятность коллизий хешей не может быть меньше при использовании еще большего количества байтов для его вычисления.
2 ответа
Если вы используете CRC-64 более 8 байтов или меньше, тогда нет смысла использовать CRC-64: просто используйте 8 байтов "как есть". CRC не имеет никакой добавленной стоимости, если входное значение не превышает предполагаемый выходной.
Как правило, если ваша хеш-функция имеет вывод n битов, то коллизии начинают появляться, когда вы накопили около 2n/ 2 строк. Короче говоря, если вы используете 64 бита, то очень маловероятно, что вы столкнетесь с коллизией в первых 2 миллиардах строк. Если вы получите 160-битный или более вывод, тогда коллизии практически невозможны (коллизий будет гораздо меньше, чем сбоев оборудования, таких как загорание процессора). Это предполагает, что хеш-функция является "идеальной". Если ваша хеш-функция начинается с выбора нескольких байтов данных, то необязательно, что выбранные вами байты не могут иметь никакого влияния на вывод хеша, поэтому вам лучше использовать "хорошие" байты - которые полностью зависят от вид строк, которые вы хэшируете. Здесь нет общего правила.
Мой совет - сначала попытаться использовать универсальную хеш-функцию для всей строки; Я обычно рекомендую MD4. MD4 - это криптографическая хеш-функция, которая была полностью нарушена, но для проблемы без обеспечения безопасности она все еще очень хороша при смешивании элементов данных (криптографически, CRC гораздо более сломан, чем MD4). Сообщалось, что MD4 на некоторых платформах на самом деле быстрее CRC-32, так что вы можете попробовать его. На базовом ПК (мой 2,4 ГГц Core2) реализация MD4 работает со скоростью около 700 МБ / с, поэтому мы говорим о 35000 хэшированных строках по 2 КБ в секунду, что неплохо.
Каковы шансы, что первые 8 букв двух разных строк одинаковы? В зависимости от того, что это за строки, они могут быть очень высокими, и в этом случае вы обязательно получите хеш-коллизии.
Хэш все это. Несколько килобайт это ничто. Если у вас нет необходимости сохранять наносекунды в вашей программе, отсутствие хеширования полных строк будет преждевременной оптимизацией.