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 )
- https://en.wikipedia.org/wiki/Hash_table
- Hash table runtime complexity (insert, search and delete)
