JavaScript使用哈希表来实现Map和Set吗？

Question

JavaScript使用哈希表来实现Map和Set吗？

12

我是一名Python开发者，正在学习JavaScript的基础知识。

我开始使用Map和Set。它们似乎有着与Python中的dict和set相同的API，因此我认为它们是哈希表并且可以保证O(1)的查找时间。

但出于好奇心，我尝试在Chrome控制台中执行以下操作：

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

发生的情况是这样的:

Set(1) {Set(3)}

JavaScript可以愉快地创建集合。这是为什么呢？在Python中，您会收到一个错误，因为您不能将可变项放入集合或字典中。为什么JavaScript允许它？

- Ram Rachum

4

因为JavaScript允许对可变数据类型进行哈希，这并不是不可能的，但非常不建议，以至于Python不允许这样做。当然，在Python中，您可以定义自己的可变和可哈希的自定义类型。但请注意，对象是通过其身份进行哈希处理，因此它并不是非常危险，但也不是非常有用。 - juanpa.arrivillaga

JS允许它，因为它允许它。请注意，Java和C#也允许可变项放入哈希桶中。当然，如果它们的哈希标识不稳定，这可能会导致问题，这可能是Python试图避免的，但是在这里，JS肯定没有做任何与众不同的事情。实际上，在某些方面，JS通过不允许对象的哈希标识更改来缓解了一些问题-它始终是对象的引用，这避免了将对象排序到一个哈希桶中后“丢失”对象的问题，然后代码在另一个哈希桶中查找它。 - VLAZ

1

然而，这样做也会带来其他问题，因为如果没有实际的对象，就不能在哈希集合中查找对象。使用自定义哈希标识可以通过构造散列到相同值的东西来查找它。因此，这种方法有其优点和缺点，但再次强调，这并不是不正常的。 - VLAZ

2个回答

3

这些数据结构的内部表示取决于运行代码的引擎（例如V8或Chakra）。然而，规范要求引擎使用机制来实现这些结构，以便在集合中的元素数量上呈次线性的访问时间。来源于 ECMAScript® 2021 Language Specification - 23.1 Map Objects。

- gurisko

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- juanpa.arrivillaga · Accepted Answer

以下是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的默认行为没有区别。用户定义类型的默认状态是可哈希的：

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

在 Python 中，默认情况下，object.__eq__ 是基于对象标识进行比较的，因此上述代码是可行的。但是，如果你重写了 __eq__，默认情况下，__hash__ 会被设置为 None，并且在尝试使用哈希容器时会失败：

>>> 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__以保持一致性，并注意，虽然您的用户定义对象从未真正变得非常“不可变”