Es6映射和 Set 复杂性，v8实现

在 v8中检索/查找是 O (1) ，这是一个合理的假设吗？

(我知道标准并不能保证这一点)

33478 次浏览
小开
最佳答案

在 v8中检索/查找是 O (1) ，这是一个合理的假设吗？

对于这些操作，V8使用的散列表的变体通常具有 O(1)复杂性。

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

小开

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

1: 我们可以假设好的哈希表实现具有实际的 O (1)时间复杂度。
2: 这里是 V8团队发布的一篇博客，解释了如何在 哈希表实现上对 Map、 Set、 WeakSet和 WeakMap: 优化哈希表: 隐藏哈希代码进行一些内存优化

基于1和2: V8的集合和地图的 get & set & add & has的时间复杂度实际上是 O (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);

马克地图集: 382.935毫秒 目标集: 76.077 ms 125.478 ms 2.764 ms

BenchMarkMapSet: 373.172 ms 标准目标集: 77.192毫秒 BenchMarkMapGet: 123.035 ms 2.638 ms

小开

最初的问题已经得到了回答，但是 O (1)并没有说明实现的效率有多高。

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

接下来，我们需要知道散列表的初始大小、负载因子以及它是如何(以及何时)增长/收缩的。简短的回答是: 初始大小为4，负载因子为2，表(即 Map)在达到其容量时增长为 x2，一旦删除的条目超过1/2，表就会收缩。

让我们考虑最坏的情况，当表中有 N 个条目(已满) ，所有条目都属于一个 bucket，并且所需的条目位于尾部。在这种情况下，查找需要 N 次通过链元素。

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

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

除此之外，诸如内存布局或散列函数之类的细节也很重要，但我在这里不打算深入讨论这些细节。如果您好奇 V8地图是如何在引擎盖下工作的，您可能会发现更多的细节 给你。一段时间以前，我对这个话题很感兴趣，并试图以一种可读的方式分享我的发现。

小开

我们为什么不测试一下。

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


提交答案