javascript中Set和Map的时间复杂度

Question

javascript 中 Set & Map 基本操作的时间复杂度是多少？它们是在 hashmap 还是 BST 中？

Answer 1

根据 ECMA 的 Set 和 Maps 文档（http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-objects）：

集合对象必须使用哈希表或其他机制来实现，平均而言，这些机制提供的访问时间与集合中的元素数量呈次线性关系。本 Set 对象规范中使用的数据结构仅用于描述 Set 对象所需的可观察语义。它不是一个可行的实施模型。

你会发现与 Maps、WeakMaps 和 WeakSets 相似的句子。因此，您应该期望时间复杂度是次线性的。此外，您可以查看有关Javascript ES6 计算/时间复杂度集合的解决方案