2008-08-29 4 views
100

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

function Hash(key) 
    return key mod PrimeNumber 
end 

(мод является оператор% в С и других подобных языках)

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

+30

Считаете ли вы использование одной или нескольких следующих хэш-функций общего назначения: http://www.partow.net/programming/hashfunctions/index.html –

+0

В fnv_func тип p [i] является char, что произойдет с h после первой итерации? Было ли это сделано специально? –

+4

@martinatime сказал: * В википедии имеется множество информации о хэш-функциях http://en.wikipedia.org/wiki/Hash_function и в нижней части этой статьи http://www.partow.net/programming/hashfunctions/ index.html имеет алгоритмы, реализованные на разных языках. * – 2501

ответ

25

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

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

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

+0

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

+0

Я читал на сайте Дженкинса, что SFH является одним из лучших, но я думаю, что Мурмур мог бы сделать лучше, см. Этот отличный ответ: http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm- is-best-for-unique-and-speed/145633 # 145633 – nawfal

+2

Что означает YMMV? – cobarzan

2

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

+0

Он, похоже, ничего не требует криптографической защиты, поэтому SHA-1 будет излишним. – Erik

+0

, несмотря на то, что никаких столкновений для SHA-1 не найдено, считается, что это вопрос нескольких лет или месяцев, прежде чем он будет найден. Я бы рекомендовал использовать SHA-256. –

46

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

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

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

Это на самом деле один из тех случаев, когда я советую прочитать, что должен сказать Кнут в: Искусство компьютерного программирования, vol. 3. Еще одним хорошим показателем является Жюльен Уокер The Art of Hashing.

+1

Konrad, вы, безусловно, правы с теоретической точки зрения, но вы когда-нибудь пробовали использовать функцию хэша Paul Hsieh, о которой я упоминал в своем комментарии? Это действительно неплохо против множества разных данных! –

1

Функция хорошая хэш обладает следующими свойствами:

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

  2. Учитывая пару сообщений, т 'и т, то вычислительно невозможно найти два такими, что H (M) = H (M')

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

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

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

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

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

+0

Я думаю, что рекомендация криптографической хэш-функции - это действительно плохой совет в этом случае. – Slava

8

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

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

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

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

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

+0

обновленная ссылка на The Hash Function Lounge: http://www.larc.usp.br/~pbarreto/hflounge.html –

+0

Насколько хорошо FNV противостоят столкновениям с деньгами по сравнению, например, с таким же количеством бит с SHA1? –

+0

@ Kevin До тех пор, пока характеристики хэша лаваша хороши (крошечные изменения в вводе = большие изменения в выходе), тогда столкновения дня рождения - это просто функция бит в хэше. FNV-1a превосходна в этом отношении, и вы можете иметь столько же или немного бит в хэше, сколько хотите (хотя для получения небольшого счета не требуется 2). –

4

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

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; 
} 

Edit:

  • Лэндон Curt Noll рекомендует на his site-1A FVN алгоритм над исходным алгоритмом FVN-1: улучшенный алгоритм лучше диспергирует последний байт в хэше. Я соответствующим образом скорректировал алгоритм.
+3

Возможно, вам захочется посмотреть на этот сайт для получения информации о том, почему эти значения выбраны: http: //isthe.com/chongo/tech/comp/fnv/#fnv-prime – Cthutu

1

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

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

 Смежные вопросы

  • Нет связанных вопросов^_^