Вступление :
Хеширование - это важная структура данных, которая предназначена для использования специальной функции, называемой функцией хеширования, которая используется для сопоставления заданного значения с определенным ключом для более быстрого доступа к элементам. Эффективность сопоставления зависит от эффективности используемой хеш-функции.
Пусть хэш-функция H (x) отображает значение
с индексом x% 10 в массиве. Например, если список значений [11,12,13,14,15], он будет сохранен в позициях {1,2,3,4,5} в массиве или хеш-таблице соответственно.
Фаза 1 обучения
Предположим, мы хотим разработать систему для хранения записей сотрудников, использующих номера телефонов. И мы хотим, чтобы следующие запросы выполнялись эффективно:
- Вставьте номер телефона и соответствующую информацию.
- Найдите номер телефона и получите информацию.
- Удалите номер телефона и связанную с ним информацию.
Мы можем подумать об использовании следующих структур данных для хранения информации о разных телефонных номерах.
- Массив телефонных номеров и записей.
- Связанный список телефонных номеров и записей.
- Сбалансированное двоичное дерево поиска с номерами телефонов в качестве ключей.
- Таблица прямого доступа.
Для массивов и связанных списков нам необходимо выполнять линейный поиск, что на практике может быть дорогостоящим. Если мы используем массивы и сохраняем сортировку данных, то телефонный номер можно будет искать за O (Logn) времени с помощью двоичного поиска, но операции вставки и удаления становятся дорогостоящими, так как мы должны поддерживать порядок сортировки.
Благодаря сбалансированному двоичному дереву поиска мы получаем умеренное время поиска, вставки и удаления. Можно гарантировать, что все эти операции будут выполнены за время O (Logn).
Еще одно решение, которое можно придумать, - использовать таблицу прямого доступа, в которой мы создаем большой массив и используем номера телефонов в качестве индекса в массиве. Запись в массиве - NIL, если номер телефона отсутствует, иначе запись массива хранит указатель на записи, соответствующие номеру телефона. С точки зрения сложности по времени это решение является лучшим среди всех, мы можем выполнять все операции за O (1) раз. Например, чтобы вставить номер телефона, мы создаем запись с подробностями данного номера телефона, используем номер телефона в качестве индекса и сохраняем указатель на созданную запись в таблице.
Это решение имеет множество практических ограничений. Первая проблема с этим решением заключается в том, что требуется огромное дополнительное пространство. Например, если номер телефона состоит из n цифр, нам нужно пространство O (m * 10n) для таблицы, где m - размер указателя на запись. Другая проблема заключается в том, что целое число в языке программирования может не хранить n цифр.
Из-за вышеуказанных ограничений таблица прямого доступа не всегда может быть использована. Хеширование - это решение, которое можно использовать практически во всех подобных ситуациях, и на практике оно работает очень хорошо по сравнению с вышеуказанными структурами данных, такими как массив, связанный список, сбалансированный BST. При хешировании мы получаем время поиска O (1) в среднем (при разумных предположениях) и O (n) в худшем случае.
Хеширование - это улучшение по сравнению с таблицей прямого доступа. Идея состоит в том, чтобы использовать хеш-функцию, которая преобразует данный номер телефона или любой другой ключ в меньшее число и использует это маленькое число в качестве индекса в таблице, называемой хеш-таблицей.
Хеш-функция: функция, которая преобразует заданный большой телефонный номер в небольшое практическое целое число. Отображенное целочисленное значение используется в качестве индекса в хеш-таблице. Проще говоря, хеш-функция преобразует большое число или строку в небольшое целое, которое может использоваться в качестве индекса в хеш-таблице.
Хорошая хеш-функция должна иметь следующие свойства
1) Эффективно вычислимая.
2) Должны равномерно распределять ключи (каждая позиция в таблице одинаково вероятна для каждого ключа)
Например, для телефонных номеров плохая хеш-функция должна принимать первые три цифры. Лучше рассмотреть последние три цифры. Обратите внимание, что это может быть не лучшая хеш-функция. Могут быть способы получше.
Хеш-таблица: массив, в котором хранятся указатели на записи, соответствующие заданному номеру телефона. Запись в хэш-таблице равна NIL, если ни один из существующих телефонных номеров не имеет значения хэш-функции, равного индексу записи.
Обработка конфликтов. Поскольку хеш-функция дает нам небольшое число для большого ключа, существует вероятность того, что два ключа приведут к одному и тому же значению. Ситуация, когда вновь вставленный ключ отображается на уже занятый слот в хеш-таблице, называется коллизией и должна обрабатываться с помощью некоторой техники обработки коллизий. Ниже приведены способы обработки столкновений:
- Цепочка. Идея состоит в том, чтобы каждая ячейка хеш-таблицы указывала на связанный список записей, которые имеют одинаковое значение хеш-функции. Цепочка проста, но требует дополнительной памяти за пределами таблицы.
- Открытая адресация. При открытой адресации все элементы хранятся в самой хеш-таблице. Каждая запись таблицы содержит либо запись, либо NIL. При поиске элемента мы один за другим исследуем слоты таблицы, пока не будет найден нужный элемент или пока не станет ясно, что этого элемента нет в таблице.
Фаза 2 обучения
Что такое коллизия?
Поскольку хеш-функция возвращает нам небольшое число для ключа, который является большим целым числом или строкой, существует вероятность того, что два ключа приведут к одному и тому же значению. Ситуация, когда вновь вставленный ключ отображается на уже занятый слот в хеш-таблице, называется коллизией и должна обрабатываться с помощью некоторой техники обработки коллизий.
Какова вероятность столкновения с большой таблицей?
Столкновения очень вероятны, даже если у нас есть большая таблица для хранения ключей. Важное наблюдение - Парадокс дня рождения. При наличии всего 23 человек вероятность того, что у двух людей один и тот же день рождения, составляет 50%.
Как справляться с коллизиями?
В основном есть два метода обработки коллизий:
1) Раздельное связывание
2) Открытая адресация
В этой статье только обсуждается отдельная цепочка. Мы обсудим открытую адресацию в следующем посте.
Раздельное объединение:
Идея состоит в том, чтобы каждая ячейка хеш-таблицы указала на связанный список записей, которые имеют одинаковое значение хеш-функции.
Давайте рассмотрим простую хеш-функцию как «key mod 7» и последовательность ключей как 50, 700, 76, 85, 92, 73, 101.
Программа на C ++ для хеширования с цепочкой
Преимущества:
1) Простота реализации.
2) Хеш-таблица никогда не заполняется, мы всегда можем добавить больше элементов в цепочку.
3) Менее чувствительны к хеш-функция или коэффициенты загрузки.
4) Обычно используется, когда неизвестно, сколько и как часто ключей можно вставлять или удалять.
Недостатки:
1) Производительность цепочки кеш-памяти невысока, поскольку ключи хранятся с использованием связанного списка. Открытая адресация обеспечивает лучшую производительность кеша, поскольку все хранится в одной таблице.
2) Потеря места (некоторые части хеш-таблицы никогда не используются)
3) Если цепочка становится длинной, время поиска может в худшем случае становится O (n).
4) Использует дополнительное место для ссылок.
Производительность объединения.
Производительность хеширования можно оценить, исходя из предположения, что каждый ключ с одинаковой вероятностью будет хеширован в любой слот таблицы (простое равномерное хеширование).
m = Number of slots in hash table n = Number of keys to be inserted in hash table Load factor α = n/m Expected time to search = O(1 + α) Expected time to insert/delete = O(1 + α) Time complexity of search insert and delete is O(1) if α is O(1)
Фаза-3 Обучение
Открытая адресация
Как и отдельная цепочка, открытая адресация - это метод обработки коллизий. В открытой адресации все элементы хранятся в самой хеш-таблице. Таким образом, в любой момент размер таблицы должен быть больше или равен общему количеству ключей (обратите внимание, что мы можем увеличить размер таблицы, скопировав старые данные, если это необходимо).
Вставка (k): продолжайте прощупывать, пока не найдете пустой слот. Как только будет найден пустой слот, вставьте k.
Поиск (k): продолжайте исследование, пока ключ слота не станет равным k или пока не будет достигнут пустой слот.
Удалить (k): Интересна операция удаления. Если мы просто удалим ключ, поиск может закончиться неудачей. Поэтому слоты удаленных ключей помечаются как «удаленные».
Insert может вставить элемент в удаленный слот, но поиск не останавливается на удаленном слоте.
Открытая адресация осуществляется следующими способами:
а) Линейное зондирование: При линейном зондировании мы линейно зондируем следующий слот. Например, типичный промежуток между двумя зондами равен 1, как показано в примере ниже.
пусть hash (x) будет индексом слота, вычисленным с использованием хеш-функции и S быть размером стола
If slot hash(x) % S is full, then we try (hash(x) + 1) % S If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S .................................................. ..................................................
Давайте рассмотрим простую хеш-функцию как «key mod 7» и последовательность ключей как 50, 700, 76, 85, 92, 73, 101.
Кластеризация. Основная проблема с линейным зондированием - это кластеризация, многие последовательные элементы образуют группы, и для поиска свободного места или поиска элемента требуется время.
б) Квадратичное зондирование. Мы ищем i2-й слот на i-й итерации.
let hash(x) be the slot index computed using hash function. If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S .................................................. ..................................................
c) Двойное хеширование. Мы используем другую хеш-функцию hash2 (x) и ищем слот i * hash2 (x) в i-м чередовании.
let hash(x) be the slot index computed using hash function. If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S .................................................. ..................................................
См. Это для пошаговых диаграмм.
Сравнение трех вышеперечисленных:
Линейное зондирование имеет лучшую производительность кеширования, но страдает от кластеризации. Еще одно преимущество линейного зондирования - легко вычислить.
Квадратичное зондирование находится между ними с точки зрения производительности кеша и кластеризации.
Двойное хеширование имеет низкую производительность кеша, но не имеет кластеризации. Двойное хеширование требует большего времени вычислений, поскольку необходимо вычислить две хеш-функции.
S.No. Раздельное связывание Открытая адресация 1. Объединение проще реализовать. Открытая адресация требует дополнительных вычислений. 2. В цепочке хеш-таблица никогда не заполняется, мы всегда можем добавить больше элементов в цепочку. При открытой адресации таблица может заполниться. 3. Цепочка менее чувствительна к хэш-функции или факторам нагрузки. Открытая адресация требует особой осторожности, чтобы избежать кластеризации и коэффициента нагрузки. 4. Сцепление в основном используется, когда неизвестно, сколько и как часто ключи могут быть вставлены или удалены. Открытая адресация используется, когда известны частота и количество ключей. 5. Производительность цепочки кеш-памяти невысока, так как ключи хранятся в связанном списке. Открытая адресация обеспечивает лучшую производительность кеша, поскольку все хранится в одной таблице. 6. Потеря места (некоторые части хеш-таблицы в цепочке никогда не используются). При открытой адресации слот можно использовать, даже если вход не сопоставлен с ним. 7. Цепочка использует дополнительное пространство для ссылок. Нет ссылок в открытой адресации
Производительность открытой адресации.
Как и при использовании цепочки, производительность хеширования можно оценить, исходя из предположения, что каждый ключ с одинаковой вероятностью будет хеширован в любой слот таблицы (простое равномерное хеширование).
m = Number of slots in the hash table n = Number of keys to be inserted in the hash table Load factor α = n/m ( < 1 ) Expected time to search/insert/delete < 1/(1 - α) So Search, Insert and Delete take (1/(1 - α)) time
Ссылка: https://www.geeksforgeeks.org/
Пожалуйста, дайте мне знать, если что-то неясно или есть что-то еще, что вы хотели бы увидеть в этой или следующей статье. Не стесняйтесь обращаться ко мне в любое время, если хотите что-то обсудить. Буду более чем счастлив, если вы присылаете свои отзывы, предложения.
Спасибо, что дочитали до конца. Вы можете связаться со мной, если вам понадобится помощь:
Интернет: https://portfolio.abhisheksrivastava.me/
Instagram: https://www.instagram.com/theprogrammedenthusiast/
LinkedIn: https: // www. linkedin.com/in/abhishek-srivastava-49482a190/
Github: https://github.com/abhishek2x
Электронная почта: [email protected]
