es6 Map和Set复杂度,v8实现

Question

在v8实现检索/查找是否为O(1)这是一个公平的假设吗？

(我知道标准并不保证)

Answer 1

在v8实现检索/查找是否为O(1)这是一个公平的假设吗？

是.V8使用散列表的变体,这些散列表通常具有O(1)这些操作的复杂性.

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

Answer 2

对于那些不想深入兔子洞的人：

1：我们可以假设好的哈希表实现实际上具有O（1）时间复杂度。
2：这是张贴V8团队博客中解释了一些内存优化是如何在其完成的散列表实施方案为Map，Set，WeakSet，和WeakMap：优化哈希表：隐藏的哈希码

基于1和2：V8的设置和地图的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) 并没有说明实现的效率如何。

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

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

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

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

众所周知，虽然散列表中的单个操作“便宜”，但重新散列却不是。重新散列的时间复杂度为 O(N)，并且需要在堆上分配新的散列表。此外，在必要时，重新散列作为插入或删除操作的一部分执行。因此，例如，map.set()通话费用可能比您预期的要高。幸运的是，重新散列是一种相对不常见的操作。

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