4. Хеш-таблица (Hash table)
Структура данных, которая позволяет хранить пары ключ-значение и выполнять три операции над ними: добавление новой пары, поиск значение по ключу и удаление пары по ключу.
4.1 Структура хеш таблицы
HashTable
index
| data
| |
v v
┌───────────┬───────┐
| | |
├───────────┼───────┤
hash(key) = | hash code | key |
├───────────┼───────┤
| | |
└───────────┴───────┘
4.2 Хеш-функция
Хеш-функция должна превращать ключ из пары ключ-значение в индекс массива, в котором хранятся значения. Например, у нас есть массив длиной 5 элементов для хранения значений.
const array = new Array(5);
Теперь мы хотим положить в него значение с ключом 3. Можно реализовать хеш-функцию так, чтобы она возвращала то значение, которое она получила.
const hash = key => key;
У такого подхода есть проблема: в случае, если мы захотим положить в хеш-таблицу значение с ключом 7 — нам не удастся положить его в массив, потому что 7 больше длины массива.
В такой ситуации нам может помочь операция нахождения остатка от деления.
const hash = key => key % 5;
В качестве ключа может использоваться симоволы (например 'a'). В таком случае мы можем привести символ к числу, взяв его ASCII представление.
const hash = char => char.charCodeAt(0) % 5;
В таком случае индекс для вставки в массив будет равен 97 % 5 == 2.
Как быть со строками? Мы может сложить коды каждого из символов в строке и найти остаток от деления.
const hash = string => {
let result = 0;
for (let i = 0; i < string.length; i++) {
result += string.charCodeAt(i);
}
return result % 5;
};
Тогда индексом для ключа 'Hello world' будет hash('Hello world') == 4.
Так и работают хеш функции: для каждого ключа они вычисляют значение индекса в массиве. Проблема функции K mod N в том, что для двух разных ключей она может вернуть один и тот же индекс.
hash(3) == 3;
hash(13) == 3;
Такие ситуации называются коллизиями.
4.3 Разрешение коллизий в хеш-таблицах
4.3.1 Открытая адресация (Open addressing)
Сначала мы хотим добавить ключ 1 в хеш-таблицу. Хеш-функция K mod N вычисляет нам индекс 1.
┌────┬────┐
| 0 | |
├────┼────┤
---> | 1 | 1 |
├────┼────┤
| 2 | |
├────┼────┤
| 3 | |
├────┼────┤
| 4 | |
└────┴────┘
После этого мы хотим добавить ключ 11, но K mod N вычисляет нам такой же индекс. В такой ситуации мы начинаем итерирование по индексам в поисках свободного места — такой способ называется линейное пробирование.
┌────┬────┐
| 0 | |
├────┼────┤
| 1 | 1 |
├────┼────┤
---> | 2 | 11 |
├────┼────┤
| 3 | |
├────┼────┤
| 4 | |
└────┴────┘
Теперь мы хотим добавить ключ 22, K mod N вычисляет индекс 2, но там уже хранится другой ключ. Мы поступаем таким же образом: интерируемся в поисках свободного места.
┌────┬────┐
| 0 | |
├────┼────┤
| 1 | 1 |
├────┼────┤
| 2 | 11 |
├────┼────┤
---> | 3 | 22 |
├────┼────┤
| 4 | |
└────┴────┘
После этого мы хотим проверить, добавлен ли ключ 31 в нашу хеш-таблицу. K mod N вычисляет индекс 1. Мы смотрим на значение по этому индексу, но там лежит не 31, а 1. Достаточно ли этого, чтобы понять, что ключа 31 нет в таблице? Нет, нам нужно сделать еще две итерации до тех пор, пока мы не найдем свободное место. В этом проблема открытой адресации: чем больше заполенность хеш-таблицы, тем больше итераций надо сделать, чтобы найти нужный ключ.
Сложность удаления ключа при линейном пробировании так же зависит от заполненности таблицы. Для того, чтобы удаление не требовало большого количества интераций, удаленным элементам ставят специальный флаг. Итерирование не останавливается на элементах с таким флагом при добавлении и поиске. Такой подход не освобождает ячейки при удалении элементов, но не требует передобавления каждого добавленного элемента, следующего за удаленным.
4.3.2 Метод цепочек (Separate chaining)
При таком подходе в массиве хранятся не ключи, а связанные списки ключей. В случае коллизии хеш-функции новый ключ добавляется в тот список, который лежит по тому же индексу.
┌────┬────┐
| 0 | |
├────┼────┤ ┌────┬────┐ ┌────┬────┐
| 1 | ─┼─> | 1 | ─┼─> | 11 | X │
├────┼────┤ ├────┼────┤ └────┴────┘
| 2 | ─┼─> | 22 | X |
├────┼────┤ └────┴────┘
| 3 | |
├────┼────┤
| 4 | |
└────┴────┘
4.3.2.1 Добавление элемента в хеш-таблицу (add)
/**
* Добавление элемента в хеш-таблицу O(1)
* @param {number} key
* @param {*} value
*/
add(key) {
// Вычисление хеш-кода O(1)
const hashCode = this._hashFn(key);
// Доступ к списку по индексу, либо создание нового O(1)
this._array[hashCode] = this._array[hashCode] || new LinkedList();
// Добавление элемента в конец списка O(1)
this._array[hashCode].pushBack(key);
}
4.3.2.2 Поиск элемента по ключу (find)
/**
* Поиск элемента по ключу
* В лучшем случае -- O(1)
* В худшем случае -- O(n)
* @returns {boolean}
*/
find(key) {
// Вычисление хеш-кода O(1)
const hashCode = this._hashFn(key);
// Доступ к списку по индексу O(1)
const list = this._array[hashCode];
// Если списка нет -- возврат false O(1)
if (!list) {
return false;
}
// Поиск в списке по ключу
// В лучшем случае -- O(1)
// В худшем случае -- O(n)
return list.find(key);
}
4.3.2.3 Удаление элемента по ключу (remove)
/**
* Удаление элемента по ключу
* В лучшем случае -- O(1)
* В худшем случае -- O(n)
*/
remove(key) {
// Вычисление хеш-кода O(1)
const hashCode = this._hashFn(key);
// Доступ к списку по индексу O(1)
const list = this._array[hashCode];
// Если списка нет -- ничего делать не надо O(1)
if (!list) {
return;
}
// Удаление из списка по ключу
// В лучшем случае -- O(1)
// В худшем случае -- O(n)
list.erase(key);
}
4.4 Примеры использования
4.4.1 Реализация множества
Необходимо реализовать множество, над которым можно совершать три операции:
- Добавление элемента в множество за O(1)
- Удаление элемента из мнажества за O(1)
- Возврат случайного элемента из множества за O(1)