Работая над проблемами структуры данных и алгоритмов, важно находить эффективные решения, которые продолжали бы работать эффективно даже при увеличении набора данных. Это означает наличие хорошей временной сложности Big O, и для некоторых проблем один из способов сделать это - использовать Hash Maps.

Хэш-карта хранит пары ключ-значение в JavaScript. Хеш-карта может быть объектом Javascript или встроенным объектом Map JavaScript. В других языках тоже есть свои версии, например, в Python это словарь, а в Ruby - хеш, основная идея та же, но с использованием пар ключ-значение. Итак, как это может помочь улучшить наш Big O? В большинстве случаев поиск, вставка и удаление хэш-карты - это постоянное время Big O (1) (что является наилучшим возможным временем выполнения). Следует также сказать, что не самый распространенный худший случай для хэш-карты - это линейное время Big O (n) (что не страшно).

Где использовать хеш-карту? Работая с алгоритмами кодирования, вы заметите, что проблема заключается в хранении пар ключ-значение, из которых вы можете извлечь или выполнить поиск, чтобы найти ответ. Тогда, возможно, стоит попробовать использовать хеш-карту. Чтобы использовать практический пример, первый вопрос на Leetcode.com - это «Две суммы». Задача дает вам массив целых чисел и целевое целое число. Из этого массива, добавив два целых числа, нам может понадобиться целевое число и вернуть индекс двух чисел, и каждый вход имеет только одно решение.

Простой подход грубой силы заключался бы в создании вложенного цикла для перебора всех чисел (один цикл для одного числа и второго для следующего числа) в массиве и вычитания одного из чисел из целевого числа, чтобы проверить, не он равен другому числу. Написанный на JavaScript, это будет выглядеть так:

Вложенный цикл дает нам временную сложность квадратичного времени O (n²). В этом случае мы можем использовать хэш-карту, чтобы улучшить это. Нам нужен только один цикл, чтобы найти целевое число за вычетом числа, которое мы находимся в цикле, и искать это значение в хэш-карте (которая используется для хранения чисел в массиве как ключей и их индексов как ценности). Затем с помощью условного оператора найдите нужное значение и его индекс на карте. Это уменьшает нашу временную сложность до O (n) с одним циклом и вставкой / поиском нашей хеш-карты, равной O (1). Закодированный на JavaScript с использованием объекта в качестве хэш-карты будет выглядеть так:

Как я уже упоминал ранее, мы также можем использовать объект JavaScript Map с тем же эффектом, что и объект JavaScript в качестве карты. Нам просто нужно использовать правильный синтаксис и вызывать функции, которые идут с объектом Map has, get и set (их гораздо больше, это только три, которые мы используем). Таким образом, с использованием объекта карты, по сути, тот же код, что и выше, будет выглядеть так:

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

Работа над курсами Udemy Мастер-класс по алгоритмам JavaScript и структурам данных и Мастер-класс по программированию: структуры данных + алгоритмы помогла мне понять и использовать хэш-карты.

Дополнительные материалы на plainenglish.io