How do Maps hash object references in JavaScript?

Question

A standard JavaScript object is presumably implemented like a hashmap in every other language — hash of the key modulus the size. This works great for objects, not so much for Maps, as keys can be mutable objects.

Initially, I assumed it would hash the address of the key. Great! However, the address is not static either. When an array or object grows beyond its capacity, it is reallocated in a new memory location.

Given that my "logical" assumption is wrong, how are Maps implemented? Something must be hashed to provide O(1) lookup.

NB: This is not the same as a hashmap, dictionary, or whatever else you'd like to call it. This is specific to the Map object in JavaScript.

Before others inevitably ask, yes I've searched. I'm unable to find anything, either on Stack Overflow or other sites. — jhpratt
– jhpratt, Commented Jul 23, 2018 at 20:56
Possible duplicate of How is a JavaScript hash map implemented? — chevybow
– chevybow, Commented Jul 23, 2018 at 20:56
@chevybow Not the same. Map is a specific type of object, and is not the same as a standard object in JS. — jhpratt
– jhpratt, Commented Jul 23, 2018 at 20:57
Note that "moving memory", e.g. after garbage collection, needs to update references anyways - imagine having an array in a variable, and the physical data changes position. I don't know how implementations handle this (and you did not mention which implementation you are concerned about), but they likely either hash some metadata for the reference (like some ID), or update everything when memory is moved (unlikely, because costly). — ASDFGerte
– ASDFGerte, Commented Jul 23, 2018 at 21:02

JLRishe · Accepted Answer · 2018-07-24 03:40:17Z

Here's what ECMAScript-262 standard (June 2018 edition) says:

23.1 Map Objects

Map objects are collections of key/value pairs where both the keys and values may be arbitrary ECMAScript language values. A distinct key value may only occur in one key/value pair within the Map's collection. Distinct key values are discriminated using the SameValueZero comparison algorithm.

Map object 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 structures used in this Map objects specification is only intended to describe the required observable semantics of Map objects. It is not intended to be a viable implementation model.

The last statement in the statement above states that the Javascript standard itself is agnostic about the mechanism used to implement Map. It only requires that the lookup/update operations on a Map run in sub-linear (i.e. typically O(log(N)) ) time.

Collectives™ on Stack Overflow

How do Maps hash object references in JavaScript?

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related