CODEWITHSUNDEEP
javascriptpythondictionarysethashtable
Ram Rachum
Ram Rachum

Reputation: 88648

Does JavaScript use hashtables for Map and Set?

I'm a Python developer, making my first steps in JavaScript.

I started using Map and Set. They seem to have the same API as dict and set in Python, so I assumed they're a hashtable and I can count on O(1) lookup time.

But then, out of curiosity, I tried to see what would happen if I were to do this in Chrome's console:

new Set([new Set([1, 2, 3])])

What happens is this:

Set(1) {Set(3)}

JavaScript happily creates the set. How can this be? In Python you would have gotten an error since you can't put a mutable item in a set or a dict. Why does JavaScript allow it?

Upvotes: 12

Views: 2006

Answers (2)

gurisko
gurisko

Reputation: 1182

The internal representation of these data structures depends on the engine running your code (such as V8 or Chakra). However, the specification requires the engines to implement these structures in

mechanisms that [...] provide access times that are sublinear on the number of elements in the collection.

From ECMAScript® 2021 Language Specification - 23.1 Map Objects

Upvotes: 3

juanpa.arrivillaga
juanpa.arrivillaga

Reputation: 96098

Consider the following JS code:

> m1 = new Map([['a', 1]])
Map { 'a' => 1 }
> m2 = new Map()
Map {}
> m2.set(m1, 3)
Map { Map { 'a' => 1 } => 3 }
> m2.get(m1)
3

But note, it is hashing based on identity, i.e. ===, so...

> m2.get(new Map([['a',1]]))
undefined

So really, how useful is this map?

Note, this isn't different than Python's default behavior. The default status of user-defined type is being hashable:

>>> class Foo: pass
...
>>> f0 = Foo()
>>> s = {f0}
>>> Foo() in s
False
>>> f0 in s
True

In Python, by default, object.__eq__ will compare based on identity, so the above is fine. However, if you override __eq__, by default, __hash__ is set to None and trying to use a hashing-based container will fail:

>>> class Bar:
...    def __init__(self, value):
...       self.value = value
...    def __eq__(self, other):
...       return self.value == other.value
...
>>> b0 = Bar(0)
>>> b1 = Bar(2)
>>> {b0, b1}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'Bar'

At this point, you must implement __hash__ to be consistent with __eq__, and note, though, that your user-defined object is never really very "immutable"

Upvotes: 8

Related Questions