2

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.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
jhpratt
  • 6,841
  • 16
  • 40
  • 50
  • Before others inevitably ask, yes I've searched. I'm unable to find anything, either on Stack Overflow or other sites. – jhpratt Jul 23 '18 at 20:56
  • Possible duplicate of [How is a JavaScript hash map implemented?](https://stackoverflow.com/questions/8877666/how-is-a-javascript-hash-map-implemented) – chevybow Jul 23 '18 at 20:56
  • 2
    @chevybow Not the same. `Map` is a specific type of object, and is _not_ the same as a standard object in JS. – jhpratt Jul 23 '18 at 20:57
  • Maybe you've seen them, but there are few resources linked here: https://stackoverflow.com/questions/33611509/es6-map-and-set-complexity-v8-implementation & https://stackoverflow.com/questions/34328136/are-javascript-map-objects-indexed-to-optimize-map-get – Mark Jul 23 '18 at 20:58
  • 2
    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 Jul 23 '18 at 21:02
  • 3
    You'd have to look at V8's or SpiderMonkeys source code. – Felix Kling Jul 23 '18 at 21:23
  • _“as keys are mutable”_ — as long as the _reference_ of the mutable object stays the same, this may not be a problem. You only need to hash the reference, not the contents. – Sebastian Simon Jul 23 '18 at 22:57
  • @Xufox Yes, but the can't the address also change, when it grows beyond capacity? – jhpratt Jul 23 '18 at 22:58
  • @jhpratt The allocator / garbage collector usually provides some kind of hashable reference for this – Bergi Jul 24 '18 at 08:27
  • @Bergi If you've got a source for that, I'd be happy to accept it as an answer. – jhpratt Jul 24 '18 at 11:27
  • I don't know if V8 actually does this, but an efficient way to handle hashing objects that can move is to store the hash code in an internal property of the object. – Barmar Mar 04 '21 at 07:17

1 Answers1

0

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.

JLRishe
  • 99,490
  • 19
  • 131
  • 169
balajeerc
  • 3,998
  • 7
  • 35
  • 51