Хеш-таблицы — это структура данных, которая позволяет создавать список пар значений. Вы можете затем извлекать определённое значение, используя ключ для этого значения, который вы предварительно поместили в таблицу.
Хеш-таблица преобразует ключ в целочисленный индекс с помощью хеш-функции, и индекс определяет, где хранить пару ключ/значение в памяти.
Как использовать хеш-таблицы с классами Object и Map в JavaScript
Наиболее распространённый пример хеш-таблицы в JavaScript — это тип данных Object, где вы можете связывать значения свойств объекта с ключами свойств.
В следующем примере ключу Nathan соответствует значение номера телефона "555-0182", а ключу Jane — значение "315-0322":
Однако тип Object в JavaScript — это особый вид реализации хеш-таблицы по двум причинам:
- Он имеет свойства, добавленные классом Object. Введённые вами ключи могут конфликтовать и перезаписывать свойства по умолчанию, унаследованные от класса.
- Размер хеш-таблицы не отслеживается. Вам нужно вручную подсчитывать, сколько свойств определено программистом, а не унаследовано от прототипа.
Например, прототип Object имеет метод hasOwnProperty(), который позволяет проверять, не унаследовано ли свойство:
JavaScript не блокирует попытку перезаписать метод hasOwnProperty(), что может привести к ошибке:
Для решения этих недостатков JavaScript создал другую реализацию структуры данных хеш-таблицы, которая называется Map.
Как и Object, Map позволяет хранить пары ключ-значение внутри структуры данных. Вот пример работы Map:
В отличие от типа Object, Map требует использования методов set() и get() для определения и извлечения пар ключ-значение, которые вы хотите добавить в структуру данных.
Также нельзя перезаписать унаследованные свойства Map. Например, следующий код пытался перезаписать значение свойства size на false:
Как видно из приведённого выше кода, вы не можете добавить новую запись в объект Map без использования метода set().
Структура данных Map также является итерируемой, что означает, что вы можете перебирать данные следующим образом:
Теперь, когда вы узнали, как JavaScript реализует хеш-таблицы в виде структур данных Object и Map, давайте посмотрим, как вы можете создать собственную реализацию хеш-таблицы.
Как реализовать структуру данных хеш-таблица в JavaScript
Хотя JavaScript уже имеет две реализации хеш-таблицы, написание своей собственной реализации часто является одним из популярных вопросов на собеседованиях по JavaScript.
Вы можете реализовать хеш-таблицу в JavaScript в три шага:
- Создайте класс HashTable с начальными свойствами table и size.
- Добавьте функцию hash(), чтобы преобразовывать ключи в индексы.
- Добавьте методы set() и get() для добавления и извлечения пар ключ/значение из таблицы.
Итак, начнем с создания класса HashTable. Приведенный ниже код создаст таблицу корзин размером 127:
Все ваши пары ключ/значение будут храниться внутри свойства table.
Как написать метод hash() Следующим шагом необходимо создать метод hash(), который будет принимать значение ключа и преобразовывать его в индекс.
Простой способ создания хеша — это суммировать коды ASCII символов в ключе, используя метод charCodeAt(), как показано ниже. Обратите внимание, что метод назван с _ в начале, чтобы указать, что он является приватным:
Но так как класс HashTable имеет только 127 корзин, это означает, что метод _hash() должен возвращать число от 0 до 127.
Чтобы убедиться, что значение хеша не превышает размер корзины, необходимо использовать оператор модуля:
Теперь, когда метод _hash() завершен, пришло время написать методы set() и get().
Как написать метод set()
Чтобы установить пару ключ/значение в вашей хеш-таблице, вам нужно написать метод set(), который принимает (ключ, значение) в качестве параметров:
Метод set() вызовет метод _hash(), чтобы получить индекс. Пара [ключ, значение] будет назначена таблице по указанному индексу. Затем свойство size будет увеличено на единицу.
Теперь, когда метод set() готов, давайте напишем метод get(), чтобы получить значение по ключу.
Как написать метод get() Чтобы получить определенное значение из хеш-таблицы, вам нужно написать метод get(), который принимает ключ в качестве параметра:
Метод вызовет метод _hash(), чтобы снова получить индекс таблицы. Вернуть значение, хранящееся в table[index].
Таким образом, метод get() вернет либо пару ключ/значение, либо undefined, если пара ключ/значение не хранится в указанном индексе.
Пока все идет хорошо. Теперь добавим еще один метод для удаления пары ключ/значение из хеш-таблицы.
Как написать метод remove() Чтобы удалить пару ключ/значение из хеш-таблицы, вам нужно написать метод remove(), который принимает ключ в качестве параметра:
Получите правильный индекс, используя метод _hash(). Проверьте, имеет ли table[index] истинное значение и больше ли его длина нуля. Присвойте неопределенное значение правильному индексу и уменьшите свойство size на единицу, если это так. Если нет, просто верните false.
Теперь у вас есть рабочий метод remove(). Давайте проверим, работает ли класс HashTable правильно.
Как протестировать реализацию хеш-таблицы Время протестировать реализацию хеш-таблицы. Вот полный код для реализации хеш-таблицы:
Чтобы протестировать класс HashTable, создайте новый экземпляр класса и установите несколько пар ключ/значение, как показано ниже. Пары ключ/значение ниже — это просто произвольные числовые значения, связанные с названиями стран без особого значения:
Затем попробуйте получить их с помощью метода get():
Наконец, попробуйте удалить одно из этих значений с помощью метода remove():
Хорошо, все методы работают, как ожидалось. Попробуем еще одно добавление с новым экземпляром HashTable и извлечем эти значения:
Ой! Похоже, у нас возникли проблемы. ?
Как справиться с коллизией индексов
Иногда хеш-функция в хеш-таблице может возвращать одно и то же число индекса. В приведенном выше тестовом примере строки "Spain" и "?" обе возвращают одно и то же хеш-значение, потому что число 507 является суммой их ASCII-кодов.
Одно и то же хеш-значение приведет к коллизии индекса, перезаписывая предыдущее значение новым.
На данный момент данные, хранящиеся в нашей реализации хеш-таблицы, выглядят следующим образом:
[
[ "Spain", 110],
[ "France", 100]
]Чтобы справиться с коллизией номера индекса, нужно хранить пары ключ/значение во втором массиве, чтобы конечный результат выглядел следующим образом:
[
[
[ "Spain", 110 ],
[ "?", 192 ]
],
[
["France", 100]
],
]Чтобы создать второй массив, нужно обновить метод set(), чтобы он:
- Проверял table[index] и перебирал значения массива.
- Если ключ в одном из массивов равен ключу, переданному методу, заменял значение в индексе 1 и прекращал выполнение с помощью оператора return.
- Если совпадающий ключ не найден, добавлял новый массив ключа и значения во второй массив.
- В противном случае инициализировал новый массив и добавлял пару ключ/значение в указанный индекс.
- При каждом вызове метода push() увеличивал свойство size на единицу.
Полный код метода set() будет следующим:
Далее обновите метод get(), чтобы он также проверял массив второго уровня с помощью цикла for и возвращал правильную пару ключ/значение:
Наконец, обновите метод remove(), чтобы он перебирал массив второго уровня и удалял массив с правильным значением ключа, используя метод splice():
Теперь ваш класс HashTable сможет избегать коллизий номеров индексов и хранить пары ключ/значение во втором уровне массива.
В качестве бонуса добавим метод display(), который будет отображать все пары ключ/значение, хранящиеся в хеш-таблице. Нужно использовать метод forEach() для перебора таблицы и метод map() для преобразования значений в строку, как показано ниже:
Вот полный код класса HashTable с применением избежания коллизий для вашего справочника:
Вы можете протестировать реализацию, создав новый экземпляр HashTable и выполняя вставку и удаление:
Теперь в экземпляре HashTable нет коллизий. Отличная работа!
Итак
В этом уроке вы узнали, что такое хэш-таблица и как JavaScript использует ее для создания структуры данных Object и Map.
Вы также узнали, как реализовать собственный класс HashTable, а также как предотвратить столкновение ключевых индексов Hash-таблицы с помощью техники цепочки.
Используя структуру данных Hash Table, вы сможете создать ассоциативный массив с быстрыми операциями поиска, вставки и удаления.
