Hashmaps and Time Complexity

Question

My understanding is ES6 Map object can implement a Hashmap in Javascript. Is that correct?
indexOf method in arrays has an O(n) time complexity.
Does has method in Maps have O(1) time complexity? If yes why? How JS can find an element in a Map object in one step? How it works differently than indexOf? If not having an O(1) then Es6 Map is not a real Hashmap...

From the spec: *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.* — Pointy, Jan 28 '21 at 16:59
As with most other such things in JavaScript, precise implementation details are not part of the spec. — Pointy, Jan 28 '21 at 17:00
There is a whole range of time complexities between *O(1)* and *O(n)*. Don't make this a binary choice. — trincot, Jan 28 '21 at 17:07
https://stackoverflow.com/questions/33611509/es6-map-and-set-complexity-v8-implementation — Daphoque, Feb 01 '21 at 13:56
I'm not sure why you bring the `indexOf` time complexity into this question. It's completely unrelated to hashMaps (and will inevitably be `O(n)`, in any language, because there's no "better" way to do it than naively check every index of the array/list for the desired value). — Robin Zigmond, Feb 01 '21 at 17:57

Menelaos · Accepted Answer · 2021-02-06T03:31:19.273

My understanding is ES6 Map object can implement a Hashmap in Javascript. Is that correct?

No, it's not correct the way it is phrased. When you say implement you remind me of interfaces and languages like java. In Java, there is the interface map and then there are different implementations like hashmap, treemap, etc.

In the case of javascript, you could use map (or you could even use an array), to implement a hashmap (or hashtable) algorithm.

Do note that in some browsers like v8, map is already built using hashtables so it is already a hashmap. Unfortunately, the ECMAScript 2015 specification (see https://262.ecma-international.org/6.0/#sec-map-objects ) does not specify or dictate the exact implementation. Instead, it is quite open ended allowing each browser or javascript engine to have a compatible implementation.

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.

If a hashtable is used, then it is a hashmap (not the same exactly as java), but the underlying implementation depends on the actual browser.

Note/FYI: Maps in google's V8 engine are built on top of hash tables.

indexOf method in arrays has an O(n) time complexity.

Yes. You cannot do better than O(n) in a random unsorted array.

Does has method in Maps have O(1) time complexity?

Usually yes. Considering that the map uses hashtables (or somethling like hashtables). Additionally, there has to be:

descent hash function that is constant time and doesn't take long to compute
not too many collisions because we would then have to iterate through multiple items that had the same hash code.

O(1) isn't always guaranteed, and the worst case scenario of O(N) is quite unlikely.

Have a look @ the theory behind hashmaps and hashtables :

How JS can find an element in a Map object in one step?

Map uses a hashtable (or a similar mechanism) as specified in the spec. Therefore, when an object is requested a hash is calculated. Then the specific location in an internal table is located. This is the basic theory about hash tables and why they are usualy O(1). Do note, that if there are many collisions performance can move towards O(N).

See: https://stackoverflow.com/a/9214594/1688441 from Hash table runtime complexity (insert, search and delete)

Hash tables are O(1) average and amortized case complexity, however it suffers from O(n) > worst case time complexity. [And I think this is where your confusion is]

That excellent answer lists the situations of worst cases.

How it works differently than indexOf

Hashtables use a hash and do a lookup inside a table/array. Instead, indexOf searches step by step within an array/collection/string. See: https://262.ecma-international.org/5.1/#sec-15.4.4.14

If not having an O(1) then Es6 Map is not a real Hashmap

This is not correct. A hashmap can have a worst-case performance of O(N). There is an excellent wikipedia article about hashmap/hashtable with an excellent table: (from: https://en.wikipedia.org/wiki/Hash_table )