ES6中的Map和Set复杂度，V8实现

Question

在V8实现中，检索/查找是否是O(1)的假设是合理的吗？（我知道标准并不保证这一点）

- Uri

---

平均而言？还是最坏情况？ - Oriol

标准确实保证了次线性复杂度。顺便说一下，这是一个关于编程的内容。 - Bergi

@Oriol 都知道会很有趣。 - Uri

不确定V8使用什么，但规范提到哈希表是一种可能性。哈希表平均情况下具有常数时间操作，并且最坏情况下为线性。 - Oriol

另一个很好的答案可以在这里找到：[https://dev59.com/oZLea4cB1Zd3GeqPyid9] - Lonnie Best

Answer 1

在v8实现中，检索/查找是否是O（1）的公平假设？

是的。 V8使用一种变体的哈希表，通常对于这些操作具有O（1）的复杂度。

有关详细信息，您可能需要查看https://codereview.chromium.org/220293002/，其中基于https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables 实现了OrderedHashTable。

- Bergi

---

稍作解释一下，V8 中的 Map 和 Set 最近已经通过 JavaScript 进行了重新实现。https://codereview.chromium.org/947683002 在 V8 中这是常见的做法，通过在 JavaScript 中实现新功能，可以让 JIT（Crankshaft/Turbofan）优化运行时的代码。 - Diego Pino

@DiegoPino：谢谢。我之前以为OrderedHashTable的实现仍然是当前版本，因为我在trunk中找到了它... - Bergi

看起来实现已从 src/collections.js 迁移到了 src/builtins/builtins-collections-gen.cc https://github.com/v8/v8/blob/master/src/builtins/builtins-collections-gen.cc#L1424 - protoEvangelion

Answer 2

对于不想深入了解细节的人：

1：我们可以假设好的哈希表实现的时间复杂度几乎为O（1）。
2：这篇博客是由V8团队发布的，其中解释了对其 Map、Set、WeakSet和WeakMap 的哈希表实现进行的一些内存优化： 优化哈希表：隐藏哈希码

基于1和2：V8的Set和Map的get & set & add & has 时间复杂度几乎为O(1)。

- David Guan

Answer 3

原问题已经得到解答，但O（1）并不能说明实现的效率有多高。

首先，我们需要了解在Maps中使用的哈希表的变体。 “传统”哈希表不适用，因为它们没有提供任何迭代顺序保证，而ES6规范要求插入按照迭代顺序进行。因此，V8中的Maps是建立在所谓的deterministic hash tables之上的。这个想法与经典算法类似，但是对于桶有另一层间接引用，并且所有条目都被插入并存储在固定大小的连续数组中。确定性哈希表算法确实保证基本操作（如set或get）的O（1）时间复杂度。

接下来，我们需要知道哈希表的初始大小，负载因子以及它如何（以及何时）增长/缩小。简短的答案是：初始大小为4，负载因子为2，表格（即Map）在容量达到时增加x2，并在删除条目超过1/2时缩小。

让我们考虑最坏情况，当表中有N个条目（它满了），所有条目都属于单个桶，并且所需的条目位于尾部。在这种情况下，查找需要通过链元素移动N次。

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

众所周知，哈希表中的各个操作非常“廉价”，但重新哈希是不廉价的。重新哈希具有O（N）时间复杂度，并需要在堆上分配新哈希表。此外，重新哈希作为插入或删除操作的一部分执行，必要时进行。因此，例如，map.set（）调用可能比您预期的更昂贵。幸运的是，重新哈希是相对较少的操作。

除此之外，内存布局或哈希函数等细节也很重要，但我不准备在这里详细介绍。如果你好奇V8 Maps是如何工作的，你可以在这里找到更多细节here。我曾经对这个主题感兴趣，并尝试以易读的方式分享我的发现。

- Andrey Pechkurov

Answer 4

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.935毫秒 benchMarkObjSet: 76.077毫秒 benchMarkMapGet: 125.478毫秒 benchMarkObjGet: 2.764毫秒

benchMarkMapSet: 373.172毫秒 benchMarkObjSet: 77.192毫秒 benchMarkMapGet: 123.035毫秒 benchMarkObjGet: 2.638毫秒

- Abhay Kumar

---

这是因为Map类是按插入顺序排序的。 - Manohar Reddy Poreddy

将数字作为对象属性名称时会以特殊方式处理。当您修改基准以使用字符串属性名称 map.set('k' + i, i)，obj['k' + i] = i 等时，对象的速度比 map 显著慢。 - Victor

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)吧。

- Redu