Алгоритмы и структуры данных

Структура данных: Хэш-таблица

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

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

Идея

Ключевая идея хэш-таблицы заключается в двух вещах:

  • Использовании массива для хранения пар, что дает
  • Хэширования

Элементы массива же в хэш-таблице называются бакетами (bucket). Хэш-функция используется для распределения пар в массиве бакетов.

Имея ключ, индекс бакета высчитывается следющим образом:

hash = hashfunc(key)
index = hash % array_size

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

Коллизии

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

Решается эта проблема обычно методом цепочек (separate chaining). Метод цепочек подразумевает хранение не единственной пары в бакете, а списка пар. Тогда время для нахождения нужной пары увеличивается до времени нахождения ячейки массива (константное) + времени нахождения ключа в списке. В качестве реализации списка обычно используется односвязный список.

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

Идеальная хэш-функция

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

Использование идеальной хэш-функции позволяет нам:

  • Добиться константного времени доступа в худшем случае, так как список больше не нужен
  • Оптимизировать расходы на память, позволяя не хранить ключ, так как нам больше нет необходимости его сравнивать при коллизиях

Load Factor

Load Factor — это отношение количества пар, помещенных в хэш-таблицу, к количеству бакетов (размера массива).

С возрастанием данной величины возрастает и количество коллизий, так как остается все меньше свободных бакетов (а при превышении значения в 1 свободных бакетов совсем не остается), а значит возрастает и среднее время доступа, переставая быть константым. Обычно, при невысоких требованиях доступности (reliability), решением является увеличение размера таблицы в 2 раза при достижении некоторого load factor. В таком случае нам также требуется перераспределить все пары.

Анализ

Проанализируем время выполнения операций и занимаемое хэш-таблицой место.

Место, занимаемое хэш-таблицей всегда зависит от количества записей (если оно будет всегда фиксированного размера, то деградирует скорость оперций), соответственно — O(n).

Средний случай — это когда load factor не высокий, коллизий мало и в среднем в каждом бакете находится только по одной паре

  • Поиск: O(1) — требуется обратиться только к ячейке массива, что всегда происходит за константное время
  • Вставка: O(1) — вставить новый элемент в пустой список
  • Обновление: O(1) — найти элемент в списке из 1 пары и обновить в нем значение
  • Удаление: O(1) — требуется обратиться к ячейке массива + удаление элемента из списка размером 1

Худший случай — это когда все операции маппинга идут только в один бакет из-за плохой хэш-функции. Тогда:

  • Поиск: O(N) — необходимо пройтись по всему списку
  • Вставка: O(1) — требуется обратиться к ячейке массива + вставить новый элемент в конец списка. Однако обычно вставка скрывает под собой также и обновление, поэтому и ее время можно оценить как O(N)
  • Обновление: O(N) — зависит от времени поиска пары
  • Удаление: O(1) — необходимо пройтись по всему списку

Добавить комментарий

Ваш адрес email не будет опубликован.