Что такое хеш-таблицы?

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

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

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

Например:

у нас есть 10 ключевых значений, поэтому мы резервируем 10 индексов в памяти для вставки данных.

ключевые значения: 10,76,82,19,17,55,43,91,88,64

В этом примере мы собираемся использовать k mod 10 в качестве хеш-функции.

А вот и формула h´(k) = k 𝑚𝑜𝑑 10 или h´(k) = k 𝑚𝑜𝑑 n

Вот наша пустая память, пиши сейчас,

мы взяли ключевое значение 10 и передали его в качестве входных данных в хеш-функцию

10 mod 10 = 0, поэтому мы вставим 10 в индекс 0 следующим образом.

Теперь второе значение ключа, равное 76

76 по модулю 10 = 6

теперь мы будем хранить 76 в индексе 6, вот так

Теперь следующее значение ключа, равное 82

82 по модулю 10 = 2

теперь мы будем хранить 82 по индексу 2, вот так

теперь у меня есть вывод всех значений ключей, вставленных в качестве входных данных в хеш-функцию, например,

Вставка проста, удаление также просто, нам просто нужно найти индекс с помощью хэш-функции, позвольте мне объяснить.

Удаление и обновление:

если я хочу удалить значение ключа, например 44, тогда я применю режим 44 10 = 4, и мы можем легко удалить или обновить данные, хранящиеся (44) в индексе 4.

Но во всей этой процедуре есть проблема, которая называется "Проблема столкновения"

Проблема конфликта: когда разные ключи создают один и тот же хеш-код в хеш-таблице. Это может привести к перезаписи данных и двусмысленности поиска. Если у нас есть ключевые значения, такие как 44 и 74, тогда вывод будет 4,

  1. какой из них будет храниться на 4 index.
  2. Как это решить.
  3. Как мы можем хранить оба.

Разрешение конфликтов.Существуютметоды обработки конфликтов в хэш-таблицах, когда несколько ключей создают один и тот же хэш-код, в том числе

  1. отдельная цепочка
  2. открытые методы адресации

Separate Chaining. Метод разрешения коллизий в хеш-таблицах, где каждый слот содержит связанный список. Сталкивающиеся ключи хранятся в виде узлов в связанном списке, связанном с их соответствующим слотом.Я предполагаю, что вы уже знаете структуру данных связанного списка.

Например, у нас есть ключевые значения «54,12,22,32,67,77,88,42», так как «12,22,32» будут иметь тот же индекс, поэтому мы создадим связанный список здесь и в случае « 67,77» мы точно так же разобрались с ситуацией.

Как это работает:

Инициализация. Изначально все слоты в хеш-таблице пусты.

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

Связанный список.Вместо замены существующего значения связанный список создается в слоте/индексе. Каждый узел в связанном списке содержит пару ключ-значение. Если последующие коллизии происходят в том же слоте, к существующему связанному списку добавляются новые узлы.

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

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

Отменить раздельную цепочку:

  1. Увеличенный объем памяти. Для создания отдельных цепочек требуется дополнительная память для хранения связанных списков. Каждый слот в хеш-таблице, который испытывает коллизии, должен поддерживать связанный список, для которого требуется дополнительная память, и если мы заметили в хеш-таблице, что много индексов памяти все еще пусты, например, номер индекса 4,6,7,8,9
  2. Дополнительный указатель. Каждому узлу в связанном списке требуется дополнительный указатель для хранения ссылки на следующий узел. Это увеличивает использование памяти на элемент.
  3. Дополнительная сложность: реализация отдельной цепочки требует управления связанными списками, добавление, удаление и обновление становятся более сложными. Эта сложность может усложнить реализацию и обслуживание хеш-таблиц с отдельными цепочками.

Сейчас ,

Открытая адресация:

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

Алгоритмические зонды.Алгоритмические зонды относятся к процессу поиска следующего доступного слота при возникновении коллизии.

Существует три общих метода, используемых для поиска следующего доступного слота при возникновении коллизии.

  1. Линейное зондирование
  2. Квадратичное зондирование
  3. Двойное хеширование:

Линейное зондирование:

При линейном зондировании

Сначала нам нужно найти h´(k) = k 𝑚𝑜𝑑 n, как мы всегда делаем

Если столкновение происходит в индексе i, алгоритм проверяет следующий слот i+1, который является следующим слотом. Если этот слот также занят, он продолжает проверять последующие слоты i+2, i+3 и так далее, пока не будет найден пустой слот.

Последовательность зондирования следует линейной прогрессии, отсюда и название «линейное зондирование».

Пример:

Предположим, у нас есть хеш-таблица с 10 слотами и следующая хэш-функция:

Хэш-функция: hash(key) = key % 10

Мы будем использовать линейное зондирование для разрешения коллизий. Вот как работает процесс вставки:

