В JavaScript объекты хранятся в виде пар ключ-значение. Это пример встроенной хеш-таблицы в самом языке. Если вы хотите настроить хеш-таблицу и создать свою собственную, вы можете это сделать. Хэш-таблицы могут быть реализованы в виде линейной или нелинейной структуры данных. В большинстве случаев они реализуются как линейная структура данных.
Прежде чем мы начнем с хеш-таблицы, давайте разберемся в вопросе ниже.
что такое ассоциативный массив, хэширование и коллизия?
Ассоциативные массивы — это объекты JS, которые хранят объекты как уникальные определяемые пользователем ключи. Когда сопоставление объектов происходит таким образом, оно называется "Хэширование". Хеширование всегда возвращает пары ключ-значение.
Конфликт – это когда два элемента сопоставляются с одним и тем же местом в памяти.
Обработка столкновений:
Столкновения могут быть обработаны следующими способами
Линейное зондирование:
Когда мы пытаемся добавить ключ в массив, который уже занят, мы продолжаем проверять хэш-таблицу, пока не будет найден пустой слот. Как только пустой слот найден, key вставляется в этот слот. Линейное зондирование — это тип открытой адресации.
Отдельная цепочка:
Мы можем хранить элементы отдельно, чтобы избежать коллизий, используя цепочку либо с массивами, либо со связанными списками.
Давайте посмотрим, как реализовать код для отдельного связывания с использованием массивов для создания конструктора, хеш-функции, которая вычисляет индекс ключа в таблице. , set(key,value), получение элемента на основе ключа и наконец возврат всех ключей в хэш-таблицу.
Вывод:
Наконец, поиск по ключу или значению и вставка элемента в хеш-таблицу занимает большое O(1). Производительность хеш-таблицы зависит от хэш-функции, размера таблицы и выбора метода обработки коллизий.
В этой статье мы рассмотрели серию структур данных JavaScript. Вот остальные статьи из этой серии, если хотите прочитать.
Другие связанные статьи:
Большая нотация О — что это за штука?
- Соединение точек — большая буква «О и структура массива данных»
- Соединение точек — большая буква «О и структура данных связанного списка»
- Соединяя точки — Big O и Trees Data Structure
- Соединяем точки — Big O и Stacks Data Structure
- Соединение точек — большое O и структура данных очереди
- Соединение точек — большая буква «О и структура графических данных»
- Эта статья: Соединение точек — большая буква О и структура данных хеш-таблицы
Надеюсь, вам понравилась серия статей о структуре данных JavaScript. Скоро я опубликую новые статьи. Оставайтесь с нами.
Спасибо за чтение этой статьи и, пожалуйста, подпишитесь на меня и поставьте 👏.
Ссылки:
Википедия, Алгоритмы Grokking, Шпаргалка Big O, Interview.io
