Javascript 地图是否有一定数量的可以设置的键，或者它们是否有一定数量的可以完成的键操作？

Question

所以我知道 Javascript 地图有一定数量的键可以存储（大约 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 将是一个变量（取决于您删除了多少元素，在本例中为 10000）但 INSERTED 将始终是相同的值。那么，如果我没有达到地图的极限怎么办……我不知何故达到了极限。这是我遗漏的某种参考问题吗？

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

编辑 2：这是 V8 开发者之一关于 16.7M 密钥限制的回答：

编辑 3：参见答案：。我们仍然需要 V8 开发人员或对引擎有进一步了解的人来澄清这一点。

Answer 1

我深入研究了 ECMA 语言规范以查看 Maps (Link)。您看到的行为似乎与规范一致，并且来自 Map 的 delete 原型的规范定义。

使用Map.prototype.delete(key)删除Map元素时，规范只要求匹配key的元素设置为空。

这是从 ECMA spec 复制粘贴的定义：

3.1.3.3 Map.prototype.delete ( key )
The following steps are taken:

Let M be the this value.

Perform ? RequireInternalSlot(M, [[MapData]]).

Let entries be the List that is M.[[MapData]].

For each Record { [[Key]], [[Value]] } p that is an element of entries, do
a. If p.[[Key]] is not empty and SameValueZero(p.[[Key]], key) is true, then
    i. Set p.[[Key]] to empty.
    ii. Set p.[[Value]] to empty.
    iii. Return true.

Return false.

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

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

找到时，p.[[Key]]和p.[[Value]]都是设置为空.

这意味着，当键和值消失并且不再存储或检索时，space，即存储键和值的元素本身，可能确实留在了 Map 的存储中, 并且仍然在幕后 space。

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

The value empty is used as a specification device to indicate that an entry has been deleted. Actual implementations may take other actions such as physically removing the entry from internal data structures.

...它仍然为实现简单地擦除数据而不回收 space 敞开大门，这显然是您此处示例中发生的情况。

Map.prototype.set(key, value)呢？

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

那么 Map.prototype.size 呢？

在 size 的情况下，规范遍历 Map 中的所有元素，并简单地为它遇到的所有 non-empty 元素增加一个计数器.

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

Answer 2

我调整了你的脚本（见下文）以查看在它可以再次插入密钥之前必须删除多少项目 Map。

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

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

V8 开发 blog 对此的评价如下：

ECMAScript 2015 introduced several new data structures such as Map, Set, WeakSet, and WeakMap, all of which use hash tables under the hood.

V8 source code 中有一条有趣的评论：

HashTable is a subclass of FixedArray that implements a hash table
that uses open addressing and quadratic probing.

In order for the quadratic probing to work, elements that have not
yet been used and elements that have been deleted are
distinguished.  Probing continues when deleted elements are
encountered and stops when unused elements are encountered.

- Elements with key == undefined have not been used yet.
- Elements with key == the_hole have been deleted.

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

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

其他有趣的参考资料：

and FixedArray limit
Open addressing and Lazy deletion

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 3

please check this i made some change in code now its working please let me know if it still not working

i accept this is not best way to do this, but reinitializing map object will let us add some more data, but it's also slow down operation speed, please open console to see output

var map = new Map();
let i = 0;
var ke=[]
while (true) {
  i++;

  set(i, i,map.size);

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

function set(key, value,s) {

 
  if (s >= 16730000) {
     
   var arr= ke.slice(0, 10000)
   ke.splice(0, 10000)
   arr.forEach(key => map.delete(key));
    console.log('DELETED, current map size:', map.size);
    map= new Map(map);
  
  arr=[]
  }else{
    try {
        ke.push(key)
        map.set(key, value);
      } catch (e) {
        console.log('MAP SIZE:', map.size, 'INSERTED:', key);
        throw e;
      }
  }

 
}

Javascript 地图是否有一定数量的可以设置的键，或者它们是否有一定数量的可以完成的键操作？

Do Javascript Maps have a set amount of keys that they can set or do they have a set amount of key operations that can be done?

javascript

arrays

maps

v8

3.1.3.3 Map.prototype.delete ( key )

Map.prototype.set(key, value)呢？

那么 Map.prototype.size 呢？