Реализация хеш-таблицы в JavaScript
Сегодня мы создадим нашу собственную реализацию структуры данных хеш-таблицы на JavaScript / TypeScript.
Что такое хеш-таблица?
Структура данных, используемая для хранения пар ключ-значение, к которой можно получить доступ в постоянное время (в основном).
Зачем использовать хеш-таблицу?
Хеш-таблицу можно использовать для решения проблем, когда вам нужно отслеживать различные переменные, не записывая их явно.
Приведем пример. Допустим, у вас есть следующая строка: «abgcddcccfmlk»
Теперь представьте, что вас просят убедиться, что в строке нет букв, повторяющихся более 3 раз.
Как бы ты это сделал?
Наивным ответом было бы использовать два вложенных цикла для сравнения каждой буквы с остальными одну за другой и убедиться, что буква не повторяется более 3 раз.
Хотя это решение работает, для выполнения требуется n² операций, где n равно размеру массива. Мы видим, как это решение может стать крайне неэффективным.
Теперь предположим, что у нас есть хеш-таблица, чтобы отслеживать, сколько раз повторяется каждая буква.
Наша хеш-таблица будет выглядеть примерно так
[ a: 1 ]
По мере того, как мы перебираем строку, мы будем обновлять все найденные значения и добавлять 1 к их соответствующему счетчику по мере продвижения. После одной итерации строки наша хеш-таблица будет выглядеть так прямо перед повторением последней буквы «c» в нашем массиве.
[ a: 1, b: 1, g: 1, c: 3, d: 2]
Мы видим, что если мы добавим 1 к c, она станет 4, что сделает нашу строку «недействительной». Мы можем просто остановиться на этом и вернуть false, не глядя на остальную часть массива, потому что мы знаем, что наша строка уже недействительна, поскольку «c» повторяется более 3 раз. Это займет не более n операций, что намного лучше, чем наше предыдущее решение.
Надеюсь, теперь вы понимаете, почему хеш-таблица может быть такой полезной для такого рода проблем, и все возможные варианты ее использования.
Теперь, когда мы лучше поняли, как работают хеш-таблицы на практике, давайте приступим к их реализации в JavaScript / TypeScript.
Примечание. Единственное различие между TypeScript и JavaScript - это объявление типов переменных. В приведенных ниже фрагментах кода код написан на TypeScript, но его можно легко превратить в javascript, удалив определения типов.
Например
//in typescript
var addOne(num: number): number {
return num++;
}
//in javascript
var addOne(num) {
return num++;
}
Не то чтобы мы избавились от этого, давайте копнемся!
Создание класса для нашей хеш-таблицы
Здесь мы видим, что у нашего класса есть два свойства. Размер и таблица. Наша хеш-таблица будет обычным массивом, а размер будет его длиной. Подробнее об этом позже
Определение размера нашей хеш-таблицы
Хеширующая функция всегда должна возвращать один и тот же вывод для определенного ввода. Наш результат не должен быть случайным.
Здесь мы перебираем нашу строку и превращаем каждый символ в его номер ASCII * 100. После этого мы используем оператор модуля (%), чтобы сгенерированный идентификатор соответствовал нашему диапазону (размеру нашего массива) ;
Это означает, что любой сгенерированный нами id будет числом от 0 до указанного нами значения размера;
Вставка и получение значений в нашей хеш-таблице
Чтобы вставить значение, мы просто хэшируем наш ключ и сохраняем его значение в таблице, используя id в качестве индекса.
Чтобы получить значение ключа, мы можем просто хешировать ключ, который хотим найти, и получить доступ к массиву, используя id в качестве индекса.
Но подождите секунду, что произойдет, если два разных ключа приведут к одному и тому же идентификатору.
Например, допустим, наш размер = 2;
Очень вероятно, что наша хеш-функция вернет 1 или 2.
Поэтому, если мы сохраняем значение с ключом «кошка», а другое с «собакой», наши значения потенциально могут быть перезаписаны, поскольку в нашем массиве есть только два пробела.
Когда два хеширования двух разных ключей приводят к одному и тому же идентификатору. У нас есть то, что мы называем столкновением.
Итак, как мы можем это исправить?
Есть разные способы решить эту проблему, но мы будем использовать связанный список, чтобы решить нашу «маленькую» проблему.
Чтобы реализовать это, нам нужно сжать связанный список внутри каждого индекса нашего массива внутри нашего конструктора. Нам также придется обновить наши методы insert () и get () следующим образом
Теперь мы успешно реализовали хеш-таблицу, которая устраняет конфликты с помощью связанных списков.
Это окончательный результат
И связанный список, используемый для этой реализации
Примечание. Если размер нашей хеш-таблицы слишком мал или если хеш-функция недостаточно хороша, наша хеш-таблица может ухудшить два очень больших связанных списка, что снизит общую производительность, полученную при использовании хеш-таблицы.
Это означает, что время доступа O (1) может уменьшиться до 0 (n);
Если вам понравился этот урок, не забудьте подписаться на меня, чтобы узнать больше о структурах данных и алгоритмах в будущем.
Это все на сегодня.
