Map против Set в JavaScript: выбор структуры данных

05.11.202124.12.2021 Editorial Team 2 комментария 12 996 просмотров

Spread the love

Перевод: Glad Chinda — JavaScript maps vs. sets: Choosing your data structure

Введение

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

Некоторые очень популярные языки программирования, такие как Java и Python, предоставляют множество полезных реализаций структур данных «из коробки», тогда как повсеместно распространенный язык программирования JavaScript кажется довольно скудным в этом отношении. Однако, как и большинство языков программирования, JavaScript поставляется с некоторыми очень простыми типами данных, такими как массивы, строки, объекты, set, map и т. д.

Коллекции основанные на ключах

До обновления спецификации ECMAScript 2015 (широко известной как ES6) JavaScript предоставлял объекты Array как единственное стандартное встроенная индексированная коллекция, хотя были и другие экзотические объекты, такие как arguments и объекты String, которые вели себя как массивы со специальной обработкой целых чисел, обычно называемые объектами, подобными массивам, но на самом деле они не являлись индексированными коллекциями.

Начиная с ES2015, в JavaScript было добавлено несколько новых стандартных встроенных типов, таких как:

Symbol
Promise
Proxy

Также был добавлен ряд объектов типизированных массивов, которые, как и массивы, сами являются индексированными коллекциями. В дополнение к этому в язык была добавлена новая категория, известная как коллекции с ключами, со следующими встроенными типами объектов:

Map
Set
WeakMap
WeakSet

Как следует из названия, каждый элемент (известный как запись) в коллекции с ключами может быть идентифицирован каким-либо ключом, так что ключи в коллекции различны — это означает, что каждый ключ соответствует точно одной запись в коллекции. Если вы знакомы с хэш-таблицами (hash tables), то, возможно, вы уже сделали вывод об их полезности здесь для обеспечения того, чтобы среднее время доступа было сублинейным по отношению к количеству элементов в коллекции.

В этом посте мы рассмотрим, как можно использовать объекты Map и Set для эффективного решения проблем связанных с обработкой данных. Прежде чем приступить к делу, давайте рассмотрим пример задачи.

Задача:

Дан массив целых чисел nums, верните true, если какой-либо элемент встречается в массиве хотя бы дважды, или верните false, если каждый элемент уникален.

Сделайте паузу и попробуйте решить эту проблему самостоятельно, прежде чем продолжить. Ответьте на вопрос если массив nums будет отсортирован, упростит ли это решение?

Вот пример решение проблемы:

function hasDuplicates(nums) { 
  // 1. Sort the array in-place (sorting makes it easier) 
  nums.sort((a, b) => a - b);

  if (nums.length > 1) { 
    // 2. Loop through the sorted array until a duplicate is found 
    for (let i = 1, len = nums.length; i < len; i++) { 
      // If a duplicate is found, return immediately 
      if (nums[i] == nums[i - 1]) return true; 
    } 
  }

  // 3. If it ever gets here, no duplicate was found 
  return false; 
}

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

Давайте проанализируем наше решение. Время работы вышеуказанного решения будет линейно расти по мере увеличения размера входного массива.

Решение также использует Array.prototype.sort для сортировки входного массива, изменяя в результате исходный входной массив. Следовательно, для сортировки не требуется дополнительной памяти.

Важно отметить, что если проблема требует, чтобы исходный порядок входного массива оставался неизменным, то перед использованием этого решения необходимо сделать копию входного массива. Это равносильно использованию дополнительной памяти, которая будет расти линейно по мере увеличения размера входного массива.

Теперь, рассмотрим приемлемо ли это решение?

Скорость работы алгоритма зависит от размера входных данных.
От размера данных так же зависят потребляемые вычислительные ресурсы, такие как доступная память и т.п.

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

Определение объектов Map

Резюмировать спецификацию ECMAScript 2015 Map объекты это:

Это набор пар ключ/значение, где и ключи, и значения могут быть произвольными значениями языка ECMAScript.
Это упорядоченная коллекция, что означает, что порядок вставки ее элементов имеет значение и соблюдается при повторении использование коллекции.
Ключи в коллекции являются разными или уникальными и могут встречаться только в одной паре ключ/значение.
Каждый ключ в коллекции может встречаться только один раз относительно алгоритма сравнения ECMAScript SameValueZero.

Это означает, что любое допустимое значение JavaScript — это примитивные значения (primitive values), так и ссылки на объекты, включая недопустимые значения, такие как NaN и undefined, — можно использовать в качестве ключа в коллекции объектов Map.

Что такое записи Map?

Каждая пара ключ/значение, содержащаяся в коллекции объектов Map, обычно называется объектом записи или просто записью. Объект записи обычно представляется с помощью двухэлементного массива — больше похожего на кортеж в большинстве других языков программирования — первый элемент которого является ключом, а второй элемент — значением.

Определение типа для общей записи объекта Map должно выглядеть следующим образом (в TypeScript):

type MapEntry<Key, Value> = [Key, Value];

Тем не менее, вы можете использовать синтаксис JavaScript, такой как destructuring assignment, для записи объекта Map, как если бы вы использовали массив, как показано в следующем примере цикла for … of:

/**
 * Iterating over entries of `Map` object using a 
 * `for...of` loop — assuming that `map` has been 
 * defined already as a `Map` object. 
 */
for (const [key, value] of map) { 
  console.log(key, value); 
}

Оба объекта Map и Set наследуют метод entry() от соответствующих объектов-прототипов конструкторов. Этот метод entries() возвращает итератор для всех записей, содержащихся в коллекции, в соответствии с порядком их вставки.

Однако для объектов Map итератор, возвращаемый методом entries(), также служит итератором по умолчанию для коллекции.

Создание объекта Map

