Краткое введение в хеш-таблицу и связанные с ней концепции

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

Что такое словарь?

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

Простой словарь → {key_1: value_1, key_2: value_2, ……., Key_n: value_n}

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

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

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

Таблица прямых адресов

Один из самых простых способов сохранить ключи (productIds) и соответствующие им значения (цены) - использовать таблицу прямых адресов. Таблица прямых адресов - это не что иное, как массив, где каждая позиция / слот соответствует ключу в универсальном наборе U. На следующей диаграмме показано использование таблицы прямых адресов для хранения пар ключ-значение.

Каждый элемент в наборе U отображается в соответствующий ему слот в массиве T (для простоты на диаграмме отображаются только ключи 0, 1 и 2). Здесь pᵢ - цена, соответствующая ключу i. Из диаграммы видно, что слот k в массиве T соответствует ключу k в универсальном наборе U и T [k] - значение, соответствующее ключу k.

Любая структура данных поддерживает три основные функции: вставку, удаление и поиск.

INSERT(T, key, value):
   T[key] = value
DELETE(T, key):
   T[key] = NIL
SEARCH (T, key):
   return T[key]

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

Ограничение таблицы прямого доступа

Давайте продолжим наш сценарий владельца магазина.

Ограничение 1:

Через некоторое время вы замечаете, что ваш магазин убыточен, и вы решаете продавать только ограниченное количество фруктов и овощей. Предположим, вы планируете продавать только m (m ‹n) разновидностей фруктов и овощей и каждую неделю будете менять сорт. Теперь ваша таблица прямого доступа будет выглядеть так.

Желтая область содержит m количество клавиш, которые соответствуют m разнообразию фруктов и овощей, которые вы выбрали. Теперь только слоты, соответствующие клавишам в желтой области, имеют значения, а остальные - NIL, то есть используются только m слотов из n слотов, и мы тратим память занято (mn) слотами. Предположим, что n = 100000 и m = 1000, тогда вы потратите 99% памяти, выделенной для массива. Следовательно, когда размер универсального набора U очень велик по сравнению с фактическим количеством используемых ключей, таблица прямого доступа становится неэффективной с точки зрения использования памяти.

Ограничение 2:

Что делать, если у вас 2 ГБ ОЗУ и вы используете 8 байтов для хранения каждого значения (цены)?

Максимальный размер массива T = (2 * 1024 * 1024 * 1024) / 8 = 268 435 456

Если размер универсального набора U больше 268 435 456, то таблицу прямого доступа использовать нельзя, так как будет недостаточно памяти для создания массива.

Следовательно, таблица прямого доступа будет работать только для разумного размера n.

Хеш-таблицы

Хеш-таблицы преодолевают оба вышеупомянутых ограничения. Но как работает хеш-таблица ???

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

Хеш-функция отображает каждый ключ в универсальном наборе U на слот в массиве T. Если размер массива T равен m, то

h : U → {0 , 1, 2, …, m-1}

Ранее для таблицы прямого доступа размер массива T должен был быть | U | (размер U). Однако хеш-таблица позволяет иметь размер массива m (m ‹| U |), т.е. мы можем создать массив из любых size, независимо от размера универсального набора U. Следовательно, хеш-таблица не имеет двух ограничений, которые имеет таблица прямого доступа.

Несмотря на то, что хеш-таблица преодолевает ограничения таблицы прямых адресов, у хеш-таблицы есть свои проблемы.

Столкновение

Что произойдет, если два разных ключа k₁ и k₂ будут иметь одинаковое хеш-значение, т.е. h (k₁) = h (k₂)? Такое явление называется столкновением. К счастью, есть способы справиться с этим.

  • Выбор эффективной хеш-функции, которая эффективно распределяет ключи, снизит вероятность возникновения коллизии. Назовем набор реальных ключей в желтой области набором W. Если размер набора W больше, чем размер массива T (т.е. | W | ›| T |), то полностью избежать столкновения невозможно. Однако количество конфликтов можно минимизировать за счет использования эффективной хеш-функции, которая равномерно распределяет ключи.
  • Цепочка - это еще один подход, используемый для разрешения коллизий. Предположим, два ключа k₁ и k₄ имеют одинаковое хеш-значение, затем мы сохраняем их, используя связанный список (часто двусвязные списки), как показано на диаграмме ниже.

Сложность времени в цепочке хеш-таблиц

  • Вставка

Пары "ключ-значение" вставляются в начало связанного списка. Если мы сделаем предположение, что вставляемый ключ еще не присутствует, тогда время выполнения вставки в наихудшем случае будет O (1). Мы можем проверить, присутствует ли ключ уже или нет, перед вставкой за дополнительную плату (которая пропорциональна размеру связанного списка, поскольку вам нужно пройти через связанный список)

  • Удаление

Учитывая, что связанный список является двусвязным списком, элемент x (пара ключ-значение / узел в связанном списке) в двусвязном списке может быть удален в худшем случае. временная сложность O (1) (подробнее об удалении в двусвязных списках). Однако, если входом для функции удаления является ключ k (а не узел x), то временная сложность удаления пропорциональна размеру связанного списка, поскольку вы необходимо пройти через связанный список, чтобы найти соответствующий узел.

  • Поиск

Для поиска время выполнения в худшем случае составляет O (| W |), потому что в худшем случае хеш-функция даст одно и то же хеш-значение для всех ключей. Однако на практике этого никогда не происходит. Теоретически было доказано, что среднее время работы составляет Θ (1 + n / m) в предположении простого равномерного хеширования для хеш-таблицы размера m, в котором хранится n элементов (n / m определяется как коэффициент нагрузки ).

Что такое хорошая хеш-функция?

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

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

Ресурс: Кормен, Т. Х., Лейзерсон, К. Э., Ривест, Р. Л., и Стейн, К. (2009). Введение в алгоритмы. Пресса MIT.