JavaScript 是否对 Map 和 Set 使用哈希表？

Question

我是一名 Python 开发人员，正在 JavaScript 迈出第一步。

我开始使用 Map and Set。它们似乎具有与 Python 中的 dict 和 set 相同的 API，因此我假设它们是一个哈希表，我可以指望 O(1) 查找时间。

但是，出于好奇，我试图看看如果我在 Chrome 的控制台中执行此操作会发生什么：

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

这是怎么回事：

Set(1) {Set(3)}

JavaScript愉快地创建了集合。怎么会这样？在 Python 中，你会得到一个错误，因为你不能将可变项放入集合或字典中。为什么 JavaScript 允许它？

Answer 1

考虑以下 JS 代码：

> 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

但是请注意，它是基于身份的散列，即 ===，所以...

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

说真的，这张地图有多大用处？

请注意，这与 Python 的默认行为没有什么不同。 user-defined 类型的默认状态是可哈希的：

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

在Python中，默认情况下，object.__eq__会根据身份进行比较，所以上面的就可以了。但是，如果您覆盖 __eq__，默认情况下，__hash__ 设置为 None 并且尝试使用 hashing-based 容器将失败：

>>> 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'

此时，您必须实现 __hash__ 以与 __eq__ 保持一致，但请注意，您的 user-defined 对象从来都不是真正的“不可变”[=21] =]

Answer 2

这些数据结构的内部表示取决于引擎运行您的代码（例如 V8 或 Chakra）。但是，规范要求引擎在

中实现这些结构

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

来自ECMAScript® 2021 Language Specification - 23.1 Map Objects

JavaScript 是否对 Map 和 Set 使用哈希表？

Does JavaScript use hashtables for Map and Set?

javascript

python

dictionary

hashtable

set