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

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

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

Сложность хеш-таблицы

Лучший/худший случай

  1. Пробел: O(n)/O(n)
  2. Поиск: O(1)/O(n)
  3. Вставка: О(1)/О(н)
  4. Удалить: O(1)/O(n)

Наилучший и наихудший случай для пространства — это n, который представляет собой объем хранимых данных. Лучший случай для поиска, вставки и удаления — O(1), что означает, что он мгновенно находит местоположение искомого значения, но худший случай — O(n). В худшем случае метод хеширования приводит к одной и той же строке снова и снова для всех значений, поэтому ему приходится просматривать все в местоположении.

В зависимости от метода хеширования можно иметь один и тот же хеш-код в качестве вывода несколько раз, как при моддинге. Вот почему важно иметь хороший метод хеширования, чтобы свести к минимуму вероятность этого. Но в случае, если это произойдет, важно иметь способ справиться с этим. Есть 2 разных способа передать это:

  1. Каждое ведро будет содержать связанный список элементов, поэтому любые элементы с одинаковым хэш-кодом будут помещены в связанный список. Вот откуда исходит наихудший случай O(n), когда все помещается в одно и то же ведро и связанный список.
  2. Увеличьте размер корзины, чтобы значения в связанном списке перераспределялись. В этом случае метод has должен быть обновлен, чтобы учесть новый размер корзины.

Вывод

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