Хеширование - это отображение некоторого множества объектов в множество чисел. Хеширование позволяет унифицировать способ доступа к произвольным данным.
Применение хеширования:
- Хеш таблица, которая вычисляет хеш значение ключа для доступа к нужному бакету
- Шардирование, где по хеш значению ключа мы вычисляем нужный сервер/дб
- И другое
Содержание:
Хеш-таблица (Hash table, hash map) - это структура данных, имплементирующая АТД "Ассоциативный массив" и позволяющая хранить пары вида <ключ, значение>. В основе хеш-таблицы лежит хеширование.
Особенность хеш-таблицы в том, что в среднем случае она поддерживает доступ к ключу за константное время.
Ключевая идея хеш-таблицы заключается в двух вещах:
- Использование массива для хранения пар (bucket array)
- Хеширование
Элементы массива называются бакетами (bucket). Хеш-функция используется для распределения пар в массиве бакетов (bucket array).
Имея ключ, индекс бакета вычисляется следующим образом:
Последнее выражение, взятие хеша по модулю размера массива, требуется потому, что хеш функция может выдать значение за
пределами массива. Такое значение замапить невозможно, если только не выделить массив такого размера, что он покрыл бы
все возможные выходные значения хеш функции. Понятно, что выделять массив такого размера совершенно не эффективно,
поэтому самым тривиальным решением остается взять хеш по модулю
Таким образом, имея ключ и хеш-функцию, мы можем вычислить индекс для расположения пары в нужной ячейке массива бакетов и дальнейшего доступа к ней.
При использовании хеш функций обязательно возникают коллизии. Коллизия хеш-функции - это случай, когда для двух различных блоков данных мы получаем один и тот хеш или индекс. Это плохо, так как при попытке вставить новую пару, мы можем наткнуться на уже существующую.
Решается эта проблема разными способами. Но перед тем, как перейти к этим способам, нужно рассказать об открытом и закрытом хешировании.
Открытое хеширование (open hashing) - это когда элемент хранится не прямо в ячейке, указанном хеш значением, а в списке.
Также это называется Closed addressing - это когда адрес (location) элемента определяется полностью лишь одним хеш значением ключа.
Почему же эти два понятия так отличаются: в одном open, в другом closed? Дело в том, что open означает, что у нас нет строгих гарантий на что-либо, а closed наоборот - означает что строгие гарантии есть.
То есть, open hashing - потому что объекты на самом деле не хранятся в массиве напрямую, а хранятся они в списке. Но closed addressing потому, что адрес бакета определяется строго значением хеша.
Метод цепочек (separate chaining) - это вид открытого хеширования. Он подразумевает хранение не единственной пары в бакете, а списка пар. В качестве структуры данных обычно используется односвязный список, но может быть и Binary Search Tree, если элементов слишком много и линейный поиск может занять много времени.
При поиске значения мы находим нужный бакет, как и раньше, а затем просто проходимся по всем парам в списке и сравниваем
искомый ключ с ключом в каждой паре, т.е. нужно, чтобы была корректно определена операция equals. Как только нашли
ключ, возвращаем эту пару.
При вставке же новой пары с таким же индексом мы просто добавляем эту пару в конец списка.
Понятно, что время для нахождения нужной пары увеличивается до времени нахождения ячейки массива (константное) + времени нахождения ключа в списке.
Закрытое хеширование (closed hashing) - это парадигма разрешения коллизий, которая использует * probing* для нахождения следующей свободной ячейки массива.
Этот метод также известен как Open addressing, потому что здесь индекс бакета не определяется строго хеш значением, а зависит от данных в таблице. Но closed hashing потому, что мы не выходим за рамки хеш таблицы - все элементы напрямую хранятся в бакетах, а не списках.
Варианты разрешения коллизий типа closed hashing:
- Linear Probing
- Quadratic Probing
- Double Hashing
- и другие
Здесь можно почитать и о методе цепочек, и о других closed hashing методах разрешения коллизий https://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BB%D0%BB%D0%B8%D0%B7%D0%B8%D0%B9
Если случается коллизия, т.е. ячейка с индексом i занята, то мы ищем следующую ячейку массива следующим образом:
Такая последовательность перебора называется Probe sequence.
Однако, существует проблема: такой метод создает длинные последовательности занятых бакетов. Когда мы будем добавлять новые ключи, велик шанс, что мы попадем в одну из ячеек последовательности и еще более усугубим проблему, удлинив эту последовательность. Все это влечет за собой увеличение среднего времени поиска и вставки. Этот феномен называется Primary clustering.
Этот вариант обладает хорошей утилизацией кэша, но страдает от clustering. Поиск в таком варианте такой же - просто идем по последовательности и сравниваем искомый ключ с текущим.
Если случается коллизия, т.е. ячейка с индексом i занята, то мы ищем следующую ячейку массива следующим образом:
Такой способ оставляет большие свободные промежутки между занятыми ячейками и избегает primary clustering.
Однако, если два ключа мапятся в один и тот же индекс, то второй ключ пойдет по тем же самым шагам, что и первый ключ. Если это происходит слишком часто (из-за плохой хеш функции), то длинные последовательности все равно образуются и производительность падает. Да, в этом варианте сложнее попасть в индекс занятой последовательности, так как элементы идут не подряд, но это все равно может случиться. Этот феномен называется Secondary Clustering, и он является обобщением Primary Clustering.
Clustering происходит потому, что probe sequence не зависит от ключа - мы просто перебираем
Этот вариант не обладает такой хорошей утилизацией кеша, как Linear Probing, но и меньше страдает от clustering, то есть является чем-то средним между linear probing и double hashing.
Самый продвинутый вариант. В этом методе разрешения коллизий используется еще одна хеш функция для определения probe
sequence. Допустим, мы замапили ключ в индекс
Этот вариант совсем плох в плане утилизации кеша, но зато избегает как primary, так и secondary clustering.
- Максимально возможный Load Factor: open - бесконечный, closed - 1, потому что в closed hashing мы храним элементы напрямую в ячейках массива
- Размер внутреннего массива у Closed Hashing должен быть сильно больше, так как ключи лежат напрямую в массиве
- Утилизация кеша в closed hashing лучше, так как элементы лежат линейно в памяти
- Closed hashing работает лучше, если набор исходных элементов известен заранее
- Clustering отсутствует у обоих, если в closed hashing использовать double hashing
Lazy Deletion - это особая техника удаления ключей из таблицы, использующей open addressing. В этом способе удаление элемента происходит путем помечания ключа как удаленного, вместо того чтобы удалять его полностью. Тогда эти ячейки считаются как пустые при вставке и как занятые при поиске.
Проблема с этим способом такая, что когда количество удалений/вставок увеличивается, стоимость поиска увеличивается. Чтобы улучшить время, мы сделаем вот такой трюк: когда какой-нибудь элемент был найден при поиске, то этот элемент перемещается в самую первую встретившуюся в текущем probing sequence ячейку, которая была помечена как удаленная.
Весь смысл Lazy Deletion в том, чтобы при удалении не искать элемент, который можно переместить в освободившуюся ячейку, а делать это при поиске элемента, таким образом улучшая время удаления.
Load Factor - это отношение количества пар, помещенных в хеш-таблицу, к количеству бакетов внутреннего массива ( размеру массива).
С возрастанием данной величины возрастает и количество коллизий, так как остается все меньше свободных бакетов, а при превышении значения в 1 свободных бакетов совсем не остается, а значит возрастает и среднее время доступа, переставая быть константным. Обычно, при невысоких требованиях доступности (reliability), решением является увеличение размера таблицы в 2 раза при достижении некоторого load factor. В таком случае нам также требуется перераспределить все пары (рехешировать).
Проанализируем время выполнения операций и занимаемое хеш-таблицой место.
Место, занимаемое хеш-таблицей всегда зависит от количества записей - поэтому
Средний случай - это когда load factor не высокий, коллизий мало и в среднем в каждом бакете находится только по одной паре
-
Поиск:
$O(1)$ - требуется обратиться только к ячейке массива, что всегда происходит за константное время -
Вставка:
$O(1)$ - вставить новый элемент в пустой список -
Обновление:
$O(1)$ - найти элемент в списке из 1 пары и обновить в нем значение -
Удаление:
$O(1)$ - требуется обратиться к ячейке массива + удаление элемента из списка размером 1
Худший случай - это когда все элементы мапятся только в один бакет из-за плохой хеш-функции. Тогда:
-
Поиск:
$O(N)$ - необходимо пройтись по всему списку -
Вставка:
$O(1)$ - требуется обратиться к ячейке массива + вставить новый элемент в конец списка -
Обновление:
$O(N)$ - необходимо пройти по всему массиву за$O(n)$ + заменить значение в паре за$O(1)$ -
Удаление:
$O(1)$ - необходимо пройтись по всему списку + удалить элемент. Удаление в односвязном списке - это$O(1)$ , но если используется другая структура данных, нужно смотреть на ее время удаления. Однако, асимптотически операция удаления все равно будет работать за$O(n)$ , так как я еще не встречал такой структуры данных, удаление из которой заняло бы больше чем линейное время, а [поиск$O(n)$ + удаление$O(n)$ ]$= O(n)$
Когда набор значений, которые требуется замапить, известен заранее, мы можем использовать идеальную хеш-функцию.
Идеальная хеш-функция (Perfect Hash Function) - это такая хеш-функция, которая преобразует заранее известное статическое множество ключей в диапазон целых чисел без коллизий, т.е. один ключ соответствует только одному уникальному значению. А если количество результирующих значений такое же как и количество входящих ключей, такая функция называется минимальной идеальной хеш-функцией (minimal perfect hash function). С математической точки зрения такая функция является инъекцией (injection).
Использование идеальной хеш-функции позволяет нам:
- Добиться константного времени доступа в худшем случае, так как коллизий больше не возникает
- Оптимизировать расходы на память, позволяя не хранить ключ, так как нам больше нет необходимости сравнивать его при коллизиях, так как коллизий то больше и нет