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

Обертка

  • Основная цель хеширования — индексация данных и сокращение времени на вставку, удаление и поиск.
  • Основными элементами хеширования являются значение ключа, хэш-функция, хеш-таблица и коллизии (вспомните вора сыра!).
  • Чтобы избежать коллизий, нужно иметь хорошую хэш-функцию или использовать такие методы, как линейное зондирование или цепочка.

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА