JavaScript中Set和Map的时间复杂度

Question

JavaScript中Set和Map的时间复杂度

javascriptdictionarysettime-complexity

3

在javascript中，Set和Map的基本操作的时间复杂度是多少？

它们是哈希表还是二叉搜索树？

- Jeong Ho Nam

4

该规格要求实现提供次线性的访问时间。具体细节留给每个实现自行确定。 - Pointy

1

据我所知，大多数（如果不是全部）的实现都使用哈希，因此访问时间为 O(1)。但是，规范并没有强制要求这样做，因此也有可能使用基于 BST 的实现。 - VLAZ

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vishal Kotak · Accepted Answer

根据ECMA关于Set和Maps的文档（http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-objects），Set对象必须使用哈希表或其他机制来实现，这些机制的平均访问时间在集合中元素数量的次线性。此Set对象规范中使用的数据结构仅旨在描述Set对象所需的可观察语义，而不是可行的实现模型。

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