Javascript Maps 是否有一组可以设置的键，或者它们是否有一组可以完成的键操作？

Question

所以我知道 Javascript Maps 有一定数量的键可以存储（大约 16.7 M ）。

我试图测试我是否可以（以一种非常丑陋的方式）从数组中删除最旧的元素。我注意到无论我做什么，实际上并不是地图大小成为限制因素，而是我所做的操作数量限制了我。

下面是一个示例代码：

const map = new Map();
let i = 0;

while (true) {
  i++;

  set(i, i);

  if (i % 1000 === 0)
    console.log('INSERTED: ', i, 'KEYS', 'MAP SIZE :', map.size);
}

function set(key, value) {
  if (map.size > 16770000) {
    Array.from(map.keys()).slice(0, 10000).forEach(key => map.delete(key));
    console.log('DELETED, current map size:', map.size);
  }

  try {
    map.set(key, value);
  } catch (e) {
    console.log('MAP SIZE:', map.size, 'INSERTED:', key);
    throw e;
  }
}

当您运行代码段时，只需检查您的控制台。您应该注意的是最后（当抛出异常时）您将获得 Map Size 和 INSERTED。地图大小将是一个变量（取决于您删除的元素数量，在本例中为 10000）但 INSERTED 将始终是相同的值。那么，如果我没有达到地图的极限，那怎么会......我不知何故达到了极限。这是我缺少的某种参考问题吗？

编辑：正如@CRice 所提到的，如果您将删除的项目增加到 10,000,000 左右，那么这个循环似乎会永远持续下去。

编辑 2：这是 V8 开发人员之一关于 16.7M 密钥限制的回答：https : //stackoverflow.com/a/54466812/5507414

编辑 3：见答案：https : //stackoverflow.com/a/63234302/5507414。我们仍然需要 V8 开发人员或对引擎有更多了解的人来澄清这一点。

Answer 1

我修改了您的脚本（见下文）以查看在Map.

结果是 8388608 (= 16777216/2) with node v12.18.1（建立在 Chrome 的 V8 JavaScript 引擎上）。

它让我想起了一种常见的模式，即当底层数据结构几乎满时，它的大小会增加一倍。所以我在 V8 引擎中寻找实际的 Map 实现。

以下是 V8 开发博客对此的描述：

ECMAScript 2015 引入了几种新的数据结构，例如 Map、Set、WeakSet 和 WeakMap，所有这些结构都在底层使用了哈希表。

这是V8 源代码中一个有趣的注释：

HashTable 是 FixedArray 的子类，它实现了一个哈希表
使用开放寻址和二次探测。

为了使二次探测工作，没有的元素
尚未使用和已删除的元素是
区别开来。当删除的元素被删除时继续探测
遇到未使用的元素时停止。

- 尚未使用 key == undefined 的元素。
- 带有 key == the_hole 的元素已被删除。

基本上，当脚本删除一个键时，它似乎只是被标记为已删除。正如 V8 代码注释所说，它变成了一个“洞”。只有当引擎真正重建底层数据结构时才会真正删除它（这就是脚本删除一半元素时发生的情况）。

无论如何，这是我的理解。我们需要深入研究 V8 代码以阐明所有细节。

其他有趣的参考资料：

• Node.js Map和FixedArray 限制中的最大条目数
• 开放寻址和懒惰删除

map = new Map();
let i = 0;

while (true) {
  i++;

  try {
    map.set(i, i);
  } catch (e) {
    console.log(e);
    break;
  }

  if (i % 100000 === 0)
    console.log('inserted: ', i);
}

console.log('max map size:', map.size, 'inserted:', i);

let j = 0;
while (true) {
  j++;

  map.delete(j);

  if (j % 100000 === 0) {
    console.log('deleted: ', j, 'map size: ', map.size);

    if (map.size == 0) {
        break;
    }
  }

  try {
    map.set(i, i);
  } catch(e) {
    continue;
  }

  break;
}

console.log('deleted before inserting again: ', j);

Answer 2

我深入研究了 ECMA 语言规范以查看 Maps（链接）。您所看到的行为似乎与规范一致，并且来自 Map 删除原型的规范定义。

当一个地图元素与删除Map.prototype.delete(key)，该规范只要求具有匹配的元素key被设置为空。

这是从ECMA 规范复制和粘贴的定义：

3.1.3.3 Map.prototype.delete ( key )

采取以下步骤：

1. 令 M 为 this 值。
2. 履行 ？RequireInternalSlot( M , [[MapData]])。
3. 让条目成为列表，即M .[[MapData]]。
4. 对于作为条目元素的每个 Record { [[Key]], [[Value]] } p，执行 a。如果p .[[Key]] 不为空且 SameValueZero( p .[[Key]], key ) 为真，则     i. 将p .[[Key]] 设置为空。     ii. 将p .[[Value]] 设置为空。     三、返回真。
   
   
   
   
5. 返回假。

对我们来说，这里最重要的部分是 4a。

删除元素时，Map.prototype.delete检查每个记录p 中是否存在p .[[Key]] 与提供的key参数匹配的元素。

找到后，p .[[Key]] 和p .[[Value]] 都设置为 empty。

这意味着，当键和值消失并且不再存储或可检索时，存储键和值的元素本身的空间可能确实留在 Map 的存储中，并且仍然占用幕后的空间.

虽然该规范包含以下关于其使用“空”的注释......

值空用作指定设备以指示条目已被删除。实际实现可能会采取其他行动，例如从内部数据结构中物理删除条目。

...它仍然为实现打开了大门，可以简单地擦除数据而不回收空间，这显然是您的示例中发生的情况。

什么Map.prototype.set（键，值）？

在 的情况下set()，该函数首先检查具有匹配键的现有元素以改变 的值，并跳过该过程中的所有空元素。如果没有找到，则“附加 p [<key, value>] 作为条目的最后一个元素”。

那么，Map.prototype.size呢？

在 的情况下size，规范循环遍历 Map 中的所有元素，并简单地为遇到的所有非空元素增加一个计数器。

我发现这真的很有趣......如果我不得不冒险猜测，我认为在大多数情况下查找和删除空元素的开销被认为是不必要的，因为必须达到填充结构的数量如此之大， IE。因为地图包含这么多。我想知道删除一个空元素的时间和空间开销对于足够大的数据集有多大需要。