Почему поиск в set работает за O(1)?

Как работает Set в JavaScript

Set — это коллекция уникальных значений, реализованная на основе хеш-таблицы. Хеш-таблица — это структура данных, которая хранит пары ключ-значение, где ключом является сам элемент. При добавлении элемента вычисляется его хеш-функция, которая преобразует значение в индекс массива (bucket). Затем элемент помещается в соответствующую ячейку.

Почему поиск O(1)

Поиск элемента в Set выполняется за константное время, потому что:

• Вычисление хеша элемента — быстрая операция, обычно O(1).
• Хеш сразу указывает на ячейку, где может находиться элемент.
• Даже при коллизиях (когда разные элементы имеют одинаковый хеш) используется цепочка или открытая адресация, но среднее время остаётся O(1) при хорошем распределении.

Пример кода

const set = new Set();
set.add(10);
set.add('hello');
set.add({a: 1});

// Поиск за O(1)
console.log(set.has(10)); // true
console.log(set.has('world')); // false

Вывод

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