На момент публикации этой статьи единственный способ создать объект Map — это вызвать функцию глобального конструктора Map. Функция конструктора должна быть вызвана с ключевым словом new — в противном случае будет выдано исключение TypeError.

Когда функция конструктора Map вызывается без аргументов, возвращается пустой объект Map размера 0.

// Throws a`TypeError` — when invoked without `new` keyword 
const throwTypeErrorMap = Map();

// Creates an empty `Map` object of 0 `size`
const mapA = new Map();

// Omitting the parentheses — when invoked without arguments
// Also creates an empty `Map` object of 0 `size`
const mapB = new Map;

console.log(mapA.size); // 0 
console.log(mapB.size); // 0

Функцию конструктора Map также можно вызвать с необязательным итеративным аргументом (iterable). Если используется этот аргумент то он должен:

правильно реализовать итеративный протокол (iterable protocol) — многие встроенные объекты JavaScript реализуют этот протокол, такие как Array, String и Set, а также Map
возвращать объект-итератор, который создает двухэлементный объект, подобный массиву, первый элемент которого будет использоваться в качестве ключа Map, а второй элемент — значение, которое нужно связать с этим ключом

Если итерируемый аргумент не соответствует этим двум требованиям, будет сгенерировано исключение TypeError — единственное исключение, когда итерируемый объект — это значение null или undefined, и в этом случае эффект будет таким же, как при вызове функции конструктора Map без каких-либо аргументов, и создается пустой объект Map размером 0.

Обратим внимание на второе указанное выше требование. Очевидно, что новый объект Map не может быть создан из строкового примитива, даже несмотря на то, что объекты String сами являются итериремыми объектами.

// Map from String — throws a `TypeError` 
const throwTypeErrorMap = new Map("programming");

Когда мы создаем новый объект Map из другого итеративного объекта, сначала создается пустой объект Map, а затем выполняются следующие шаги для каждого объекта записи, созданного объектом-итератором, который возвращается итератором:

Извлекается первый и второй элементы из объекта записи как ключ и значение соответственно
Проверяется, существует ли уже запись с ключом в коллекции объектов Map с помощью сравнения SameValueZero.
1. Если он существует, обновляется текущее значение записи до этого значения
2. Если он не существует, добавляется новая запись в конец коллекции объектов Map с этим ключом и значением
  
  const pairs = [[1, 3], [3, 3], [4, 2], [2, 2]];
  
  // (1) Map из Array или Set
  // Здесь set создается из массива pairs и
  // используется для создания map. Однако map так же
  // может быть создано напрямую из массива pairs.
  
  const mapA = new Map(new Set(pairs));
  console.log(mapA.size); // 4
  console.log(…mapA); // [1, 3] [3, 3] [4, 2] [2, 2]
  
  // (2) Map из Map
  // Новый map будет содержать все записи оригинального map
  // Однако, оба map будут разными объектами.
  
  const mapB = new Map(mapA);
  console.log(…mapA); // [1, 3] [3, 3] [4, 2] [2, 2]
  console.log(…mapB); // [1, 3] [3, 3] [4, 2] [2, 2]
  console.log(mapA === mapB); // false
  console.log(mapA.size === mapB.size); // true
  
  // (3) Map из Object
  // В ES6, есть метод Object.entries()
  // и он возвращает массив пар
  // ключ/значение для каждого элемента объекта.
  
  const mapC = new Map(Object.entries({
  language: “JavaScript”,
  hello: “world”
  }));
  console.log(mapC.size); // 2
  console.log(…mapC); // [“language”, “JavaScript”] [“hello”, “world”]

Теперь, когда мы можем создавать новые объекты Map, давайте продолжим исследовать их свойства и методы экземпляров.

`Свойства и методы экземпляра объекта Map`

Проверка размера

Мы уже несколько раз видели свойство size в действии. Как следует из названия, size возвращает количество записей в объекте Map.

Возможно, вам будет интересно узнать, что свойство size является свойством доступа, а не свойством данных. Кроме того, у него есть только функция доступа get, и не функция set. По этой причине его значение нельзя изменить с помощью операции присваивания.

Всякий раз, когда вы обращаетесь к свойству size объекта Map, будет вызываться его функция доступа get, которая в основном подсчитывает и возвращает количество элементов (записей), находящихся в настоящее время в объекте Map.

Ищем ключ

Есть несколько случаев, когда достаточно знать, присутствует ли запись с определенным ключом в объекте Map. Каждый объект Map изначально имеет метод has(), который можно вызвать, чтобы проверить, присутствует ли запись с указанным ключом в объекте Map. Метод has() возвращает логическое значение — true, если указанный ключ присутствует, и false в противном случае.

const M = new Map(Object.entries({ 
  language: "JavaScript", 
  hello: "world" 
}));

console.log(M.has("hello")); // true 
console.log(M.has("Hello")); // false 
console.log(M.has("language")); // true 
console.log(M.has("world")); // false

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

Когда метод get() вызывается с ключом, для которого не существует записи, он возвращает значение undefined.

const M = new Map(Object.entries({ 
  language: "JavaScript", 
  hello: "world" 
}));

console.log(M.get("hello")); // "world" 
console.log(M.get("Hello")); // undefined 
console.log(M.get("language")); // "JavaScript" 
console.log(M.get("world")); // undefined

Хотя метод get() возвращает undefined для несуществующих ключей, на него не следует полагаться при проверке существования ключа в коллекции Map, поскольку также возможно, что ключ в коллекции имеет значение undefined.

Самый точный способ определить наличие ключа в коллекции — использовать метод has().

Добавление, обновление и удаление записей

Возможность добавлять, обновлять или удалять одну или несколько записей из объекта Map очень важна, и каждый объект Map имеет методы set(), delete() и clear().

