Javascript ES6 вычислительная/временная сложность коллекций

Question

Какая временная сложность (в примечаниях с большим О) предоставляется спецификацией ES6 для Keyed Collections (Set, Map, WeakSet и WeakMap)?

Мои ожидания, и я ожидаю, что от большинства разработчиков, является то, что спецификации и реализации будут использовать widely accepted производительных алгоритмов, в этом случае Set.prototype.has, add и delete всем, быть O (1) в среднем случае. То же самое для эквивалентов Map и Weak–.

Не совсем очевидно, была ли задана временная сложность реализации, например. в ECMAScript 2015 Language Specification - 6th Edition — 23.2 Set Objects.

Если не понимают его (и это, безусловно, очень возможно, я), это выглядит спецификации ECMA мандатов, что реализация (например Set.prototype.has) являются использовать линейное время (O (N)) алгоритм. Мне было бы чрезвычайно удивительно, что более эффективные алгоритмы не были бы санкционированы или даже разрешены спецификацией, и мне было бы очень интересно объяснить, почему это так.

Answer 1

справа от that very paragraph ваших связанно с:

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

Вы найдете то же самое предложение на Maps, WeakMaps и WeakSets.

Это выглядит спецификации ECMA мандаты, что реализации (например, Set.prototype.has) являются использовать линейное время (O(n)) алгоритм.

No:

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

Наблюдаемые семантика главным образом связана с предсказуемой итерации порядка (который все еще может быть implemented efficient and fast). В спецификации действительно предполагается, что реализация использует хеш-таблицу или что-то подобное с постоянным доступом, хотя деревья также допускают использование (с логарифмической степенью доступа).