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"