ES6 集合：线性时间复杂度是强制性的吗？

ES6 规范引入了键控集合，例如 Set、Map、WeakSet 和 WeakMap。这些集合提供了基于键存储和检索数据的有效方法。然而，问题出现了：规范是否要求这些集合上的操作具有线性时间复杂度？

线性时间复杂度或算法选择左开放

尽管期望广泛接受的高性能算法，例如 Set 和 Map 原型的 O(1) 访问，ES6 规范令人惊讶地为线性时间算法敞开了大门。

该规范指出“集合对象必须使用平均而言提供次线性访问时间的[机制]来实现。”这种语言可以被解释为包括线性时间算法。然而，它并没有明确强制要求它们。

同样，该规范也不排除性能更高的算法，如哈希表或平衡树，它们提供对数时间复杂度。

缺少明确的性能要求

规范中缺乏明确的性能要求引起了开发人员的关注，他们希望规范能够快速确定优先级

但是，值得注意的是，该规范侧重于可观察的语义，例如可预测的迭代顺序。虽然人们普遍期望基于哈希的高效实现，但该规范允许使用树等替代数据结构，它提供对数时间复杂度。

结论

ES6 规范确实没有明确要求对键控集合进行操作的线性时间复杂度。虽然在某些实现中可以观察到线性时间算法，但该规范为更高性能的实现留出了空间。开发人员应查阅特定浏览器或运行时文档，以了解这些集合操作在不同上下文中的实际时间复杂度。