Set & WeakSet

24.07.2018
Смотрите видео
на Youtube
Типы коллекций Set и WeakSet представляют собой множество — набор значений, причём каждое значение может встречаться только один раз. До ECMAScript 6 реализовать множество в JavaScript можно было с помощью массива: при добавлении элемента проверять, есть ли он уже во множестве или нет. Так вот, Set и WeakSet — это специальные структуры данных для хранения уникальных значений. Чем они отличаются друг от друга, мы поговорим чуть позже, а пока подробнее рассмотрим Set. Создадим новый set и добавим в него элементы:

const fruits = new Set();

fruits.add('apple');
fruits.add('orange');
fruits.add('pear');
fruits.add('orange');

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


console.log(fruits.size);

Элементы Set могут быть разных типов, для проверки на равенство используется алгоритм SameValueZero. Он похож на строгое равенство, но ещё и корректно обрабатывает значение NaN.


fruits.add(NaN);
fruits.add(NaN);

Как видите, размер множества стал равен четырём, потому что NaN добавился только один раз.

Проверить наличие элемента во множестве можно с помощью метода has():


console.log(fruits.has('apple'));
console.log(fruits.has(NaN));

А удалить с помощью метода delete():


fruits.delete('apple');
console.log(fruits.has('apple'));

С помощью метода clear() можно удалить все элементы множества:


fruits.clear();

Можно задать элементы множества в конструкторе, он принимает любую итерируемую структуру данных, например, массив:


const vegetables = new Set(['tomato', 'potato', 'broccoli']);

Метод add можно вызывать по цепочке:


vegetables.add('cucumber')
    .add('zucchini');

Set является итерируемой структурой данных, его можно перебрать с помощью цикла for...of:


for (let vegetable of vegetables) {
    console.log(vegetable);
}

Set сохраняет тот порядок элементов, в котором они были добавлены.

Можно использовать деструктуризацию:


const [veg1, veg2] = vegetables;
console.log(veg1, veg2);

Или превратить множество в массив с помощью spread-оператора или метода Array.from():


console.log([...vegetables]);
console.log(Array.from(vegetables));

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

Объединение множеств — множество, содержащее в себе все элементы исходных множеств. Объединение можно реализовать так:


const a = new Set([1,2,3]);
const b = new Set([4,3,2]);
const union = new Set([...a, ...b]);

С помощью spread-оператора мы объединили два сета в один массив, а потом передали этот массив в качестве параметра в конструктор нового сета.

Пересечение множеств — это множество, которому принадлежат элементы, которые есть во всех исходных множествах.


const a = new Set([1,2,3]);
const b = new Set([4,3,2]);
const intersection = new Set([...a].filter(x => b.has(x)));

На этот раз мы превращаем первый сет в массив с помощью spread-оператора и применяем к нему метод filter. В условии фильтра проверяем, что данный элемент есть во втором множестве. Таким образом мы получаем массив элементов, которые есть в обоих множествах. А потом передаём этот массив в конструктор нового сета.

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


const a = new Set([1,2,3]);
const b = new Set([4,3,2]);
const difference = new Set([...a].filter(x => !b.has(x)));

Теперь мы получаем массив элементов первого множества, которые не входят во второе множество, и передаём этот массив в конструктор нового сета.

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

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

Сублинейно — значит меньше, чем линейно. Коллекция Set в V8, например, реализована с помощью хэш-таблиц, которые обеспечивают константное время проверки, есть элемент во множестве или нет. В массиве время такой проверки линейно зависит от количества элементов.

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

WeakSet очень похож на Set — это тоже коллекция, которая хранит уникальные значения, но:

  • WeakSet может содержать только объекты
  • WeakSet не имеет свойства size
  • WeakSet не имеет метода clear()
  • WeakSet не является итерируемым
  • И если на объект, который хранится в WeakSet, нет ни одной внешней ссылки, то сборщик мусора удалит этот объект.

В остальном API WeakSet точно такой же, как у Set.

Юзкейсы для WeakSet, которые мне удалось найти, довольно специфические, например, Доменик Деникола предлагает вот такой способ проверить в классе, что метод вызывается именно у экземпляра этого класса.


const foos = new WeakSet();

class Foo {
    constructor() {
        foos.add(this);
    }

    method() {
        if (!foos.has(this)) {
            throw new TypeError('Incompatible object!');
        }
    }
}