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

StackOverflow https://stackoverflow.com/questions/34595

Вопрос

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

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 обеспечивает лучшую дисперсию (и, следовательно, меньшее количество коллизий), чем простой простой мод, как вы упомянули, и он более адаптируем к различным размерам входных данных.

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

Это хороший пример, а также пример того, почему вы никогда бы не захотели его написать.Это хэш Фаулера / Нолла / Во (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 или что-то в этом роде.

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

<Ол>

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

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

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

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

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

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

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

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

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top