Метод set() принимает значение JavaScript в качестве аргумента и добавляет это значение в конец объекта Map, если его еще нет. Если указанное значение уже есть в объекте Map, оно игнорируется.

Метод add() возвращает тот же объект Map с добавленным значением, что позволяет использовать цепочку методов или процесс одновременного вызова нескольких вызовов add().

С другой стороны, метод delete() удалит запись, связанную с указанным ключом, из объекта Map — при условии, что такая запись есть в объекте Map. Если запись действительно удаляется из объекта Map в результате этой операции удаления, она возвращает true; в противном случае возвращается false.

В некоторых случаях может быть полезно полностью удалить все записи из объекта Map. Хотя это может быть достигнуто путем выполнения нескольких вызовов delete() объекта Map, очевидно, что это будет иметь больше смысла, если это будет сделано за один вызов метода.

Именно это и делает метод clear(). Вызов метода clear() очищает объект Map и возвращает значение undefined.

// Convert object to map 
const M = new Map(Object.entries({ 
  language: "JavaScript" 
}));

console.log(M.size); // 1 
console.log(...M); // ["language", "JavaScript"]

// (1) Add and update some map entries 
M.set("year", 1991); 
M.set("language", "Python");

console.log(M.size); // 2 
console.log(...M); // \["language", "Python"\] ["year", 1991]

// (2) Add or update several values at once (using chaining) 
M.set("version", 3) 
  .set("year", 2000) 
  .set("version", "2.0");

console.log(M.size); // 3 
console.log(...M); // \["language", "Python"\] ["year", 2000] ["version", "2.0"]

// Delete some entries from the map 
console.log(M.delete("Year")); // false 
console.log(M.delete("year")); // true 
console.log(M.delete("year")); // false 
console.log(M.delete("version")); // true

console.log(M.size); // 1 
console.log(...M); // ["language", "JavaScript"]

// Empty the map 
M.clear();

console.log(M.size); // 0

Итерация коллекции

Еще одна вещь, которую мы можем захотеть сделать с объектом Map, — это просмотреть ключи, значения или записи, которые в нем находятся.

Вы можете перебирать каждую запись в объекте Map (в порядке вставки) с помощью цикла for … of. Это связано с тем, что каждая итерация имеет метод Symbol.iterator(), который возвращает свой итератор по умолчанию, который отвечает за создание последовательности значений для цикла.

Помимо цикла for … of, та же последовательность значений, возвращаемая итератором по умолчанию, является тем, на чем основаны оператор spread(…), оператор yield * и destructuring assignment.

Мы уже упоминали метод entries(), который возвращает итератор для всех записей в объекте Map в соответствии с порядком их вставки. Как указывалось ранее, итератор, возвращаемый методом entry(), также служит итератором по умолчанию для объекта Map.

Тем не менее, два цикла for … of, показанные в следующем фрагменте кода, одинаковы и будут давать точно такую же последовательность значений:

const M = new Map([[1, 3], [3, 3], [4, 2], [2, 2]]);

// (a) Iteration using the default iterator ([Symbol.iterator]) 
for (const [key, value] of M) { 
  console.log(key, value);
}

// (b) Iteration using the `entries()` iterator 
for (const [key, value] of M.entries()) { 
  console.log(key, value); 
}

Важно отметить, что итеративный объект может предоставлять другие итераторы помимо итератора по умолчанию, предоставляемого его методом [Symbol.iterator]. Это верно для большинства встроенных итераций в JavaScript, включая объекты Map.

Фактически, каждый объект Map изначально имеет три метода, которые возвращают итераторы, а именно:

entries()
keys()
values()

Метод keys(), как следует из названия, возвращает итератор, который выдает ключи, связанные с каждой записью объекта Map (в порядке вставки). Метод values() возвращает итератор, который возвращает значения, связанные с каждой записью объекта Map.

Следующий фрагмент кода демонстрирует несколько способов использования итеративного поведения объекта Map для доступа к значениям или ключам каждого элемента в нем.

const M = new Map([[1, 3], [3, 3], [4, 2], [2, 2]]);

// Using the spread operator (...) to pass values 
// in the Map object as function arguments. 
console.log(...M.values()); // 3 3 2 2

// Using the spread operator in building an array 
// with the unique keys of the Map object. 
const arr = [...M.keys()];

console.log(arr); // [1, 3, 4, 2] 
console.log(arr[0]); // 1 
console.log(arr[3]); // 2 
console.log(arr.length); // 4

// Using destructuring assignment with a `Map` object 
// to extract the first, second and remaining keys. 
const [first, second, ...remainingKeys] = M.keys();

console.log(first); // 1 
console.log(second); // 3 
console.log(remainingKeys); // [4, 2] 
console.log(remainingKeys.length); // 2

// Iteration using a for...of loop 
// to read all the keys in the collection. 
for (const key of M.keys()) { 
  console.log(key); 
}

// 1 
// 3 
// 4 
// 2

Итерация объектов Map с помощью метода forEach()

Мы рассмотрели несколько способов перебора объекта Map. Однако остается еще один очень полезный метод итерации — метод forEach().

Как и в случае с массивами, метод forEach() объекта Map принимает функцию обратного вызова в качестве своего первого аргумента, который запускается для каждой записи объекта Map. Метод forEach() также принимает необязательный второй аргумент, который представляет значение this, которое будет использоваться при выполнении функции обратного вызова.

Функция обратного вызова forEach() вызывается с тремя аргументами для каждой записи объекта Map:

Первый аргумент — это значение, связанное с текущей записью в итерации.
Второй аргумент — это ключ, связанный с текущей записью в итерации.
Третий аргумент — это сам объект Map.

