Аутентификация посредством хэширования

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

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

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

Альтернатива перемещению лишних записей из переполненного сегмента в соседние — это помещение их в область переполнения, специально зарезервированную для этой цели. Самый простой способ организации области переполнения заключается в простом сборе всех записей из всех сегментов. В этом случае поиск записи, не поместившейся в сегмент, будет выполняться во всей области переполнения. Однако традиционный подход состоит в связывании записей, не поместившихся в определенный сегмент, чтобы в области переполнения хранился набор связных списков. В этом случае файл, хранящийся в пяти сегментах, может иметь вид, показанный на рис. 8.12 (заполненная записями область хранения закрашена). Обратите внимание, что элементы из сегментов 1 и 4 были перемещены в область переполнения, и, если добавить еще один элемент в сегмент 2, его тоже придется переместить.

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