Does JavaScript use hashtables for Map and Set?

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


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"