Какая временная сложность (в примечаниях с большим О) предоставляется спецификацией ES6 для Keyed Collections (Set, Map, WeakSet и WeakMap)?
Мое ожидание, и я ожидаю, что у большинства разработчиков заключается в том, что спецификации и реализации будут использовать широко принятые алгоритмы исполнения, в этом случае Set.prototype.has
, add
и delete
для всех O (1) в среднем случае. То же самое для эквивалентов Map
и Weak–
.
Мне не совсем очевидно, была ли задана временная сложность реализации, например. в Спецификация языка ECMAScript 2015 - 6-е издание - 23.2 Установка объектов.
Если я не пойму это (и это, конечно, очень возможно), то, похоже, спецификация ECMA требует, чтобы реализации (например, Set.prototype.has
) использовали алгоритм линейного времени (O (n)). Мне было бы чрезвычайно удивительно, что более эффективные алгоритмы не были бы санкционированы или даже разрешены спецификацией, и мне было бы очень интересно объяснить, почему это так.