Как записать хеш-функцию в C?
Хэш-таблицы, как говорят, являются самым быстрым / лучшим способом Хранить/Получать данные.
Мое понимание хэш-таблицы, хеширование следующим образом (Исправьте меня, если я неправ или добавьте, Существует ли что-нибудь больше):
- Хэш-таблица является только массивом (единственный или многомерный) для хранения значений.
- Хеширование является процессом, чтобы найти, что индекс/местоположение в массиве вставляет/получает данные. Вы берете элемент (элементы) данных и передаете его как ключ (ключи) к хеш-функции, и Вы получили бы индекс/местоположение, где вставить/получить данные.
У меня есть вопрос:
Хеш-функция используется для хранившего/получения данных, ОТЛИЧАЮЩИХСЯ от криптографической хеш-функции, используемой в приложениях защиты для аутентификации как MD5, HMAC, SHA-1 и т.д....?
Каким образом (s) - они отличающийся?
- Как записать хеш-функцию в C?
- Разве существует ли некоторый стандарт или инструкции к нему?
- Как мы удостоверяемся, что вывод хеш-функции т.е., индекс не вне диапазона?
Было бы замечательно, если Вы могли бы упомянуть некоторые хорошие ссылки для понимания их лучше.
3 ответа
Криптографический хеш подчеркивает, что кому-либо трудно намеренно создать конфликт. В случае хеш-таблицы акцент обычно делается на быстром получении разумного разброса результатов . Таким образом, они обычно сильно различаются (в частности, криптографический хеш обычно на много медленнее).
Для типичной хеш-функции результат ограничен только типом - например, если он возвращает size_t, это нормально для него вернуть любой возможный size_t. Вам решать, чтобы уменьшить этот выходной диапазон до размера вашей таблицы (например, используя остаток от деления на размер вашей таблицы, который часто должен быть простым числом).
В качестве примера довольно типичная нормальная хеш-функция может выглядеть примерно так:
// warning: untested code.
size_t hash(char const *input) {
const int ret_size = 32;
size_t ret = 0x555555;
const int per_char = 7;
while (*input) {
ret ^= *input++;
ret = ((ret << per_char) | (ret >> (ret_size - per_char));
}
return ret;
}
Основная идея здесь состоит в том, чтобы каждый бит входной строки влиял на результат и (как можно быстрее) иметь каждый бит на результат влияет хотя бы часть входных данных. Обратите внимание, что я не особо рекомендую это как отличную хеш-функцию - просто пытаюсь проиллюстрировать некоторые основы того, что вы пытаетесь достичь.
Боб Дженкинс подробно описал свою хорошую, хотя и немного устаревшую, хэш-функцию . В статье есть ссылки на более новые и лучшие хэш-функции, но в описании рассматриваются проблемы создания хорошей хеш-функции.
Кроме того, большинство реализаций хеш-таблиц фактически используют массив связанных списков для разрешения коллизий. Если вы хотите просто использовать массив, хеш-функция должна проверить наличие коллизий и создать новый хеш-индекс.
Упомянутые вами криптографические хеш-функции могут использоваться как хеш-функции для хеш-таблицы, но они намного медленнее, чем хеш-функции, разработанные для хеш-таблицы. Скорость упрощает атаки методом грубой силы.
Цели проектирования разные.
С помощью криптографических хэш-функций вы хотите, например, чтобы хеш-функция и хеш-функция не могли использоваться для определения исходных данных или любых других данных, которые могли бы создать такой же хеш-код.
Хеш-функции, используемые с хеш-таблицами и другими структурами данных, не нуждаются в таких свойствах безопасности. Часто бывает достаточно, если хеш-функция работает быстро и равномерно распределяет входной набор по множеству возможных хешей (чтобы избежать ненужной кластеризации / коллизий).