Map.get() implementation algorithm

[anthumchris]

When retrieving values from a Map/WeakMap, does Chromium's Map.get(key) implement a O(1) hash lookup or is the retrieval O(n) by traversing all of the keys in the Map until the key is found?

The Map.get() ECMA spec states "For each Record...do...", which indicates O(n) traversal, while the Map Objects ECMA spec states "Maps must be implemented using either hash tables or other mechanisms...".

[Claudia]

Most implementations implement that as amortized O(1) to my knowledge. This includes runtimes in every major browser, including Chromium/Blink.

There's other cases where things are almost implemented differently to the spec in practice, like:

• Using bytecode and virtual/actual machine instructions instead of AST interpretation
• Using libc builtins for certain typed array operations
  
• Storing ASCII strings using 8-bit characters instead of 16-bit characters
• Using bytecode instead of continuations for regular expressions
• Doing direct bit manipulation for `Math.sign` and `Math.abs`
• Sidestepping the Promise constructor factory for literal `Promise.resolve()`/`Promise.reject()`
• Not reifying `arguments` or spread arguments unless the object is directly stored or is needed in a closure

This of course is not exhaustive. It's just showing some of the many ways implementors optimize things.

[Jakob Kummerow]

If you read the full paragraph of which you quoted the beginning, it pretty much answers your question:

Maps must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of Maps. It is not intended to be a viable implementation model.

So an implementation based on O(n) traversal (actually Ω(n) if we're being precise) would not be spec compliant.

In practice, V8's implementation of Map is hash-based and hence O(1).

Another viable option would be a tree-based implementation, which would give O(log(n)) access times. That difference may or may not matter in practice. Trees may or may not use a little less memory than hash tables, depending on specific implementation details.

On Wed, Apr 24, 2024 at 9:26 PM anthumchris <ch...@anthum.com> wrote:

When retrieving values from a Map/WeakMap, does Chromium's Map.get(key) implement a O(1) hash lookup or is the retrieval O(n) by traversing all of the keys in the Map until the key is found?

The Map.get() ECMA spec states "For each Record...do...", which indicates O(n) traversal, while the Map Objects ECMA spec states "Maps must be implemented using either hash tables or other mechanisms...".

--