Что такое хорошая хеш-функция?

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

function Hash(key)
  return key mod PrimeNumber
end

(mod - это оператор% в C и подобных языках)

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

Для выполнения «нормального» поиска по хэш-таблице практически по любым данным - эта, написанная Полом Хси, - лучшее, что я когда-либо использовал.

http://www.azillionmonkeys.com/qed/hash.html

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

Для универсальных хешей не существует такой вещи, как «хорошая хеш-функция» (ред. Да, я знаю, что есть «универсальное хеширование», но я имел в виду не это). В зависимости от контекста качество хеша определяется разными критериями. Два человека уже упоминали SHA. Это криптографический хеш, и он совсем не подходит для хеш-таблиц, о которых вы, вероятно, имеете в виду.

К хеш-таблицам предъявляются самые разные требования Но все же найти хорошую хеш-функцию во всем мире сложно, потому что разные типы данных предоставляют разную информацию, которая может быть хеширована. Как правило, полезно рассматривать всю информацию, содержащуюся в типе, одинаково. Это не всегда легко или даже возможно. По причинам статистики (и, следовательно, коллизии) также важно создать хороший разброс по проблемному пространству, то есть по всем возможным объектам. Это означает, что при хэшировании чисел от 100 до 1050 не следует позволять старшей цифре играть большую роль в хеш-функции, потому что для ~ 90% объектов эта цифра будет равна 0. Гораздо важнее оставить последние три цифры. цифры определяют хеш.

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

На самом деле это один из тех случаев, когда я советую прочитать, что говорит Кнут в «Искусство программирования» , т. 3. Еще одно хорошее чтение - « Искусство хеширования» Жюльен Уокер .

Есть две основные цели хеш-функций:

• для равномерного распределения точек данных на n бит.
• для надежной идентификации входных данных.

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

Если вы просто создаете хеш-таблицу в программе, вам не нужно беспокоиться о том, насколько обратим или взломан алгоритм ... SHA-1 или AES для этого совершенно не нужны, вам лучше использовать изменение FNV . FNV обеспечивает лучшую дисперсию (и, следовательно, меньшее количество столкновений), чем простой основной мод, как вы упомянули, и он более адаптируется к различным размерам ввода.

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

Это пример хорошего, а также пример того, почему вы никогда не захотите его писать. Это хэш Fowler / Noll / Vo (FNV), который в равной степени является гением информатики и чистым вуду:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

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

• Лэндон Курт Нолл рекомендует на своем сайте алгоритм FVN-1A по сравнению с исходным алгоритмом FVN-1: улучшенный алгоритм лучше распределяет последний байт в хэше. Соответственно скорректировал алгоритм.

Я бы сказал, что главное практическое правило - не катить самостоятельно. Попробуйте использовать что-то, что было тщательно протестировано, например, SHA-1 или что-то в этом роде.

Хорошая хеш-функция имеет следующие свойства:

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

2. Для пары сообщений m 'и m вычислительно невозможно найти два таких, что h (m) = h (m')

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

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

Не используйте MD5 или SHA-1 в новых проектах. Большинство криптографов, включая меня, сочли бы их взломанными. Главный источник слабости обоих этих конструкций заключается в том, что второе свойство, которое я обозначил выше, не выполняется для этих конструкций. Если злоумышленник может сгенерировать два сообщения, m и m ', которые имеют одно и то же значение, они могут использовать эти сообщения против вас. SHA-1 и MD5 также страдают от атак на расширение сообщений, которые могут фатально ослабить ваше приложение, если вы не будете осторожны.

Более современный хэш, такой как Whirpool, - лучший выбор. Он не страдает от этих атак с расширением сообщений и использует ту же математику, что и AES, для доказательства защиты от различных атак.

Надеюсь, это поможет!

То, что вы здесь говорите, это то, что вы хотите иметь тот, который использует сопротивление столкновения. Попробуйте использовать SHA-2. Или попробуйте использовать (хороший) блочный шифр с функцией одностороннего сжатия (никогда не пробовал раньше), например AES в режиме Миягути-Принил. Проблема в том, что вам необходимо:

1) иметь капельницу. Попробуйте использовать первые 256 бит дробных частей константы Хинчина или что-то в этом роде. 2) иметь схему заполнения. Легко. Выбросьте его из хэша, такого как MD5 или SHA-3 (Keccak [произносится как "кет-чак"]). Если вас не волнует безопасность (некоторые другие сказали это), посмотрите FNV или lookup2 Боба Дженкинса (на самом деле я первый, кто рекомендует lookup2) Также попробуйте MurmurHash, это быстро (проверьте это: 0,16 cpb ).