Статья посвящена тому, как работает хеширование, начиная с его истории и заканчивая его реализацией на C++.
ТЫ ВЫУЧИШЬ:
1. Что такое хеширование
2. Основные элементы алгоритма хэширования
3. Плюсы и минусы
4. Реализация
1. ЧТО ТАКОЕ ХЕШИРОВАНИЕ
Хеширование — это «искусство» преобразования ключевого значения информации в индекс области памяти в массиве.
Вы когда-нибудь задумывались, как можно найти определенного человека в списке контактов, используя только его номер телефона или фамилию, и получить действительно быстрый ответ с вашего мобильного телефона? Или, возможно, как все ваши пароли безопасности от всех ваших онлайн-аккаунтов хранятся в безопасности? (криптографически)… Или, может быть, как учителя могут узнать, занимаются ли их ученики плагиатом? (Алгоритм Рабина-Карпа)…. Или даже как ваш маршрутизатор Wi-Fi доставляет ваши сообщения из пункта А в пункт Б, не изменяя их содержания?
Все упомянутые выше примеры были разработаны и основаны на идее, использованной в «Алгоритме хеширования», поэтому, если вы хотите узнать, как это работает на уровне программирования, то вы попали по адресу!
ЗАДНИЙ ПЛАН
В 1958 году Ганс Петер Лун представил на международной научной конференции машину под названием «KWIC для ключевых слов в контексте», которая могла обрабатывать большое количество текстов длиной от 500 до 5000 слов, а система KWIC могла автоматически построить своего рода индекс.
В то время индексировать и классифицировать информацию было довольно сложно из-за объема и сложности статей. Кроме того, было трудно уследить за классификацией (индексацией), поскольку информация во многих областях росла слишком быстро.
«К началу 1960-х годов KWIC стал центральным элементом разработки сотен компьютеризированных систем индексации, в том числе тех, которые использовались Химической реферативной службой, Биологической реферативной службой и Институтом научной информации. KWIC был своего рода аналогом поисковой системы того времени: он позволял пользователям быстро находить нужную им информацию».
(IEEE SPECTRUM – Hallam Stevens/2018).
Нет никаких сомнений в том, что созданная Питером машина KWIC стала важной вехой в разработке новых и более сложных способов для компьютеров просматривать и хранить данные, такие как базы данных, идентификация шаблонов и хранение паролей.
2. Принципиальные элементы алгоритма хеширования
ВВЕДЕНИЕ В КОНЦЕПЦИЮ:
4 основные части: значение ключа, функция хеширования, хеш-таблица и коллизии.
· Ключевое значение:
Часть информации, с которой вы собираетесь связать информацию, которую хотите сохранить в безопасности.
· Функция хеширования:
Алгоритм, который преобразует значение ключа в индекс, который сообщает вам, где вы можете найти, вставить или удалить запись в массиве, в котором хранится вся информация.
Другими словами, он сопоставляет значение ключа со значением индекса, которое можно использовать в качестве места в массиве.
· Хеш-таблица:
(Структура данных) Массив, в котором хранится информация.
· Столкновение:
Много раз после прохождения через хеш-функцию разные значения ключа могут давать одно и то же значение индекса.
Это большая проблема! Потому что у вас не может быть двух элементов информации в ОДНОМ месте. Следовательно, вам нужен способ поиска нового места для хранения новой информации.
Существует множество способов обработки столкновений. Наличие хорошей "функции хэширования" позволяет правильно распределять индексы и память в массиве.
Однако, когда коллизии неизбежны, есть много способов справиться с коллизиями, и это два наиболее распространенных способа обработки коллизий:
- Открытая адресация (линейное зондирование). Поиск следующего доступного места в массиве для размещения новой информации.
- Сцепление. Идея состоит в том, чтобы каждая ячейка хэш-таблицы указывала на связанный список записей с одинаковым значением хеш-функции.
Теперь, когда вы знаете все элементы хэширования… вы можете задаться вопросом, что, черт возьми, представляет собой исходная картинка?! Ну, это неуместная и из ряда вон выходящая история, чтобы вы запомнили понятия хеширования.
Бандитский сыр пытается украсть сочную мышь (хеш-таблица — информация, которую вы хотите сохранить), и для выполнения своей миссии сыру требуется огромный ключ (значение ключа), чтобы открыть таинственный и волшебный замок (хеш-функция). , которые открываются только правильным ключом.
*(Эта идея пришла из культурного знания, что «все мыши любят сыр и всегда пытаются его украсть», как в популярном фильме «Рататуй»).
Это очень нелепо, я знаю, но с этого момента, когда вы пытаетесь вспомнить, как работает «хэширование», вы будете вспоминать зло и головореза, пытающихся украсть мышь!
3. Плюсы и минусы
ПЛЮСЫ
• Поиск O(1): среднее время поиска (при разумных предположениях).
• Безопасность
• Быстрый поиск данных
МИНУСЫ
• Поиск O(n) в худшем случае. (Линейное время/пройдите через все элементы, чтобы добраться до нужного)
- Столкновения, столкновения и еще раз столкновения!
4. Реализация
Важно отметить, что следующий пример кода был получен в GeeksforGeeks, и было сделано лишь несколько изменений, чтобы дополнить концепции. Все части, которые были изменены или включены в код, также были упомянуты в комментариях к коду:
ПРИМЕР:
В этом случае будет использоваться метод цепочки для обработки коллизий, и все аспекты хэширования будут рассмотрены в этом примере:
Во-первых, были включены все стандартные библиотеки. Кроме того, было включено «использование пространства имен std», чтобы сократить время и строки кода каждый раз, когда что-то должно было быть напечатано на мониторе.
Следующей частью было объявление нашего класса HASH, в котором мы собирались разработать эту структуру данных.
На следующем рисунке в строке 41 объявлена самая распространенная хэш-функция, которая возвращает модуль ключа, деленный на количество элементов в списке, то есть BUCKETS. Возвращаемое значение — это число от 0 до BUCKETS, которое будет индексом, в котором будет храниться значение.
Например, если BUCKETS=10, то хэш-таблица будет иметь значения от 0 до 9, и в результате применения хеш-функции возвращаемые значения будут индексами от 0 до 9.
Поэтому, если необходимо добавить значение ключа 12, позиция в списке, куда оно будет добавлено, соответствует позиции 2 хеш-таблицы. То же самое относится и к значениям 48, которые будут размещены в позиции 8, и 75 в позиции 5.
Как только все атрибуты и методы были объявлены в классе, следующим шагом будет объявление конструктора по умолчанию, единственной обязанностью которого является определение количества доступных пробелов в списке, который должен быть созданный под названием table. Эта таблица будет представлять окончательную хеш-таблицу, в которой будут объединены все вставленные элементы.
Следующим шагом будет реализация всех действий, которые будут выполняться методами:
Первым методом был insertItem(), который напрямую использует push_back для вставки элемента в конец списка, что в данном случае будет значением индекса, предоставленным хэш-функция. Автоматически новый элемент вставляется в связанный список, где сохраненное значение в хэш-таблице является указателем на первое значение. Это будет продолжаться для всех новых значений, которые вставляются и имеют один и тот же индекс.
Для deleteItem() необходимо просмотреть один за другим все элементы в связанном списке, начиная со значения индекса в хеш-таблице. Если поиск достигает конца таблицы, а значение не найдено, будет отображаться сообщение об ошибке.
С другой стороны, если значение ключа действительно найдено, то значение будет стерто, а хэш-таблица будет отображаться снова.
Для searchItem() код был в основном таким же, как и для deleteItem(). Единственная разница заключается в том, что в этом случае будет только сообщение, сообщающее пользователю, было ли найдено заданное значение ключа или нет.
Наконец, , showHash() реализует вывод хэш-таблицы.
Чтобы наглядно представить, как работает этот код, был реализован массив всего из 4 значений 15,10,12 и 28 для реализации их в хеш-таблице. Затем создается объект типа Hash для размещения 4 начальных значений, находящихся в массиве a[].
Окончательный результат был следующим:
Как упоминалось ранее, функция deleteItem() использовалась для значения ключа (12), которое было найдено, и хеш-таблица была распечатана снова, чтобы увидеть разницу. Кроме того, значение 10 было найдено в позиции 2 хеш-таблицы. Снова использовалась функция deleteItem() со значением 12, но на этот раз она не была найдена и было выдано сообщение об ошибке.
Обертка
- Основная цель хеширования — индексация данных и сокращение времени на вставку, удаление и поиск.
- Основными элементами хеширования являются значение ключа, хэш-функция, хеш-таблица и коллизии (вспомните вора сыра!).
- Чтобы избежать коллизий, нужно иметь хорошую хэш-функцию или использовать такие методы, как линейное зондирование или цепочка.
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА
- Дейл, Н. Б. (2003). Структуры данных C++ Plus: Vol. 3-е изд.. Джонс и Бартлетт Обучение.
- Ли, Гэри (2014) Алгоритмы на основе хэша. Облачная сеть.
- Пратик, Г. (nd). Основы хеш-таблиц. Учебные пособия и примечания: структуры данных. Получено 18 ноября 2020 г. с https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/
- Рана, С. (2018, 06 сентября). Хеширование: Набор 1 (Введение). Получено 15 ноября 2020 г. с https://www.geeksforgeeks.org/hashing-set-1-introduction/?ref=lbp.
- Стивенс, Х. (30 января 2018 г.). Ганс Питер Лун и рождение алгоритма хеширования. Получено 17 ноября 2020 г. с https://spectrum.ieee.org/tech-history/silicon-revolution/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm.