Пишем хеш-таблицу на джаваскрипт

Определение

Что такое Хеш таблица? Это структура данных, которая по ключу хранит какое-либо значение. Внимательный зритель может спросить в чем же отличие от Ассоциативного массива. Основное отличие в том, что это Хеш-таблица – это неупорядоченный ассоциативный массив. Ассоциативные Массивы это суперсет хеш-таблиц, те. делают все то же самое плюс, в дополнение к свойствам хеш-таблицы, они так же хранят порядок элементов и позволяют пройтись по ним циклом.

Зачем?

Очень быстрая структура данных в общем случае. Константа сложности на все операции О(1).

Игрушечная реализация

Следуя из определения нам нужно каким-то образом хранить отношение ключа и данных.

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

Номер это уже хорошо, но нам-бы хотелось использовать строки.

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

1. На вход хэш-функции подается сообщение произвольной длины;
2. На выходе хэш-функции формируется блок данных фиксированной длины;
3. Значения на выходе хэш-функции распределены по равномерному закону;
4. При изменении одного бита на входе хэш-функции существенно изменяется выход.

Мы же сегодня рассмотрим игрушечный пример.

В нормальном языке мы бы взяли массив фиксированной длины потому что он быстрее динамического, а мы хотим получить константное время. В Джаваскрипте же массивы динамические поэтому мы зафиксируем длину искусственно. Просто чтобы продемонстрировать как это все работает.

Хеш функция

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

Давайте ее немного улучшим. Используем другие свойства строки чтобы сгенерировать число. Например обратим все символы в их числовые коды и что-нибудь с ними сделаем.

Коллизии

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

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

На википедии доступно много вариантов реализации. Мы же рассмотрим один из простых и к тому же немного схитрим.

Для начала давайте подумаем, что можно сделать в таком случае?

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

Чтобы решить коллизию нам нужно как-то хранить все значения и уметь искать нужное. Для этого мы будем хранить не одно значение по ключу, а массив значений. И это именно тот момент где мы хитрим. Обычно мы не знаем наперед сколько коллизий у нас будет, поэтому в выделить массив нужного размера не можем и нам приходится использовать Связный Список. Я думаю, что для одного видео одной структуры данных достаточно поэтому давайте просто использовать массив потому что в Джаваскрипте массивы динамические, т.е. длина массива увеличивается если мы продолжаем добавлять новые элементы.

Вариант с динамическим массивом вообще вполне имеет право быть если верить википедии.

Вывод

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