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

Question

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

function Hash(key) 
    return key mod PrimeNumber 
end 

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

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