es6映射和设置复杂性，v8实现

Question

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

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

Answer 1

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);

基准MarkMapSet： 382.935ms基准MarkObjSet： 76.077ms基准MarkMapget： 125.478ms基准MarkObjget： 2.764ms

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

Answer 2

因为人们不想把兔子洞挖得太深：

1：我们可以假设好的哈希表实现实际上有O（1）时间复杂度。
2：这是V8团队发布的一篇博客，解释了如何在其哈希表实现上为Map，Set，进行内存优化优化哈希表：隐藏哈希代码

基于1和2:V8的设置和地图的get

Answer 3

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

是的。V8使用的散列表变体通常具有这些操作的O（1）复杂性。

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