const M = new Map([[1, 4], [3, 5], [4, 0], [2, 2]]);
M.forEach(function _callback(value, key, map) {
   console.log([...map]);
   const replacement = this[value];
   if (replacement) map.set(key, replacement);
   else if (Number.isInteger(value)) map.delete(key);
}, "hello");

console.log([...M]);

// [[1, 4], [3, 5], [4, 0], [2, 2]]
// [[1, "o"], [3, 5], [4, 0], [2, 2]]
// [[1, "o"], [4, 0], [2, 2]]
// [[1, "o"], [4, "h"], [2, 2]]
// [[1, "o"], [4, "h"], [2, "l"]]

Для ясности, вызов метода forEach() в предыдущем фрагменте кода приводит к следующим вызовам _callback():

_callback.call("hello", 1, 4, M); 
_callback.call("hello", 3, 5, M); 
_callback.call("hello", 4, 0, M); 
_callback.call("hello", 2, 2, M);

Что такое объект Set?

Объект Set — это упорядоченный набор уникальных значений.

Для каждого объекта Set справедливо следующие утверждение:

Это упорядоченная коллекция: порядок размещения важен
Значения в коллекции являются различными или уникальными: каждое значение может встречаться в коллекции только один раз относительно алгоритма сравнения ECMAScript SameValueZero.

В коллекции может содержаться любое допустимое значение JavaScript — как примитивные значения, так и ссылки на объекты, включая недопустимые значения, такие как NaN и undefined.

Maps против Sets в JavaScript

Поскольку мы уже рассмотрели объекты Map в предыдущем разделе, давайте посмотрим, как они сравниваются с объектами Set, прежде чем продолжить.

Set	Map
Одномерные коллекции: они хранят только уникальные значения	Двумерные коллекции: они хранят записи пар ключ/значение, и каждый ключ уникален в коллекции
И ключ, и значение указывают на одно и то же значение или ссылку для каждой записи	И ключ, и значение указывают на одно и то же значение или ссылку для каждой записи
Итератор по умолчанию ([Symbol.iterator]) объекта Set — это тот, который возвращается из его метода values ().	Итератор по умолчанию получается из метода entries()
Нет методов set () и get (). Есть метод add ()	Есть методы set () и get ()

Создание объекта Set

Как и в случае с объектами Map, единственный способ создать объект Set — это вызвать функцию глобального конструктора Set. Функция конструктора должна быть вызвана с ключевым словом new — в противном случае будет выдано исключение TypeError. Когда функция конструктора Set вызывается без аргументов, возвращается пустой объект Set размером 0.

// Throws a `TypeError` — when invoked without `new` keyword 
const throwTypeErrorSet = Set();

// Creates an empty `Set` object of 0 `size` 
const setA = new Set();

// Omitting the parentheses — when invoked without arguments 
// Also creates an empty `Set` object of 0 `size`
const setB = new Set;

console.log(setA.size); // 0 
console.log(setB.size); // 0

Функцию конструктора Set также можно вызвать с необязательным итерируемым аргументом. Если указан, итерируемый аргумент то он должен быть объектом JavaScript, который должным образом реализует итеративный протокол. Многие встроенные объекты JavaScript реализуют этот протокол, такие как Array, String и Map, а также Set, что означает, что все они являются допустимыми объектами и могут быть переданы в функцию конструктора Set в качестве итеративного аргумента.

Если итерируемый объект имеет значение null или undefined, тогда эффект будет таким же, как и при вызове функции конструктора Set без аргументов — будет создан пустой объект Set размером 0. В противном случае для любого другого итеративного значения, которое не реализует итеративный протокол должным образом, будет выдано исключение TypeError.

В отличие от объектов Map, создание нового объекта Set из другого итеративного объекта имеет эффект устранения дублирования, т. е. устранения избыточных повторяющихся значений, полученных внутренним итератором итерационного объекта. Это связано с одним важным атрибутом объекта Set, который состоит в том, что он должен содержать только отдельные дискретные значения.

// (1) Set from String 
// Set contains all the unique characters of the string 
const testString = "programming"; 
const uniqueChars = new Set(testString);

console.log(testString.length); // 11 
console.log(uniqueChars.size); // 8 
console.log(...uniqueChars); // p r o g a m i n

// (2) Set from Array 
// Set contains all the distinct elements of the array 
const integers = [1,1,1,3,3,4,3,2,4,2]; 
const distinctIntegers = new Set(integers);

console.log(integers.length); // 10 
console.log(distinctIntegers.size); // 4 
console.log(...distinctIntegers); // 1 3 4 2

// (3) Set from Set 
// New set contains all the items of the original set 
// However, both sets are entirely different objects. 
// Think of it as creating a clone of a set. 
const setA = new Set([1,1,1,3,3,4,3,2,4,2]); 
const setB = new Set(setA);

console.log(...setA); // 1 3 4 2 
console.log(...setB); // 1 3 4 2 
console.log(setA === setB); // false 
console.log(setA.size === setB.size); // true

Давайте еще раз рассмотрим нашу предыдущую задачу и воспользуемся тем, что мы узнали о объектах Set. На этот раз мы создадим новый объект Set из массива nums, содержащий только отдельные целые числа (без дубликатов). Затем мы можем определить, содержит ли массив nums дубликаты, сравнив размер объекта Set с длиной массива nums.

Вот как выглядит новое решение:

function hasDuplicates(nums) { 

  // Create a new set from `nums` containing only its distinct 
  // integers (i.e de-duplicate the `nums` array).
 
  const distinct = new Set(nums);

  // If the size of the distinct set matches the length of the 
  // nums array, then there are no duplicates, and vice-versa. 

  return distinct.size != nums.length; 
}

