Does JavaScript use hashtables for Map and Set?

Question

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?

Dime

Because JS lets you hash mutable types. That isn't impossible just inadvisable enough that Python doesn't let you do it. Of course, in Python, you can define your own custom types that are mutable and hashable. But, note, objects are hashed by identity, so it's not terribly dangerous, but it is not very useful. – Chloe

JS allows it because it allows it. Note that Java and C# also allow mutable items to be put in hash buckets. This can lead to problems if their hash identity is unstable, of course, which is probably what Python tries to avoid, however, JS is certainly not doing anything out of the ordinary here. In fact, in some respects JS mitigates some of the problems by not allowing the hash identity of the object to change - it's always the object's reference, which avoids the issue of "loosing" the object after it's sorted into one hash bucket and it then changes so the code looks for it in another. – Too

Then again, that creates other problems, since you cannot look for an object in a hash set without actually having the object. A custom hash identity would allow you to find it by constructing something that hashes to the same value. So, the approach has positives and negatives but, again, it's not in any way abnormal. – Too

Answer 1

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"

Chloe

"So really, how useful is this map?" it can be used as a decoupled and quite cheap way to add meta information to objects without modifying the objects themselves. In fact, a map where the key is also a map is a perfect illustration - you cannot even change the Map class. You can use the same approach with other third party objects to allow you to enrich them without ever touching them. Add the objects to a map as a key, add whatever data you want for them as a value (could even be functions/methods) and then fetch that meta information from the map using your object. – Too

@Too you probably want to use a WeakKeyMap for that however, otherwise your attributes table may grow unbounded. For a more ECS-ish system you'd be keying on IDs not arbitrary objects. – Psalter

@Psalter yes, it depends on what exactly you want to do with this. I was pointing out how it could be useful. Too often I see people claiming that putting objects in a map/set is never useful. Since the answer touched slightly on that by asking the question, I wanted to provide an example. I thought I didn't need to specify that you would need to consider your scenario before using this approach. – Too

@Too another example of where identity-based membership is useful would be something like using a Set to keep track of visited nodes in some graph structure. – Chloe

@Chloe I was experimenting with Map now, and I see that if you add a Map as a key, it accepts it, but then if you try to use any other map as a key for the first map, it gives you the value for the second map. It's as if the only thing it cared about was the type of the object and not its contents. What's going on here? – Dime

@RamRachum showing the code you tried might clarify things. I am currently not sure what you've actually done, so I don't know what behaviour you experience. – Too

@RamRachum it cares about the identity of the object, not its contents. – Chloe

@Too Here's the code: gist.github.com/cool-RR/036b9e6f7ce3f448b275eeb4f707ab8f This is crazy. – Dime

@Chloe Check out the code above. Did the two small maps share the same identity? – Dime

Ah, my mistakes were not using set and get. – Dime

@RamRachum yes, so you are adding attributes, which converts to the string representation (don't worry, I did a double-take too, I'm a Python person as well :) ) – Chloe

Answer 2

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

Scruggs