Структура данных — это определённый способ организации и хранения данных. Для решения каждой конкретной задачи нужно сначала определиться, в каких именно структурах будут лежать необходимые данные: от этого напрямую зависит и удобство разработки, и скорость работы вашей программы. В этой статье посмотрим на структуры данных, которые есть в JavaScript, и сложности операций над ними.

Массив

Массив — это структура данных, которая позволяет нам хранить совокупности элементов в определённом порядке и получать их по их положению внутри массива (индексу). Все мы с ним работали, все мы знаем, какие методы у него есть.

const contacts = []; // Например, какой-то массив из пользовательских контактов

contacts.push('+1 999 123 45 67'); // Куда мы что-то кладем в конец
contacts[1] = '+7 999 123 45 67'; // Или по конкретному месту

contacts.sort(); // Можем его сортировать (напоминаем, что сортировка изменяет исходный массив, а не создаёт новый)

const firstContact = contacts[0]; // Или получать что-то из массива

Но вы когда-нибудь задумывались, работают ли операции над массивами одинаково быстро? На самом деле, работая с массивом, мы часто используем его даже не как массив, а как структуры данных, работающие поверх него — очереди и стеки.

Массив как очередь

Очередь — это структура данных, «мимикрирующая» под очередь из реальной жизни: элементы попадают в конец массива-очереди и достаются из начала. Такие структуры в литературе обычно ещё называют First in first out (сокращенно FIFO) — первый зашёл, первый вышел.

Для работы над очередями нам необходимы два метода: push и shift.

Во фронтенде стоит использовать очереди, если вам важен порядок операций — например, последовательный показ оповещений пользователю, чтобы не выводить всё за раз. А «под капотом» JavaScript использует очереди для того, чтобы последовательно выполнять наши коллбеки из асинхронных операций.

const notifications = []; // Какая-то очередь для показа нотификаций пользователю

// <...>

notifications.push('Всё прошло просто восхитительно!') // Куда наш код кладёт какие-то оповещения
notifications.push('И все контакты сохранились!')
notifications.push('И вообще всё прекрасно!')

// <...>

const firstAlert = notifications.shift(); // А когда нужно, мы достаём самое старое оповещение...
showAlert(firstAlert); // ...и каким-либо образом показываем его пользователю

Давайте вспомним O-нотацию из первого модуля и оценим, насколько эти операции затратны. Метод push «под капотом» просто берёт переданный ему элемент и кладёт его в конец массива. Мы знаем, где у нас конец массива (нам не нужно его вычислять) и просто добавляем туда новый элемент. Это занимает всегда одинаковое количество операций, которое не зависит ни от длины массива, ни от передаваемого элемента. Перекладывая это в О-нотацию, получаем оценку в O(1), что в целом является лучшей из возможных оценок.

Можно подумать, что shift также работает за O(1): мы знаем, где массив начинается, и просто достаём оттуда элемент. Но на самом деле это не всё, что делает shift. Ему нужно не просто вернуть элемент из начала массива, но ещё и сдвинуть все остальные элементы массива на одно «место» ближе к началу массива. Например, если имеем массив [1, 2, 3, 4], вызов shift вернёт 1, а после этого в массиве останется [<ничего>, 2, 3, 4]. «Под капотом» shift сдвинет 2 в начало массива, получит [2, <ничего>, 3, 4], потом сдвинет в начало тройку и так далее до конца массива. Если мы добавим в этот массив один новый элемент, то shift будет работать на одну операцию больше, добавим n элементов — будет работать на n операций больше. Отсюда можем заключить, что сложность shift — O(n)

Забежим немного вперёд. Как и shift, unshift тоже отрабатывает за O(n) по схожей причине: нужно сначала подвинуть все элементы «вправо», к концу массива, а уже затем добавлять нужные элементы. Из этого следует довольно важный вывод: работа с началом массива гораздо трудозатратнее, чем работа с его концом. Поэтому если вам не принципиально, куда добавлять элементы, то добавляйте их в конец. Это на порядок эффективнее!

Массив как стек

