javascript es6 Map and Set 复杂度，v8 实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33611509/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
es6 Map and Set complexity, v8 implementation
提问by Uri
Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?
在 v8 实现中检索/查找是 O(1) 是一个公平的假设吗？
(I know that the standard doesn't guarantee that)
（我知道标准并不能保证）
回答by Bergi
Is it a fair assumption that in v8 implementation retrieval / lookup is O(1)?
在 v8 实现中检索/查找是 O(1) 是一个公平的假设吗？
Yes. V8 uses a variant of hash tables that generally have O(1)complexity for these operations.
是的。V8 使用哈希表的变体，O(1)这些变体通常对这些操作具有复杂性。
For details, you might want to have a look at https://codereview.chromium.org/220293002/where OrderedHashTableis implemented based on https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables.
有关详细信息，您可能想查看https://codereview.chromium.org/220293002/，其中OrderedHashTable基于https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables实现。
回答by David Guan
For people don't want to dig into the rabbit hole too deep:
对于不想把兔子洞挖得太深的人：
1: We can assume good hash table implementations have practically O(1) time complexity.
2: Here is a blog posted by V8 team explains how some memory optimization was done on its hashtable implementationfor Map, Set, WeakSet, and WeakMap: Optimizing hash tables: hiding the hash code
1：我们可以假设好的哈希表实现实际上具有 O(1) 时间复杂度。
2：这是张贴V8团队博客中解释了一些内存优化是如何在其完成的散列表实施方案为Map，Set，WeakSet，和WeakMap：优化哈希表：隐藏的哈希码
Based on 1 and 2: V8's Set and Map's get& set& add& hastime complexity practically is O(1).
基于1和2：V8的设置和地图的get＆set＆add＆has时间复杂度几乎为O（1）。
回答by Abhay Kumar
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: 382.935ms
benchMarkObjSet: 76.077ms
benchMarkMapGet: 125.478ms
benchMarkObjGet: 2.764ms
benchMarkMapSet: 373.172ms
benchMarkObjSet: 77.192ms
benchMarkMapGet: 123.035ms
benchMarkObjGet: 2.638ms
benchMarkMapSet: 373.172ms
benchMarkObjSet: 77.192ms
benchMarkMapGet: 123.035ms
benchMarkObjGet: 2.638ms
