Где можно быстро найти определенную главу книги? Где находится заказ Марты Мустерманн? Где можно купить часы с коричневым кожаным браслетом? Эти три вопроса объединяет то, что все они связаны с местоположением (т.е. «где»), и все три предполагают, что искомое существует. Это концептуальная модель, которая также может быть легко применена к базам данных.
Возьмем, к примеру, интернет-магазин с тысячами товаров и покупателей. Данные хранятся в базах данных. Клиент может искать в базе данных определенный товар и затем заказывать его. Затем диспетчер передает заказанный товар покупателю с его адресной информацией через базу данных. Этот процесс включает в себя несколько задач поиска и сортировки, а также операции вставки и удаления в процессе заказа. Для более эффективного решения этих задач большие объемы связанных данных объединяются в единую адресную позицию в базе данных. Эта позиция вычисляется с помощью хэш-значений и состоит из таблицы с комбинациями букв и цифр, которые всегда имеют одинаковую длину. Наше руководство познакомит вас с основами использования хэш-таблиц.
В чем заключается основная идея хэш-таблицы?
Сначала из информации, содержащейся в наборе данных, вычисляется хэш-значение. Хеш-значения всех наборов данных в базе данных находятся в хеш-таблице. Дополнительная математическая операция вычисляет местоположение информации в базе данных на основе этого хэш-значения. Если пользователь вводит поисковый запрос, он также превращается в хэш-значение. Теперь поиск ведется не по запросу «часы с коричневым кожаным браслетом», а по совпадению исходного хэш-значения предмета с хэш-значением только что введенного поискового термина (т.е. совпадению двух комбинаций букв и цифр). Этот метод используется для поиска очень разнообразных результатов.
Безопасность с использованием хэш-значений
Хеш-таблица создается после того, как терминам были присвоены автоматически сгенерированные хеш-значения. Это символьные строки, которые всегда имеют одинаковую длину и генерируются хэш-функцией. Длина символьной строки и содержащиеся в ней символы определяются используемым методом хэширования. Они используются, например, для защиты информации для входа в систему от атак.
В примере с базой данных WordPress, когда кто-то пытается войти в систему, пароль, введенный пользователем, преобразуется в хэш-значение с помощью той же процедуры, а затем сравнивается с записью в поле базы данных «user_pass». Если два хэш-значения длиной 34 символа совпадают, доступ предоставляется. Хеш-значение невозможно преобразовать в пароль. Это одно из достоинств хэш-функции.
Если бы кто-то попытался взломать систему безопасности с помощью атаки «грубой силы», строку символов, содержащую все допустимые символы, пришлось бы перебирать несколько раз, пока не было бы найдено совпадение. Даже если бы злоумышленник знал используемую хэш-функцию, ему потребовалось бы ровно 839 299 365 868 340 200 попыток, чтобы найти совпадение при использовании заглавных и строчных букв и цифр в пароле длиной в 10 символов.
Более быстрая навигация по базам данных
Хеш-таблицы используются для ускорения поиска и ввода или удаления наборов данных в базах данных. Например, если вы ищете фамилию в базе данных сотрудников компании, этот процесс может занять много времени, поскольку каждое поле базы данных должно быть просмотрено одно за другим (т.е. последовательно) на предмет совпадения. Преобразование поискового запроса в хэш-значение и последующий поиск совпадения в хэш-таблице обычно намного быстрее.
Итак, как это делается? Каждому набору данных присваивается уникальный адрес. Способ их адресации всегда одинаков в пределах базы данных (например, 001, 002, 003 или 00A1, 00A2, 00A3 и т.д.). Этот адрес вычисляется с помощью хэш-функции.
Давайте рассмотрим простой пример. В этом примере база данных может содержать 11 записей с позиции 0 по позицию 10. Имя «Лиза» состоит из четырех символов ASCII с соответствующими им кодами ASCII: «L» — 76, «i» — 105, «s» — 115 и «a» — 97. Вы можете проверить это самостоятельно в Windows с помощью цифровой клавиатуры. Например, [Alt] + 0076 приведет к появлению буквы «L». Все значения ASCII складываются вместе и в результате получается хэш-значение 393 для «Lisa». Сложение значений ASCII эквивалентно использованию хэш-функции.
Затем остаток вычисляется с помощью целых чисел: 393 % 11 (места ввода) = 35, остаток 8 (знак процента «%» используется во многих языках программирования в качестве математического оператора для вычисления остатка). Значение остатка определяет, где в базе данных хранится Лиза и вся остальная информация о ней — в данном примере расчета номер индекса равен 8. Можно представить, что при таком типе адресации значения остатка будут часто повторяться. Однако чем больше мест ввода и чем длиннее хэш-значение, тем меньше вероятность повторения. «Alis Meyer» приводит к совершенно другому расположению, несмотря на использование тех же букв, поскольку «A» теперь является заглавной буквой, а «l» — строчной.
Эта диаграмма иллюстрирует проблему с повторами: Разным именам может быть присвоен один и тот же индекс. Это приводит к столкновениям (показано светло-голубыми стрелками). Что же «делает» база данных, когда происходит подобная «авария»? Она помещает набор данных в следующее доступное место в базе данных. Если в примере вы ищете «Берта Мюллер», поиск не начнется с позиции 001. Вместо этого указатель начнет поиск с позиции индекса 003, что (немного) сократит время поиска имени. Этот метод называется хэшированием с открытой адресацией, которая затем выполняет линейный поиск.
Метод цепочки для адресации использует несколько иной подход. Он не создает новое местоположение для набора данных. Вместо этого новая соответствующая запись связывается или «цепляется» после первой. Это означает, что искомый набор данных можно найти с помощью одного поискового запроса «за» первым набором данных в этом месте. Это ускоряет процесс.
Когда начинается поиск «Berta Müller», указатель устанавливается на значение 003, вычисленное по хэш-таблице, и затем остается только искать цепочку наборов данных в этом месте. Это позволяет более эффективно упаковывать большие объемы данных и ускоряет их поиск.
Этот метод также используется в кэшировании, чтобы к данным, которые были использованы один раз, можно было быстро получить доступ снова. Данные хранятся в кэше как временное хранилище и извлекаются оттуда, когда они соответствуют шаблону, связанному с деятельностью. Например, это происходит с посещаемыми веб-сайтами, которые не нужно полностью перезагружать с сервера при повторном запросе, поскольку они могут быть получены из кэша гораздо быстрее. Cookies также функционируют как форма идентификации, с которой можно сравнивать и которая показывает, где пользователь уже бывал в Интернете.
Каковы различные виды методов хэширования?
Только что описанный выше метод хеширования также известен как открытое или внешнее хеширование, которое позволяет хранить данные в цепочке списков с теоретически неограниченным пространством для хранения. Для этого не требуется больше ключей, а цепочка позволяет обрабатывать большие объемы данных. Слово «открытый» относится к открытой адресации.
При закрытом хешировании количество доступных ключей ограничено емкостью таблицы. Если вы попытаетесь хранить больше данных, чем позволяет ее емкость, произойдет переполнение. При повторном проходе по таблице она будет проверена на наличие свободных мест, куда можно поместить переполнения.
Термины «открытое» и «закрытое» хэширование не имеют четкого определения. Иногда они используются с противоположными значениями в зависимости от публикации. Поэтому рекомендуется ознакомиться и использовать соответствующее подробное описание метода в той же публикации.
Кукушкино хеширование — это еще один метод, позволяющий избежать коллизий в таблицах баз данных. Термин происходит от склонности кукушки выталкивать яйца других птиц из гнезда, чтобы снести свое собственное. Итак, в данном случае две хэш-функции используются для описания двух мест хранения. Если первое место уже занято, хранящийся там ключ будет перемещен в новое место, а его место займет второй сгенерированный ключ. Недостатком этого метода является то, что он может привести к бесконечному циклу поиска, что приведет к прерыванию начатой процедуры из-за таймаута.
Существуют различные методы поиска в базах данных, разработанные с использованием сложных математических формул, которые скрыты в виде программного кода на сайте, например, в поле основного поиска с лупой.
В целом, базы данных становятся все более объемными, поскольку количество данных растет быстрыми темпами. Динамическое хеширование решает эту проблему путем увеличения хеш-таблицы, чтобы избежать коллизий. Однако это приводит к тому, что хэш-значения ранее сохраненных данных также изменяются. Были разработаны специальные хэш-функции, которые элегантно решают эту проблему. Количество данных не ограничено (по крайней мере, теоретически). Однако в этом случае поиск выполняется менее эффективно.
Преимущества и недостатки хэш-таблиц
Самым большим преимуществом использования хэш-таблицы является возможность быстрого поиска в больших объемах данных. Однако это создает проблему для архитекторов базы данных, которые должны заранее оценить необходимый размер, чтобы снизить риск столкновений. В хэш-таблицах можно использовать многие типы данных, если по ним можно вычислить хэш-значения.
К недостаткам хэш-таблиц относится тот факт, что базы данных могут деградировать, если они проходят через большое количество коллизий. Вероятность того, что произойдет столкновение, увеличивается с ростом объема данных. Большое количество хэш-функций не имеют возможности перехода к следующему или предыдущему набору данных.