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

benchMarkMapSet: 382.935ms benchMarkObjSet: 76.077ms benchMarkMapGet: 125.478ms benchMarkObjGet: 2.764ms

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

最初的问题已经得到解答，但是 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 的工作原理感到好奇，可以在此处找到更多详细信息。前段时间我对这个话题很感兴趣，并试图以一种可读的方式分享我的发现。

我们为什么不只是测试。

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