Вставка:

  • Мы хотим вставить пару ключ-значение (23) в хеш-таблицу.
  • Рассчитываем начальный индекс с помощью хеш-функции: hash(23) = 23 % 10 = 3.
  • Если слот с индексом 3 пуст, мы сохраняем значение там.
  • Если слот занят, мы используем линейное зондирование, чтобы найти следующий доступный слот.
  • Мы проверяем следующий слот, увеличивая индекс на 1: 3 + 1 = 4.
  • Если слот с индексом 4 пуст, мы сохраняем значение там.
  • Если он занят, мы снова проверяем: 3 + 2 = 5.
  • Продолжаем этот процесс до тех пор, пока не будет найден свободный слот.

Поиск:

  • Чтобы получить значение, связанное с ключом 23, мы вычисляем начальный индекс: hash(23) = 3.
  • Мы проверяем, соответствует ли значение по индексу 3 ключу. Если нет, мы ищем следующий слот, увеличивая индекс: 3 + 1 = 4.
  • Значение по индексу 4 не совпадает, поэтому мы снова проверяем: 4 + 1 = 5.

Квадратичное зондирование:

Сначала мы должны найти h´(k) = k 𝑚𝑜𝑑 n, как мы всегда делаем, если происходит столкновение, тогда мы будем использовать квадратичное зондирование, чтобы найти следующий индекс слота.

Квадратичное измерение использует квадратное уравнение для определения следующего положения датчика.

Когда происходит коллизия по индексу , алгоритм проверяет следующий слот по формуле i + 1^2, затем i + 2^2, i + 3^2 и так далее, пока не будет найден пустой слот.

Квадратичное зондирование может помочь уменьшить кластеризацию по сравнению с линейным зондированием.

Пример:

Предположим, у нас есть хеш-таблица с 10 слотами и следующая хэш-функция:

Хэш-функция: hash(key) = key % 10

Мы будем использовать квадратичное зондирование для разрешения коллизий. Вот как работает процесс вставки:

Вставка:

  • Мы хотим вставить ключ(23) в хеш-таблицу.
  • Рассчитываем начальный индекс с помощью хеш-функции: hash(23) = 23 % 10 = 3.
  • Если слот с индексом 3 пуст, мы сохраняем значение там.
  • затем следующее значение позволяет предположить 33, затем, применяя хеш-функциюhash(33) = 33 % 10 = 3
  • Поскольку слот занят, мы используем квадратичное зондирование, чтобы найти следующий доступный слот.
  • Мы вычисляем смещение зонда, используя квадратичную функцию:i^2.
  • Начиная с индекса 3, мы прощупываем следующий слот, используя смещение: 3 + 1^2 = 4.
  • Если слот с индексом 4 пуст, мы сохраняем значение там.
  • Если занято, снова проверяем: 3 + 2^2 = 7.
  • и снова и снова, пока не найдем пустой слот.

Поиск:

  • Чтобы получить значение, связанное с ключом 23, мы вычисляем начальный индекс: hash(23) = 3.
  • Мы проверяем, соответствует ли значение по индексу 3 ключу. Если нет, мы используем квадратичное зондирование для зондирования следующего слота.
  • Используя квадратичную функцию, мы зондируем: 3 + 1^2 = 4. Значение в индексе 4 не совпадает.
  • Мы снова проверяем: 3 + 2^2 = 7, пока не найдем желаемое значение ключа.

Двойное хэширование:

Сначала мы должны найти h1´(k) = k 𝑚𝑜𝑑 n, как мы всегда делаем, если произойдет столкновение, тогда мы будем использовать двойное хеширование, чтобы найти следующий слот.

есть две формулы

h2´(k) = 8-(k 𝑚𝑜𝑑 8) — → это обобщает все значения

(h1´(k) + h2´(k))mod n

Пример:

Предположим, что размер хеш-таблицы равен 10 ;

Основная хэш-функция: h1(k) = k % 10

Вторичная хэш-функция: h2(k) = 8 - (k % 8)

Давайте вставим несколько ключей в хеш-таблицу:

Вставка:

Вставка (23):

  • Вычислите первичный хэш: h1(23) = 23 % 10 = 3.
  • Вставьте индекс 3.

Вставка (43):

  • Вычислите первичный хэш: h1(43) = 43 % 10 = 3.
  • Вычислите вторичный хэш: h2(43) = 8 - (43 % 8) = 8 - 3= 5.
  • (h1(43)+h2(43))mod10 =>(3+5) mode 10=8
  • Вставьте индекс 8.

Вставка (53):

  • Вычислите первичный хэш: h1(53) = 53 % 10 = 3.
  • Вычислите вторичный хеш: h2(53) = 8 - (53 % 8) = 8 - 5= 3.
  • (h1(53)+h2(53))mod10 =>(3+3) mode 10=6
  • Вставьте индекс 6.

и так далее мы применяем их ко всем значениям размера массива 10.

Кластеризация в линейной задаче:

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

Вывод:

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