Как устроено множество (Set) и чем хеш-множество отличается от упорядоченного?

Множество хранит уникальные ключи без значений; хеш-множество даёт `add`, `has` и `delete` в среднем за O(1), а упорядоченное на сбалансированном дереве — за O(log n), зато держит ключи отсортированными.

Хеш-множество

• По сути хеш-таблица, где хранится только ключ: HashSet в Java реализован поверх HashMap.
• Порядок обхода зависит от реализации: в Java и Python не гарантирован, а JS Set итерирует в порядке вставки.
• Худший случай O(n) при массовых коллизиях.

Упорядоченное множество

• Красно-чёрное дерево: TreeSet в Java, std::set в C++.
• Даёт то, чего нет у хеша: минимум и максимум, floor/ceiling, диапазоны, обход по возрастанию.
• В JS и Python встроенного нет — берут библиотеку (например, sortedcontainers) или сортированный массив с бинарным поиском.

Особенности JS Set

• Сравнение по SameValueZero: NaN равен NaN, +0 и -0 — один элемент.
• Объекты сравниваются по ссылке: два одинаковых {id: 1} — разные элементы.
• С ES2025 есть union, intersection, difference, isSubsetOf.

Когда что выбирать

Нужны только проверки принадлежности и дедупликация — хеш. Нужны соседи по порядку, «ближайший больший» или вывод в сортировке — дерево.

Коротко для собеседования

Хеш-множество — выбор по умолчанию для дедупликации и проверки принадлежности за O(1); упорядоченное на дереве берут, когда нужны минимум, соседи по порядку или диапазоны, за O(log n). В JS помните, что Set сравнивает объекты по ссылке, зато итерирует в порядке вставки.