为什么使用哈希而不是测试真正的相等性？

Question

我最近研究了Python的字典（我相信它们在其他语言中被称为关联数组），并对其键的一些限制感到困惑。你知道吗

首先，dict键必须是不可变的。当我查看它背后的逻辑时，答案是字典就像哈希表一样查找键的值，因此不可变键（如果它们是可哈希的）可能会更改它们的哈希值，从而在检索值时产生问题。你知道吗

我很清楚为什么会这样，但我还是有点搞不懂使用哈希表的意义。如果您只是不散列键并测试真正的相等性（假设相同构造的对象比较相等），那么您可以通过使用两个列表来复制字典的大部分功能，而不受此限制。你知道吗

所以，我想这是我真正的问题-使用哈希值而不是相等值背后的原理是什么？你知道吗

如果非要我猜的话，很可能只是因为比较整数的速度非常快而且优化了，而比较其他类的实例可能不是。你知道吗

Answer 1

您似乎忽略了哈希表的全部要点，它是快速（O（1））¹检索，并且如果没有哈希，就无法实现，即将键转换为某种分布良好的整数，用作表的索引。请注意，在检索时仍然需要相等，以便能够处理哈希冲突²，但只有在已将元素集缩小到具有特定哈希的元素集时，才能使用相等。你知道吗

只要相等，就可以用并行数组或类似的东西复制类似的功能，但这将使检索O（n）³；如果要求严格的弱排序，则可以实现RB树，它允许O（logn）检索。但是O（1）需要散列。你知道吗

查看Wikipedia以了解有关哈希表的更多信息。你知道吗

---

注意事项

1. 在病态的情况下（所有元素都放在同一个桶中），它可能变成O（n），但这在一个好的哈希函数中是不应该发生的。你知道吗
2. 由于不同的元素可能具有相同的散列，因此在到达与散列对应的bucket之后，必须检查是否实际检索与给定键关联的元素。你知道吗
3. 或者O（logn），如果您保持数组排序，但这会使插入复杂化，由于元素的移动，插入变得平均O（n）；但是，如果您有排序，那么您可能需要RB树或堆。你知道吗

Answer 2

通过使用hastables，您可以实现O(1)检索数据，而与每个独立值进行相等比较时，将采用O(n)（在顺序搜索中）或O(log(n))（在二进制搜索中）。你知道吗

还请注意，O(1)是摊销时间，因为如果有多个值散列到同一个键，则需要在这些值之间进行顺序搜索。你知道吗