3

What is time complexity of basic operation in Set & Map in javascript?

Are they in hashmaps or BSTs?

Sascha
  • 4,576
  • 3
  • 13
  • 34
Jeong Ho Nam
  • 803
  • 12
  • 20
  • 4
    The spec calls for implementations to provide sub-linear access times. Exact details are left to each individual implementation. – Pointy Aug 03 '20 at 12:24
  • 1
    As far as I'm aware, most (if not all) implementations use hashes, so the access is `O(1)`. However, the spec doesn't mandate that, so it's possible to have a BST backed implementation. – VLAZ Aug 03 '20 at 12:29

1 Answers1

1

According to the ECMA documentation for Set and Maps (http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-objects):

Set objects 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 Set objects specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

enter image description here

enter image description here

enter image description here

You will find similar sentences for Maps, WeakMaps and WeakSets. So, you should expect the time-complexity to be sublinear. Also, you can check out a solution on Javascript ES6 computational/time complexity of collections

Vishal Kotak
  • 422
  • 4
  • 11