python - Does JavaScript use hashtables for Map and Set? - Stack Overflow

admin管理员组

文章数量:1290981

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?

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?

• javascript
• python
• dictionary
• set
• hashtable

Share Improve this question Follow asked Oct 1, 2020 at 8:38 Ram RachumRam Rachum 88.7k8686 gold badges255255 silver badges386386 bronze badges 3

• 4 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. – juanpa.arrivillaga Commented Oct 1, 2020 at 8:40
• 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. – VLAZ Commented Oct 1, 2020 at 8:48
• 1 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. – VLAZ Commented Oct 1, 2020 at 8:50

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 8

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 pare 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"

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

本文标签： pythonDoes JavaScript use hashtables for Map and SetStack Overflow