Используя объект Set, мы смогли реализовать решение, время работы которого гарантированно растет линейно с размером входного массива, даже если для его работы потребуется дополнительная память. Когда дело доходит до хранения уникальных элементов в памяти, набор элементов с дубликатами будет занимать меньше места, чем один без дубликатов.

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

Свойства и методы объекта Set

Проверка размера

Как и в случае с объектами Map, свойство size возвращает количество значений в объекте Set в любой момент времени. Опять же, свойство size объекта Set.prototype является свойством доступа, а не свойством данных.

Set также имеет только функцию доступа get, а не функцию доступа set — следовательно, ее нельзя переопределить с помощью операции присваивания.

Всякий раз, когда вы обращаетесь к свойству size объекта Set, будет вызываться его функция доступа get, которая будет подсчитывать и возвращать количество элементов (значений), которые в настоящее время находятся в объекте Set.

Проверка наличия значения

Каждый объект Set изначально будет иметь метод has(), который может быть вызван для подтверждения того, присутствует ли элемент с указанным значением в объекте Set. Как и в случае с объектами Map, метод has() возвращает логическое значение — true, если указанное значение присутствует, и false в противном случае.

const uniqueChars = new Set("programming");

console.log(...uniqueChars); // p r o g a m i n

console.log(uniqueChars.has("p")); // true 
console.log(uniqueChars.has("A")); // false 
console.log(uniqueChars.has("a")); // true 
console.log(uniqueChars.has("t")); // false

Поскольку объекты Set одномерны (хранят только уникальные значения), для них нецелесообразно иметь метод get(), в отличие от объектов Map. В результате объект Set.prototype не определяет метод get ().

Добавление и удаление значений

Очень важно иметь возможность добавлять или удалять одно или несколько значений из объекта Set, и каждый объект Set изначально будет иметь методы add(), delete() и clear().

Метод add() принимает значение JavaScript в качестве аргумента и добавляет это значение в конец объекта Set, при условии, что его еще нет в объекте Set. Если указанное значение уже есть в объекте Set, оно игнорируется.

Метод add() возвращает тот же объект Set с добавленным значением, что позволяет использовать цепочку методов или знакомый процесс одновременного вызова нескольких вызовов add().

Как и в случае с объектами Map, метод delete() объекта Set удалит элемент, связанный с указанным значением из объекта Set, при условии, что такой элемент присутствует в объекте Set. Если элемент действительно удаляется из объекта Set в результате этой операции удаления, он возвращает true; в противном случае возвращается false.

Кроме того, вызов метода clear() очищает объект Set и возвращает значение undefined.

// Create new set of integers 
const integers = new Set([1,1,1,3,3,4,3,2,4,2]);

console.log(integers.size); // 4 
console.log(...integers); // 1 3 4 2

// Add some values to the set 
integers.add(5); 
integers.add(1);

console.log(integers.size); // 5 
console.log(...integers); // 1 3 4 2 5

// Add several values at once (using chaining) 
integers.add(7).add(2).add(9);

console.log(integers.size); // 7 
console.log(...integers); // 1 3 4 2 5 7 9

// Delete some values from the set 
console.log(integers.delete(3)); // true 
console.log(integers.delete(8)); // false 
console.log(integers.delete(3)); // false 
console.log(integers.delete(1)); // true

console.log(integers.size); // 5 
console.log(...integers); // 4 2 5 7 9

// Empty the set 
integers.clear();

console.log(integers.size); // 0

Теперь, когда мы узнали еще несколько вещей, которые можно делать с объектами Set, давайте вернемся к нашему предыдущему решению.

Внимательное изучение нашего предыдущего решения покажет, что оно делает слишком много. Оно всегда рассматривает каждое целое число во входном массиве, добавляя их к объекту Set (точно так же, как если бы мы многократно использовали метод add()), а затем проверяет его размер, который подсчитывает и возвращает количество элементов в объекте Set, просматривая каждый элемент.

Проблема с этим решением в том, что оно не консервативно. Вполне возможно, что повторяющееся целое число может быть обнаружено путем рассмотрения первых нескольких целых чисел в массиве, и поэтому рассмотрение оставшихся целых чисел в массиве станет излишним.

Чтобы оптимизировать это решение, мы можем решить не добавлять целые числа к объекту Set и продолжать только до тех пор, пока мы не встретим целое число, которое уже было добавлено к объекту Set.

Вот как выглядит оптимизированное решение:

function hasDuplicates(nums) {

  // 1. Create an empty set to hold distinct integers
  const distinct = new Set();

  // 2. Loop through the integers until a duplicate is found
  for (const int of nums) {

    // 2a. If a duplicate is found, return immediately
    if (distinct.has(int)) return true;

    // 2b. Otherwise, add the integer to the distinct set
    distinct.add(int);
  }

  // 3. If it ever gets here, no duplicate was found
  return false;
}

Итерация коллекций с ключами

Часто необходимо иметь представление о значениях, содержащихся в объекте Set. Это достижимо с массивами или индексированными коллекциями — следовательно, мы можем легко получить доступ к элементу массива (arr) по некоторому индексу (i), используя обозначение скобок доступа к свойствам (arr [i]).

К сожалению, этот вид доступа к элементам напрямую невозможен с объектами Set(), потому что объекты Set являются коллекциями с ключами.

Однако, как и в случае с массивами и другими итерациями, вы можете перебирать значения для каждого элемента в объекте Set (в порядке вставки), используя цикл for … of, или можно использовать последовательность значений, которую он создает с оператором spread (…), оператором yield * или destructuring assignment .

Следующий фрагмент кода демонстрирует несколько способов использования итеративного поведения объекта Set для доступа к значениям каждого элемента в нем.

const integers = new Set([1,1,1,3,3,4,3,2,4,2]);

