es6 Map 和 Set 复杂度，v8 实现

Question

在 v8 实现中检索/查找的复杂度为 O(1) 是否合理？

（我知道标准并不能保证）

Answer 1

Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?

是的。 V8 使用哈希表的一种变体，这些哈希表通常具有 O(1) 这些操作的复杂性。

有关详细信息，您可能想看看 https://codereview.chromium.org/220293002/ where OrderedHashTable is implemented based on https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables。

Answer 2

对于不想把兔子洞挖得太深的人：

1：我们可以假设好的哈希 table 实现实际上具有 O(1) 时间复杂度。
2：这是 V8 团队发布的一篇博客，解释了如何对其 hashtable 实现 for Map、Set、WeakSet，以及 WeakMap：Optimizing hash tables: hiding the hash code

基于1和2：V8的Set和Map的get & set & add & has时间复杂度实际上是O(1).

Answer 3

let map = new Map();
let obj = {};

const benchMarkMapSet = size => {
console.time("benchMarkMapSet");
for (let i = 0; i < size; i++) {
    map.set(i, i);
}
console.timeEnd("benchMarkMapSet");
};

const benchMarkMapGet = size => {
console.time("benchMarkMapGet");
for (let i = 0; i < size; i++) {
    let x = map.get(i);
}
console.timeEnd("benchMarkMapGet");
};

const benchMarkObjSet = size => {
console.time("benchMarkObjSet");
for (let i = 0; i < size; i++) {
    obj[i] = i;
}
console.timeEnd("benchMarkObjSet");
};

const benchMarkObjGet = size => {
console.time("benchMarkObjGet");
for (let i = 0; i < size; i++) {
    let x = obj[i];
}
console.timeEnd("benchMarkObjGet");
};

let size = 2e6;

benchMarkMapSet(size);
benchMarkObjSet(size);
benchMarkMapGet(size);
benchMarkObjGet(size);

benchMarkMapSet: 382.935ms benchMarkObjSet: 76.077ms benchMarkMapGet: 125.478ms benchMarkObjGet: 2.764ms

benchMarkMapSet: 373.172ms benchMarkObjSet: 77.192ms benchMarkMapGet: 123.035ms benchMarkObjGet: 2.638ms

Answer 4

最初的问题已经得到解答，但 O(1) 并不能说明实施的效率。

首先，我们需要了解哈希 table 的变体用于 Maps。 “经典”散列 tables 不会这样做，因为它们不提供任何迭代顺序保证，而 ES6 规范要求插入按迭代顺序进行。因此，V8 中的地图构建于 so-called deterministic hash tables 之上。这个想法类似于经典算法，但是桶还有另一层间接层，所有条目都被插入并存储在一个固定大小的连续数组中。确定性哈希 tables 算法确实保证了基本操作的 O(1) 时间复杂度，例如 set 或 get.

接下来，我们需要知道散列的初始大小是多少 table、负载因子以及它如何（以及何时）grows/shrinks。简短的回答是：初始大小为 4，负载因子为 2，table（即地图）一旦达到其容量就会增长 x2，一旦超过 1/2 的删除量就会缩小条目。

让我们考虑一下 worst-case，当 table 的 N 个条目中有 N 个（它已满），所有条目都属于一个桶，并且所需的条目位于尾部。在这种情况下，查找需要通过链元素进行 N 次移动。

另一方面，在最佳情况下 table 已满，但每个桶有 2 个条目，查找最多需要 2 次移动。

这是一个 well-known 事实，虽然散列 table 中的单个操作“便宜”，但重新散列不是。重新散列具有 O(N) 时间复杂度，并且需要在堆上分配新散列 table。此外，必要时，重新散列作为插入或删除操作的一部分执行。因此，例如，map.set() 调用可能比您预期的更昂贵。幸运的是，重新散列是一个相对不常见的操作。

除此之外，内存布局或哈希函数等细节也很重要，但我不打算在这里详细介绍这些细节。如果您对 V8 地图的幕后工作方式感到好奇，您可能会找到更多详细信息 here。前段时间我对这个话题很感兴趣，并试图以一种可读的方式分享我的发现。

Answer 5

为什么我们不直接测试。

var size_1 = 1000,
    size_2 = 1000000,
    map_sm = new Map(Array.from({length: size_1}, (_,i) => [++i,i])),
    map_lg = new Map(Array.from({length: size_2}, (_,i) => [++i,i])),
    i      = size_1,
    j      = size_2,
    s;

s = performance.now();
while (i) map_sm.get(i--);
console.log(`Size ${size_1} map returns an item in average ${(performance.now()-s)/size_1}ms`);
s = performance.now();
while (j) map_lg.get(j--);
console.log(`Size ${size_2} map returns an item in average ${(performance.now()-s)/size_2}ms`);

所以对我来说，它似乎随着大小的增长而收敛到 O(1)。那么我们称它为 O(1)。

es6 Map 和 Set 复杂度，v8 实现

es6 Map and Set complexity, v8 implementation

javascript

ecmascript-6

set

complexity-theory

v8