Стек (англ. stack) — это структура данных, которая работает только с концом массива: кладёт элементы в его конец и достаёт их тоже из конца. Подобные структуры называются Last in first out (LIFO) — последний зашёл, первый вышел. Для функционирования массива как стека мы используем методы pop и push. Оба они, как следует из замечания выше, работают за O(1), а потому работа со стеком гораздо быстрее, чем работа с очередью.

Во фронтенде стек используется, например, на уровне браузера. При переходе между сайтами мы заполняем историю просмотра (кладём в стек просмотренные страницы), а при нажатии кнопки «Назад» достаём из стека последнюю страницу и переходим на неё. Такой же подход используется для собственных решений для undo-redo: отмены и повторения сделанных действий в вашем приложении. Такое решение используется в большинстве редакторов текста внутри браузера с форматированием, использующих contentEditable:

const changesHistory = []; // Заведём стек для сохранения состояний нашего редактора

// <...>

changesHistory.push(input.innerHTML); // Каждый раз, когда пользователь что-то вводит в наше поле, сохраняем HTML

// <...>

input.innerHTML = changesHistory.pop(); // А как только пользователь поймет, что ошибся, и нажмет Ctrl+Z — возьмём последнее сохранённое состояние и откатимся к нему

Другие методы работы с массивами

Один из самых популярных методов на массиве — это сортировка. На виды сортировок и их внутреннее устройство мы посмотрим дальше по курсу, а пока что просто запомним, что асимптотика сортировки массива O(n*logn) (чаще пишется как O(nlogn)). Откуда берётся эта оценка, вы точно узнаете, не переживайте! А если вы вдруг забыли, что такое логарифмы, то советуем вам освежить память — с ними мы ещё встретимся.

Ещё одним часто используемым оператором в JavaScript является spread — то самое троеточие, которое позволяет вам, например, объединять массивы вот так: [...array1, ...array2]. Выглядит и читается это очень приятно, но злоупотреблять этим оператором в больших массивах не стоит: он также итерируется по всем элементам массива, и в итоге вы получаете сложность O(n)! Использовать spread в циклах нужно только в крайнем случае, иначе получим сложность минимум O(n²).

Set

Set (множество) — это структура, которая чем-то похожа на массив и в это же время значительно от него отличается. Главное отличие Set в том, что в нём могут находиться только уникальные элементы. Возможно, вы уже встречали такой способ избавления от дубликатов: [...(new Set([1, 1, 1, 2]))] => [1, 2] (кстати, за сколько он работает?). Второе отличие — в нём отсутствует индексация: мы не сможем получить конкретный элемент в множестве, зная его положение в нём (честно говоря, мы и не то чтобы знаем). А ещё все операции (кроме перебора) работают на нём за O(1): и удаление, и вставка, и проверка на вхождение элемента. Почему так быстро?

Хеш-функция

Именно использование этого заклинания позволяет нам достичь таких скоростей. Если говорить простыми словами, это обычная функция, которая берёт любой элемент и получает на основе него число (хеш). Полученное число мы используем как индекс в массиве и по этому адресу кладём, получаем или проверяем элемент во множестве. Любая хеш-функция принимает только один элемент и работает за константное время, то есть имеет асимптотику O(1). Очень важный аспект хеш-функций в том, что разные элементы могут давать одинаковый результат в функции. Тогда, оперируя только хешами, мы можем подумать, что эти элементы равны. Получение таких ситуаций называется коллизиями. Чем больше у функции стойкость к коллизиям, тем она лучше. Не беспокойтесь, вероятность такой коллизии при использовании встроенных структур крайне мала.

Чаще всего на практике множества используются именно для быстрой проверки на вхождение в какой-то огромный список или для предотвращения появления дубликатов:

const cards = new Set(['6541', '2202']); // Например, заведём какой-то массив сохранённых пользователем банковских карточек

// <...>

cards.add('7483') // Добавляем новую карточку
cards.size() // Выдаст размер множества, то есть 3, потому что карточек внутри него три

// <...>

cards.add('2202') // А вот пользователь попытался сохранить ту же карту, что уже была сохранена...
cards.size() // ...но Set не допустил образование дубликата, поэтому его размер всё ещё 3.

Согласитесь, такая проверка на дубликаты и работает быстрее, и выглядит лучше, чем работа с массивом:

