0

I just want to understand how javascript ES6 Maps (i.e. let m = new Map()) has 0(1) lookup time. My understanding of ES6 Maps is that its data structure is based on an array of tuples. You can even use an array of tuples in the constructor for Maps. Basically, my questions is:

How is

let t = [[1,'hi'], [2,'bye']]

Different than

let m = new Map([[1,'hi'], [2,'bye']])

The first case would clearly prevent constant lookup. How do ES6 maps achieve constant lookup? What is their underlying data structure?

Eric Grossman
  • 219
  • 1
  • 4
  • 9
  • Map is more like `{1:'hi', 2:'bye'}` where each key is a property of the object – charlietfl Aug 22 '20 at 15:30
  • `Map` is like an Object but it can have any value as a key, not just strings and symbols. – marzelin Aug 22 '20 at 15:39
  • "*its data structure is based on an array of tuples*" - no. That its constructor takes data in that format (actually, any iterable of tuples) doesn't mean anything about the internal data structure, which is a (hash) lookup map. – Bergi Aug 22 '20 at 15:40
  • @Bergi then how is order preserved? – Eric Grossman Aug 23 '20 at 19:50
  • 1
    @EricGrossman There are many approaches, the easiest is to use a separate list of entries in the insertion order next to the hash-positioned entries. It seems this is [what V8 uses](https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables) (or at least did in the past). – Bergi Aug 23 '20 at 20:08

2 Answers2

1

A reasonable assumption maybe that to use an Hash-Map data-structure for O(1) lookup.

It also maybe that the first element in a tuple of a Map maybe mapped with the index of the array using an Object in key value pairs. So when a particular key is called it may refer this object.

Charles
  • 227
  • 1
  • 5
-1

Map is similar to Object , And keys in map are stored in Order which is not in the case of Object. It's a iterable datastructire again , shich is not in Object. So its achieve constant lookup.

Asutosh
  • 1,775
  • 2
  • 15
  • 22