python - What is the meaning of hash if we still need to check every item?

Question

We know that tuple objects are immutable and thus hashable. We also know that lists are mutable and non-hashable.

This can be easily illustrated

>>> set([1, 2, 3, (4, 2), (2, 4)])
{(2, 4), (4, 2), 1, 2, 3}

>>> set([1, 2, 3, [4, 2], [2, 4]])
TypeError: unhashable type: 'list'

Now, what is the meaning of hash in this context, if, in order to check for uniqueness (e.g. when building a set), we still have to check each individual item in whatever iterables are there in the set anyway?

We know two objects can have the same hash value and still be different. So, hash only is not enough to compare objects. So, what is the point of hash? Why not just check each individual items in the iterables direrctly?

My intuition is that it could be for one of the reasons

1. hash is just a (pretty quick) preliminary comparison. If hashes are different, we know objects are different.
2. hash sinalizes that an object is mutable. This should be enough to raise an exception when comparing to other objects: at that specific time, the objects could be equal, but maybe later, they are not.

Am I in the right direction? Or am I missing important piece of this?

Thank you

标签： pythonpython-3.xhashtypesset

Answer 1

现在，在这种情况下，哈希的含义是什么，如果为了检查唯一性（例如，在构建集合时），我们仍然必须检查集合中的任何可迭代项中的每个单独项目？

是的，但是哈希用于保守估计两个对象是否相等，也用于将“桶”分配给一个项目。如果哈希函数经过精心设计，那么很可能（不确定）大多数（如果不是全部）最终会在不同的存储桶中，因此，我们会使用 membercheck/insertion/removal/... 算法平均在恒定时间内运行O(1)，而不是O(n)，这是典型的列表。

因此，您的第一个答案部分正确，尽管必须考虑到存储桶也肯定会提高性能，并且实际上比保守检查更重要。

背景

注意：这里我将使用一个简化的模型，使原理更清楚，实际上字典的实现更复杂。例如，这里的哈希只是一些显示原理的数字。

哈希集和字典被实现为“桶”数组。元素的哈希决定了我们将元素存储在哪个桶中。如果元素的数量增加，则桶的数量会增加，并且字典中已经存在的元素通常会“重新分配”给桶。

例如，一个空字典在内部可能看起来像：

+---+
|   |
| o----> NULL
|   |
+---+
|   |
| o----> NULL
|   |
+---+

所以两个桶，如果我们添加一个元素'a'，那么哈希是123。让我们考虑一个简单的算法来将一个元素分配给一个桶，这里有两个桶，所以我们会将具有偶数哈希的元素分配给第一个桶，将奇数哈希分配给第二个桶。由于 的散列'a'是奇数，因此我们分配'a'给第二个桶：

+---+
|   |
| o----> NULL
|   |
+---+
|   |   +---+---+
| o---->| o | o----> NULL
|   |   +-|-+---+
+---+    'a'

所以这意味着如果我们现在检查是否'b'是字典的成员，我们首先计算hash('b')，即456，因此如果我们将它添加到字典中，它将在第一个桶中。由于第一个桶是空的，我们永远不必寻找第二个桶中的元素来确定它'b'不是一个成员。

如果我们然后例如要检查是否'c'是成员，我们首先生成 的哈希'c'，即789，因此我们再次将其添加到第二个桶中，例如：

+---+
|   |
| o----> NULL
|   |
+---+
|   |   +---+---+   +---+---+
| o---->| o | o---->| o | o----> NULL
|   |   +-|-+---+   +-|-+---+
+---+    'c'         'a'

因此，现在如果我们再次检查是否'b'是成员，我们将查看第一个存储桶，并且再一次，我们不必迭代'c'并'a'确定它'b'不是字典的成员。

现在当然有人可能会争辩说，如果我们继续添加更多的字符，比如'e'和'g'（这里我们认为这些有一个奇怪的哈希），那么这个桶就会变得很满，因此如果我们稍后检查是否'i'是一个成员，我们仍然需要迭代元素。但是如果元素数量增加，通常桶的数量也会增加，并且字典中的元素将被分配一个新的桶。

例如，如果我们现在要添加'd'到字典中，字典可能会注意到插入后的元素数3大于桶数2，因此我们创建一个新的桶数组：

+---+
|   |
| o----> NULL
|   |
+---+
|   |
| o----> NULL
|   |
+---+
|   |
| o----> NULL
|   |
+---+
|   |
| o----> NULL
|   |
+---+

我们重新分配成员'a'和'c'。现在所有带有哈希h的元素h % 4 == 0都将被分配给第一个桶、h % 4 == 1第二个桶、h % 4 == 2第三个桶和h % 4 == 3最后一个桶。这意味着'a'with hash123将存储在最后一个桶中，而'c'with hash789将存储在第二个桶中，所以：

+---+
|   |
| o----> NULL
|   |
+---+
|   |   +---+---+
| o---->| o | o----> NULL
|   |   +-|-+---+
+---+    'c'
|   |
| o----> NULL
|   |
+---+
|   |   +---+---+
| o---->| o | o----> NULL
|   |   +-|-+---+
+---+    'a'

然后我们将'b'哈希添加456到第一个桶中，所以：

+---+
|   |   +---+---+
| o---->| o | o----> NULL
|   |   +-|-+---+
+---+    'b'
|   |   +---+---+
| o---->| o | o----> NULL
|   |   +-|-+---+
+---+    'c'
|   |
| o----> NULL
|   |
+---+
|   |   +---+---+
| o---->| o | o----> NULL
|   |   +-|-+---+
+---+    'a'

因此，如果我们要检查 的成员关系'a'，我们计算哈希，知道如果'a'在字典中，我们必须在第三个桶中搜索，并且会在那里找到它。如果我们寻找'b'或'c'发生同样的事情（但使用不同的存储桶），并且如果我们寻找'd'（这里使用 hash 12），那么我们将在第三个存储桶中搜索，并且永远不必检查单个元素的相等性来知道它不是字典的一部分。

如果我们要检查是否'e'是成员，那么我们计算'e'（这里345）的哈希，并在第二个桶中搜索。由于那个桶不是空的，我们开始迭代它。

对于桶中的每个元素（这里只有一个），算法将首先查看我们搜索的键是否与节点中的键引用相同的对象（但是两个不同的对象可以相等），因为这是并非如此，我们还不能声称它'e'在字典中。

接下来我们将比较我们搜索的键的哈希值和节点的键。大多数字典实现（如果我没记错的话，还有 CPython 的字典和集合），然后也将散列存储在列表节点中。所以这里它检查是否345等于789，因为不是这样，我们知道'c'和'e'不一样。如果比较这两个对象的成本很高，那么我们可以节省一些周期。

如果哈希值相等，这并不意味着元素相等，所以在这种情况下，我们将检查两个对象是否相等，如果是，我们知道元素在字典中，否则，我们知道事实并非如此。