// Using the spread operator (...) to pass values
// in the Set object as function arguments.
console.log(...integers); // 1 3 4 2

// Using the spread operator in building an array
// with the unique values from the Set object.
const arr = [...integers];

console.log(arr); // [1, 3, 4, 2]
console.log(arr[0]); // 1
console.log(arr[3]); // 2
console.log(arr.length); // 4

// Using destructuring assignment with a `Set` object
const [first, second, ...remainingIntegers] = integers;

console.log(first); // 1
console.log(second); // 3
console.log(remainingIntegers); // [4, 2]
console.log(remainingIntegers.length); // 2

// Iteration using a `for...of` loop
for (const integer of integers) {
  console.log(integer);
}

// 1
// 3
// 4
// 2

Как и в случае с объектами Map, каждый объект Set изначально имеет три метода, которые возвращают итераторы — values(), keys() и entries().

Метод values(), как следует из названия, возвращает новый итератор, который возвращает значения для каждого элемента в объекте Set (в порядке вставки). Итератор, возвращаемый методом values(), возвращает ту же последовательность значений, что и итератор по умолчанию, возвращаемый методом [Symbol.iterator].

В целях итерации метод keys() объекта Set ведет себя точно так же, как метод values(), и их можно использовать взаимозаменяемо. Фактически, значения, ключи и свойства [Symbol.iterator] объекта Set изначально указывают на одно и то же значение (функцию). Следовательно, следующие циклы for … of будут регистрировать точно такую же последовательность значений.

const integers = new Set([1,1,1,3,3,4,3,2,4,2]);

// (a) Iteration using the default iterator (`[Symbol.iterator]`)
for (const integer of integers) {
  console.log(integer);
}

// (b) Iteration using the `values()` iterator
for (const integer of integers.values()) {
  console.log(integer);
}

// (c) Iteration using the `keys()` iterator
for (const integer of integers.keys()) {
  console.log(integer);
}

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

function union(setA, setB) {
  const setUnion = new Set(setA);

  for (const value of setB) {
    setUnion.add(value);
  }

  return setUnion;
}

function intersection(setA, setB) { 
  const setIntersection = new Set();

  for (const value of setB) {
    if (setA.has(value)) {
      setIntersection.add(value);
    }
  }

  return setIntersection;
}

Как и в случае с объектами Map, объекты Set также имеют метод forEach() с аналогичной сигнатурой вызова. Однако, чтобы учесть одномерный характер объектов Set, функция обратного вызова forEach () вызывается с тремя аргументами:

Первый аргумент — это значение текущего элемента в итерации.
Второй аргумент всегда совпадает с первым аргументом
Третий аргумент — это сам объект Set

const S = new Set([1,1,1,3,3,4,3,2,4,2]);

S.forEach(function _callback(value, _, set) {
   console.log([...set]);
   const replacement = this[value];
   if (replacement) set.add(${value}${replacement});
   if (Number.isInteger(value)) set.delete(value);
}, "hello");

// [1, 3, 4, 2]
// [3, 4, 2, '1e']
// [4, 2, '1e', '3l']
// [2, '1e', '3l', '4o']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']
// ['1e', '3l', '4o', '2l']

console.log(...S); // 1e 3l 4o 2l

Для ясности, вызов метода forEach() в предыдущем фрагменте кода приводит к следующим вызовам _callback():

_callback.call("hello", 1, 1, S);
_callback.call("hello", 3, 3, S);
_callback.call("hello", 4, 4, S);
_callback.call("hello", 2, 2, S);
_callback.call("hello", '1e', '1e', S);
_callback.call("hello", '3l', '3l', S);
_callback.call("hello", '4o', '4o', S);
_callback.call("hello", '2l', '2l', S);

Случайное undefined — что это значит?

Когда функция конструктора Set вызывается без аргументов, вы уже знаете, что она создает пустой объект Set. Однако этого нельзя сказать о методе add().

Когда метод add() объекта Set вызывается без аргументов, он фактически добавляет в коллекцию элемент со значением undefined, если он еще не существует.

Другими словами, для данного Set объект S функция S.add () в точности совпадает с S.add (undefined). Это то, что я хотел бы назвать случайным undefined, потому что это может быть не преднамеренно.

Возможно, вы уже предположили поведение методов has() и delete(), когда они вызываются без каких-либо аргументов. Как и в случае с методом add(), вызов этих методов без аргументов аналогичен их вызову с undefined в качестве первого аргумента. Следовательно, для данного объекта Set S, S.has() проверяет, существует ли undefined как значение в объекте Set, а S.delete() удаляет значение undefined из коллекции, если оно существует.

// Creates an empty set object 
const S = new Set();

// Add some items to the set object 
S.add(5); 
S.add("hello"); console.log(...S); // 5 'hello'

// Adds undefined to the set object 
S.add(); console.log(...S); // 5 'hello' undefined

console.log(S.has(5)); // true 
console.log(S.has("world")); // false

// Logs `true` because `undefined` exists in the set 
console.log(S.has()); // true

// Logs `true` because `undefined` was removed from the set 
console.log(S.delete()); // true

// Logs `false` because `undefined` does not exist in the set 
console.log(S.has()); // false

Таким образом, всегда обязательно вызывайте методы add(), delete() и has() объекта Set как минимум с одним аргументом, чтобы избежать случайного значения undefined.

Удаление дубликатов из объектов Set

Прежде чем мы закончим этот раздел, посвященный объектам JavaScript Set, давайте посмотрим, как мы можем изменить версию нашей исходной задачи, используя все, что мы узнали.

Дан массив целых чисел nums, верните количество элементов, которые встречаются в массиве не менее двух раз, или верните 0, если каждый элемент уникален.

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

Вот рабочее решение задачи:

