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?

Question

So I know that Javascript Maps have a set amount of keys that they can store ( around 16.7 M ).

I was trying to test if I can ( in a very ugly way ) remove the oldest elements from the array. I noticed that no matter what I do it is actually not the Map size that was a limiting factor but it was rather the amount of operations I have done that were limiting me.

Below is an example code:

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;
  }
}

When you run the snippet, just check your console. What you should notice is at the end ( when the exception is thrown ) you will get the Map Size and the INSERTED. Map Size will be a variable ( depending on how many elements you remove, which in this case is 10000) but INSERTED will always be the same value. So how come if I am not reaching the limit of the Map.... I am somehow reaching a limit. Is this some kind of reference issue that I am missing?

EDIT: As mentioned by @CRice if you increase the items deleted to around 10,000,000 then the cycle continues on seemingly forever.

EDIT 2: Here is an answer from one of the V8 devs talking about the limit of 16.7M keys: https://mcmap.net/q/404504/-maximum-number-of-entries-in-node-js-map

EDIT 3: See answer: https://mcmap.net/q/928534/-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. We still need a V8 developer or someone with further knowledge in the engine to clarify this.

Expurgatory

Not sure I understand the problem, can you clarify? I see in my console that the size of the map at the end is 16767216 (about 16.7M, as you state). The last key inserted was 16777217, which is 10000 higher than the max map size, and the logs show that you deleted 10000 keys just before that so everything looks fine to me... – Merilee

Well If I deleted 10000 keys, doesn't that mean that I should be able to set 10000 keys more? The thing is I cannot. The last key inserted should actually be with 10000 more. But it is not. If you get the snippet and change it so it is not 10000 but 20000 you will see that the last key inserted will still be 16777217. Why isn't there more space when I delete the keys? – Expurgatory

Yes I see what you mean now. That is curious. I also notice that if you vastly increase the number of deleted items (I tried 10000000) then it continues the insert/delete cycle forever. I am also interested in what is going on here. – Merilee

Oh I didn't know that honestly. I tried 1 million but for me it failed pretty fast. Edit: just tested it. Anything below 9M is not gonna work. – Expurgatory

Great question and great answers. Voted up on everything. Can you also add a reference that points to that 16.7M limitation, please. – Ashjian

@Ashjian I added references in my answer; this one explains the Map limitation: https://mcmap.net/q/404504/-maximum-number-of-entries-in-node-js-map – Cerate

Answer 1

I adapted your script (see below) to see how many items had to be deleted before it could insert keys again in the Map.

