8

I think this question was not asked before. It is about Javascript Map:

var myMap = new Map();

What is the relationship between a Javascript Map and a hash table? Is Map an implementation of a hash table?

Improve this question
2

1 Answer 1

Reset to default
14

From the specification:

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.

So it's up to the implementation of the JavaScript engine¹, but it must be implemented in a way that delivers the same sorts of benefits using hash tables would, so using hash tables would be a sensible approach for an implementation to take. The spec specifically forbids implementing Map such that looking up an entry involves a linear search through the elements.

¹ The specification says how Map objects must behave. JavaScript engines (V8 in Chrome and Chromium and Node.js, SpiderMonkey in Firefox, JavaScriptCore in Safari, Chakra in Edge...) implement that behavior. How they do so is up to them, provided they do it in a way that's consistent with the specification.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Thanks! Hm, I think I'm confused now by the term «implementation». I though that Map was already an implementation. So calling Map() would create an instance of it without the need of implementing anything else. Where I'm wrong?
People who create JavaScript engines (like V8 that is inside Google Chrome, or like Chakra that is in MS Edge, etc) implement JavaScript Map behaviour in C or whatever language they use to create their JS engine. The spec says if you are making a new browser (or a new browser-less engine), your Map must be faster than looking through every element and comparing the key.
The 'implementation' means how JS is compiled and execuded in the browser, which uses a low-level language, mostly, AFAIK, C++.
So the instructions of the specification are about how Map() should be compiled and executed… Now I get it :)
Thanks @T.J.Crowder! Now it is clear. So I when we call new Map() we are asking to the engine to create an object with the behaviour described in the Javascript specification, regardless the way this behaviour is generated. And a Map could be created with different types of structures and logics, being a hash table one of them.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.