function countDuplicates(nums) { 
  // Create an empty set for distinct integers 
  // (i.e integers appearing only once) 
  const distinct = new Set();

  // Create an empty set for duplicate integers 
  const duplicates = new Set();

  // Create a variable to keep track of the duplicates count 
  let count = 0;

  // Loop through the integers while counting duplicates 
  for (const int of nums) { 
    // If duplicate integer is found (it has already been counted), 
    // continue with the iteration to the next integer. 
    if (duplicates.has(int)) continue;

    if (distinct.delete(int)) {
      // If integer was successfully deleted from the `distinct` set,
      // that means it has been seen once before. Hence add it, to
      // the `duplicates` set and increment `count`.
      duplicates.add(int);
      count++;
    } else {
      // Integer is being seen for the first time and should be added
      // to the `distinct` set.
      distinct.add(int);
    }
  }

  // Finally, return the duplicates count 
  return count; 
}

Map или set?

До сих пор мы подробно рассматривали объекты Map и Set. Но в дополнение к этому нам так же нужно уметь определять, когда достаточно использовать одно вместо другого при решении проблем.

Ранее мы видели, что объекты Set являются одномерными коллекциями, а объекты Map — двумерными. Это может послужить подсказкой для определения того, какой из них лучше всего подходит для конкретной проблемы.

Другими словами, объект Map следует использовать поверх объекта Set в тех случаях, когда требуется дополнительная информация помимо ключа. В большинстве случаев эта дополнительная информация требуется для принятия решений или расчета окончательного результата программы.

Чтобы еще больше продемонстрировать это, давайте рассмотрим еще одну популярную проблему.

Дан массив целых чисел и число target, верните true, если в массиве существуют два числа, которые складываются в это число, и false в противном случае.

Если бы массив нужно было отсортировать, то можно было бы предложить решение этой проблемы с линейным временем без необходимости во вспомогательном пространстве памяти. Но поскольку существует вероятность того, что массив еще не отсортирован, нам нужно использовать объект Set, чтобы предоставить некоторое вспомогательное пространство, где мы можем решить проблему за линейное время, не взяв на себя дорогостоящую задачу сортировки массива в первую очередь.

function twoSum(nums, target) { 
  // 1. Create an empty set for complements 
  // (i.e complement = target - num) 
  const complements = new Set();

  // 2. Loop through integers until a complement is found 
  for (const num of nums) { 
    // 2a. If a complement is found, return immediately 
    if (complements.has(target - num)) return true;

    // 2b. Otherwise, add the integer to the complements set
    complements.add(num);
  }

  // 3. If it ever gets here, no complement was found 
  return false; 
}

Здесь от нас требуется вернуть true, если есть два числа, сумма которых равна target, и false в противном случае. Таким образом, нас интересуют только сами числа, поэтому для решения проблемы нам нужно использовать только один объект Set.

Теперь допустим, что мы модифицируем задачу, чтобы вернуть индексы массива этих двух чисел. Для этого лучше было бы использовать объект Map. Это потому, что, помимо самих чисел, нас теперь также интересуют их соответствующие индексы в массиве — оба из которых не могут содержаться в единственном объекте Set.

function twoSum(nums, target) { 
  // 1. Create an empty map for integers against indices 
  // (i.e Map&lt;integer, index&gt;) 
  const indices = new Map();

  // 2. Loop through integers until a complement is found 
  for (let i = 0, len = nums.length; i &lt; len; i++) { 
    // 2a. Compute the complement of the current integer 
    const complement = target - nums[i];

    // 2b. If the complement already exists in the map,
    // get the complement index from the indices map and
    // return early ([complement index, current index])
    if (indices.has(complement)) {
      return [indices.get(complement), i];
    }

    // 2c. Otherwise, add the current integer and index
    // to the indices map
    indices.set(nums[i], i);
   }

  // 3. If it ever gets here, no complement was found 
  return null; 
}

Другое использование Map и Set

Объекты Map и Set могут быть очень полезны при моделировании составных структур данных (compound data structures) для решения определенных проблем.

В общем, всякий раз, когда вам нужно найти или проверить наличие элемента со средним временем доступа, которое сублинейно зависит от количества доступных элементов (приблизительно постоянное время), вам следует рассмотреть возможность использования объекта Set или Map.

Кэширование данных с помощью объектов Map

При моделировании структур данных с целью кэширования данных объект Map можно использовать в качестве таблицы поиска для проверки наличия ключа в кэше перед выполнением операций get() или put().

Обычно реализации кеша включают в себя какую-то стратегию удаления элементов из кеша с целью освобождения места — наиболее популярными стратегиями удаления кеша являются: least frequently used (LFU) и least recently used (LRU).

Рассмотрим, например, операцию get () кеш-памяти LRU: ожидается, что запись из кеша будет извлекаться с использованием ее ключа кеша примерно за постоянное время, и в процессе запись будет оцениваться как самая недавно использованная запись, потому что она была наиболее ранняя использованная.

Чтобы соответствовать требованию быстрый поиск ключа кеша — и именно здесь выделяется объект Map или любая другая форма хэш-таблицы. Для поддержания надлежащего ранжирования недавно использованных записей можно использовать очередь приоритетов.

Однако в большинстве реализаций вместо этого используется двусвязный список, поскольку он способен как удалять запись из ее текущей позиции в списке, так и повторно вставлять ее в позицию заголовка списка, и все это за постоянное время.

Минималистский план реализации типичного кэша LRU может выглядеть примерно так (полные детали реализации опущены для краткости):

interface ICache<K, V> { 
  get: (key: K) => V; 
  put: (key: K, data: V) => void; 
}