The result is 8388608 (= 16777216/2) with node v12.18.1 (built on Chrome's V8 JavaScript engine).

It reminded me of a usual pattern where the underlying data structure doubles in size when it's almost full. So I looked for the actual Map implementation in the V8 engine.

Here's what V8 development blog says about it:

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

And here's an interesting comment in 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.

Basically, when the script deletes a key, it seems that it's just marked as deleted. It becomes a "hole", as the V8 code comment puts it. It's actually deleted only when the engine actually rebuilds the underlying data structure (that's what happens when the script deletes half of the elements).

Anyway, that's my understanding. We would need to delve into V8 code in order to clarify all the details.

Other interesting references:

• Maximum number of entries in Node.js Map 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);

Cerate

This is actually a great answer and you've done some amazing research. I guess we need a V8 developer to clarify this further. But it does seem like they clear Map memory when half of the data is cleaned – Expurgatory

You may add the "v8" tag to your question in order to get a V8 developer's attention. – Cerate

Good idea! Added! – Expurgatory

Answer 2

I dug into the ECMA language spec to take a look at Maps (Link). It seems that the behavior you are seeing is consistent with spec, and comes out of the spec'd definition for Map's delete prototype.

When a Map element is deleted with Map.prototype.delete(key), the spec only requires that the element with the matching key be set to empty.

Here's the definition copied and pasted from the ECMA spec:

3.1.3.3 Map.prototype.delete ( key )

The following steps are taken:

1. Let M be the this value.
2. Perform ? RequireInternalSlot(M, [[MapData]]).
3. Let entries be the List that is M.[[MapData]].
4. 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.
5. Return false.

The most important piece to us here is 4a.

When deleting an element, Map.prototype.delete checks each record p for an element where p.[[Key]] matches the provided key argument.

When found, p.[[Key]] and p.[[Value]] are both set to empty.

This means that, while the key and value are gone and are no longer stored or retrievable, the space, the element itself where the key and value were stored, may indeed be left in the Map's storage, and still takes up space behind the scenes.

While the specification contains the following note about its use of "empty"...

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.

...it's still leaving the door open for implementations to simply wipe the data without reclaiming the space, which is apparently what is occurring in your example here.

What about Map.prototype.set(key, value)?

In the case of set(), the function checks first for an existing element with a matching key to mutate the value of, and skips over all empty elements in the process. If none is found, then "Append p [<key, value>] as the last element of entries".

What, then, about Map.prototype.size?

In the case of size, the spec loops over all elements in the Map, and simply increments a counter for all non-empty elements it encounters.

---

I found this really interesting... If I had to hazard a guess, I suppose that the overhead of finding and removing empty elements is seen as unnecessary in most cases, since the quantities that must be reached to fill the structure are so large, ie. since maps hold so much. I wonder how large the time and space overhead of removing an empty element would be for a dataset large enough for it to be needed.

Julianejuliann

The excerpt from the spec is particularly revealing, thanks for this. I think that explains why removing keys doesn't really give the map more "room". I'm still curious why the map does reclaim space when 10M+ keys are removed, but it seems that behavior is not described in the spec and might be a consequence of the specific underlying implementation of Map. – Merilee

No, the spec does not encourage implementations to keep the memory slot around. This list data structure is purely a specification device, used as the simplest choice to describe the iteration order requirements of a mutable structure. In fact, "loops over all elements" and "checks each record p" are forbidden by the time complexity requirements. – Loper

(Yes, the spec does not detail memory de/allocation or garbage collection behaviour and intentionally leaves it open, allowing memory-leaking implementations, but attributing that to the entries list is misleading.) – Loper

I appreciate your link @Bergi, time complexity isn’t something I looked into, and it certainly would come into play here regarding why garage collection isn’t done immediately. – Julianejuliann

Gonna rewrite my previous comments for fear they came across as too defensive. I didn’t intend to imply that the spec encourages garbage collection free implementations, if that’s how it came across, but simply that this aspect of the spec probably helps account for, in part, the behavior the Asker observed, which seems strange without this knowledge. – Julianejuliann

@Loper You sound knowledgeable about this aspect of the spec, given the answer you linked. If looping over all elements is forbidden by List time complexity requirements, are you saying that that line of the spec on .size() is purely for illustration purposes rather than a detail on how to implement? I was under the impression that these steps were intended to be emulated by implementations mostly directly, otherwise I find it strange that they would be written into the descriptions at all. – Julianejuliann

@Julianejuliann Yes, I'd say the entries list is purely for illustration of the behaviour, not as a guide for implementation. Citing it as the reason for gc peculiarities of V8 (the specific implementation the question is about) seems wrong - that is, unless you can find evidence that the V8 authors did try to emulate it as closely as possible. – Loper

You should take a look at Pamphile’s answer which dives into V8 specifically a little more, and appears to confirm that deleted elements stick around for the immediate future, until some garbage collection action can be taken outside the course of standard Map operations. Having deleted elements, “holes” in the underlying data structure, would lend at least a little bit of credence to taking the implementation a little more by the letter. I’ll see if I can take a closer look later. – Julianejuliann

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;
      }
  }

 
}

Tannin

I don't see how this answers the question. OP does not want to clear the entire map, they want to remove only the first few values. Also it doesn't explain why they get an error. – Loper

I am not looking for a solution to a problem but an answer to a question. And also I want to reuse an old map not create a new one – Expurgatory