const newCard = '2202';

if (!cards.includes(newCard)) {
  cards.push(newCard);
}

Map

Map — это структура вида ключ-значение (key-value): грубо говоря, мы кладём в неё элементы по какому-то «названию» (ключу) и по нему же достаём. В случае Map ключом может являться как строка, так и любой другой произвольный примитив или даже объект. Map тоже использует хеш-функцию, как и Set, но высчитывает хеш не от значения, которое мы кладём в неё, а от ключа. Таким образом, скорость получения, удаления и проверки нахождения в Map также работает за O(1)!

За счёт этого Map хорошо использовать как кеш для каких-либо трудно или долго вычисляемых элементов. Например, если мы разрабатываем приложение для совершения платежей, пользователь может выбирать в форме оплаты одну из нескольких десятков привязанных карт. На фронтенде карты — это большие объекты, которые включают в себя id, номер и множество других полей. А в поле ввода как значение мы используем какую-нибудь строку, получаемую обработкой всех полей. Чтобы не пересчитывать эту строку каждый раз, когда мы что-то выбираем из списка, можно завести Map, где ключом будет огромный объект карты, а значением — наша строка. Тогда этот Map можно будет и переиспользовать в других местах, где нужны подобные вычисления. Посмотрим (и познакомимся с методами Map, если вы их ещё не видели) на примере:

const iconsCache = new Map(); // Заведём Map для хранения иконок платёжных систем из примера выше

function getIcon(system) {
  if (iconsCache.has(system)) { // Далее если в нашем коде нам понадобится получить иконку и мы её уже запрашивали, то...
    return iconsCache.get(system); // ...просто вернём её из кеша
  }

  const icon = await fetchIcon(system); // Иначе стартанём долгий асинхронный процесс получения иконки с сервера...

  iconsCache.set(system, icon); // ...положим нашу иконку в кеш, чтобы в следующий раз не ходить на сервер

  return icon;
}

Если иконок потенциально могут быть тысячи, Map не даст вам проиграть в скорости.

Объект

Как и в случае с массивами, вы, скорее всего, несчётное количество раз пользовались объектами. Объекты, как и Map, являются key-value структурами, но внутри устроены совершенно иначе. На самом деле они настолько различаются, что в разных ситуациях даже получение значения по ключу работает с разной асимптотикой. А ещё в обычных объектах ключами могут служить только строки. Это, кстати, тема одного из любимых вопросов многих интервьюеров на собеседованиях. Посмотрите на следующий код:

const a = {
  foo: 'bar'
};

const b = {
  bar: 'baz'
};

const someObject = {
  [a]: 1,
  [b]: 2,
}

console.log(someObject[a]) // ?

Что выведется в консоль? Если вы ответили 1, то попробуйте выполнить этот код самостоятельно.

Spread оператор на объектах, как и на массивах, выполняется за O(n), поэтому тут работает та же рекомендация не использовать его в циклах. Такое случается часто при сборке объектов! Взгляните на следующий пример: из массива вида [['size', 'm'], ['id', 3], ['color', 'white']] нам нужно получить объект

{
  size: 'm',
  id: 3,
  color: 'white',
}

Самое наивное и простое решение этой задачи, простая итерация:

const properties = [['size', 'm'], ['id', 3], ['color', 'white']];

const object = {};

for (const [key, value] of properties) {
  object[key] = value;
}

Если вы впервые видите объявление по типу const [key, value]..., почитайте про деструктуризацию.

Работает это решение за O(n) — мы просто итерируемся по массиву. Но если к задаче подпустить человека, который везде пытается добавить filter/map/reduce, то мы, скорее всего, получим:

const object = properties.reduce((accumulator, [key, value]) => ({
  ...accumulator,
  [key]: value,
}), {})

Этот код выглядит более заумным, но работает он гораздо хуже — за O(n²) — n итераций и n для spread оператора внутри каждой из них.

Это подводит ещё к одному важному выводу: не бойтесь, а даже старайтесь писать максимально простоватый код — чаще всего он работает лучше мудрёного! Помимо встроенных в JavaScript структур, мы можем реализовать свои собственные, используя уже доступные в качестве строительных блоков.