class LRUCache<K, V> implements ICache<K, V> { 
  /** 
   * A DLL is used to maintain the order of the items 
   * in the cache according to how recently they were 
   * used (accessed or added). 
   *
   * Using a DLL makes it possible to remove an item 
   * from any position in the list (in constant time). 
   */ 
  protected list = new DoublyLinkedList<V>();

  /** 
   * A Map object is used as a lookup table to check 
   * for the existence of a key in the cache with an 
   * average access time that is sublinear on the 
   * number of cache items (approximately constant 
   * time). 
   */ 
  protected table = new Map<K, V>();

  /** 
   * @param size {number} The number of items that 
   * can be stored in the cache. 
   */ 
  constructor(protected size: number) {}

  get(key: K): V {} 
  put(key: K, data: V): void {} 
}

Графическое представление с map и set

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

Матрица смежности
Список смежности

Для большинства проблем должно быть достаточно представления списка смежности — и для этого можно использовать объекты Map и Set.

Большинство реализаций списков смежности используют массивы и/или связанные списки, но также можно использовать объекты Map и Set. Объект Map хранит каждую вершину в графе как свои ключи с соответствующим списком соседних вершин в объектах Set в качестве значений.

Типичная реализация неориентированного графа, представленного в виде списка смежности (с использованием объектов Map и Set), должна выглядеть примерно так:

interface IGraph<V> { 
  addVertex: (vertex: V) => void; 
  addEdge: (fromVertex: V, toVertex: V) => void; 
  removeVertex: (vertex: V) => void; 
  removeEdge: (fromVertex: V, toVertex: V) => void; 
}

class UndirectedGraph<V> implements IGraph<V> { 
  /** 
   * A Map object is used to map each vertex in the 
   * graph to a set of vertices that are connected 
   * to it. 
   */ 
  protected list = new Map<V, Set<V>>();

  addVertex(vertex: V): void { 
    if (!this.list.has(vertex)) { 
      // An array can be used to represent the set 
      // of vertices — but in this implementation, 
      // a Set object is used instead. 
      this.list.set(vertex, new Set<V>()); 
    } 
  }

  addEdge(fromVertex: V, toVertex: V): void { 
    this.addVertex(fromVertex); 
    this.addVertex(toVertex); 
    (this.list.get(fromVertex) as Set<V>).add(toVertex); 
    (this.list.get(toVertex) as Set<V>).add(fromVertex); 
  }

  removeVertex(vertex: V): void { 
    if (this.list.has(vertex)) { 
      for (const toVertex of this.list.get(vertex) as Set<V>) {
        this.removeEdge(vertex, toVertex); 
      }
      this.list.delete(vertex); 
    } 
  }

  removeEdge(fromVertex: V, toVertex: V): void { 
    if (this.list.has(fromVertex) && this.list.has(toVertex)) { 
      (this.list.get(fromVertex) as Set<V>).delete(toVertex); 
      (this.list.get(toVertex) as Set<V>).delete(fromVertex); 
    } 
  } 
}

Непересекающиеся множества и динамическое соединение

Определенную нишу проблем связности можно решить с помощью специальных структур данных, называемых непересекающимися наборами (disjoint-sets). Непересекающийся набор используется для поддержания набора элементов (узлов), которые разделены на ряд непересекающихся (несвязанных) подмножеств, также известных как связанные компоненты.

Непересекающиеся множества структурированы таким образом, чтобы эффективно выполнять две операции, а именно:

find: проверяет подмножество, к которому принадлежит элемент или узел
union: объединяет два подмножества в одно подмножество; также может использоваться для обнаружения циклов в неориентированных графах

Следующая реализация Disjoint-Set использует объект Map для сохранения своих неперекрывающихся подмножеств (реализация подробно описана):

interface IDisjointSet<T> { 
  find: (node: T) => T; 
  union: (nodeA: T, nodeB: T) => void; 
}

class DisjointSet<T> implements IDisjointSet<T> { 
  /** 
   * A Map object is used to link each node to the 
   * root of its corresponding connected component 
   * subset (using a disjoint-set data structure). 
   */ 
  protected subsets = new Map<T, T | number>();

  addNode(node: T): void { 
    if (!this.subsets.has(node)) { 
      this.subsets.set(node, -1); 
    } 
  }

  find(node: T): T { 
    let root = node;

    while (true) {
      const parent = this.subsets.get(root) as T;

      if (!this.subsets.has(parent)) {
        if (node !== root) {
          this.subsets.set(node, root);
        }

        return root;
      }

      root = parent;
    }
  }

  union(nodeA: T, nodeB: T): void { 
    const rootA = this.find(nodeA); 
    const rootB = this.find(nodeB);

    const sizeA = this.subsets.get(rootA) as number;
    const sizeB = this.subsets.get(rootB) as number;
    const sizeAB = sizeA + sizeB;

    if (sizeA < sizeB) {
      this.subsets.set(rootB, rootA);
      this.subsets.set(rootA, sizeAB);
    } else {
      this.subsets.set(rootA, rootB);
      this.subsets.set(rootB, sizeAB);
    }
  }

  isConnected(nodeA: T, nodeB: T): boolean { 
    return this.find(nodeA) === this.find(nodeB); 
  }
}

Заключение

Map и Set в JavaScript могут оказаться очень полезными для большого количества приложений и при попытке эффективно решить ряд проблем, особенно когда требуются эффективные поисковые запросы. Фактически, это специализированные реализации хэш-таблиц для JavaScript, похожие на типы HashMap и HashSet в Java, хотя и с некоторыми тонкими различиями.

Чтобы гарантировать безопасную сборку мусора, рассмотрите возможность использования еще более строгих коллекций с ключами WeakMap и WeakSet.

Была ли вам полезна эта статья?

[6 / 5]

Spread the love

Поделились