python - 如果我们仍然需要检查每个项目，哈希的含义是什么？

Question

我们知道tuple对象是不可变的，因此是散列的。我们还知道lists是可变的和不可散列的。
这很容易说明

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

现在，在这个上下文中hash的含义是什么，如果为了检查唯一性（例如，在构建集合时），我们仍然必须检查集合中的任何iterable中的每个单独项？
我们知道两个对象可以具有相同的hash值，但仍然是不同的。因此，hash仅用于比较对象是不够的。那么，散列的意义是什么？为什么不直接检查iterables中的每个项目呢？
我的直觉是这可能是因为
hash只是一个（很快）的初步比较。如果hashes不同，我们知道对象是不同的。
表示对象是可变的。当与其他对象比较时，这应该足以引发一个异常：在特定的时间，对象可以是相等的，但也许以后，它们不是。
我的方向对吗？还是我错过了重要的一部分？
谢谢你

Answer 1

现在，hash在这个上下文中的意义是什么，如果，为了检查唯一性（例如，在构建集合时），我们仍然必须检查集合中的任何iterable中的每个单独项？
是的，但是哈希用于两个对象可以相等的情况下进行保守估计，也用于分配一个“桶”到一个项目。如果哈希函数是精心设计的，那么很可能（不确定），大多数，如果不是全部，最终在不同的桶，因此，因此，我们使成员检查/插入/删除/…算法平均运行在恒定时间O（1），而不是O（n），这是典型的列表。
所以，你的第一个答案是部分正确的，尽管你必须考虑到桶肯定会提高性能，而且实际上比保守检查更重要。
背景
注：我将在这里使用一个简化的模型，使原理清晰，实际上字典的实现更为复杂。例如散列在这里只是一些数字，显示了普林西比。
哈希集和字典被实现为一个“bucket”数组。元素的散列决定了我们将元素存储在哪个bucket中。如果元素的数量增加，那么bucket的数量就会增加，字典中已经存在的元素通常会被“重新分配”到bucket中。
例如，空字典在内部可能看起来像：

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

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

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

所以这意味着如果我们现在检查'b'是否是字典的成员，我们首先计算hash('b')，也就是456，因此如果我们把它添加到字典中，它将在第一个bucket中。因为第一个bucket是空的，所以我们不必在第二个bucket中寻找元素来确定'b'不是成员。
例如，如果我们想检查'c'是否是一个成员，我们首先生成'c'的散列，即789，因此我们再次将其添加到第二个bucket，例如：

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

因此，现在如果我们再次检查'b'是否是一个成员，我们将查看第一个bucket，然后，我们再也不必遍历'c'和'a'来确定'b'不是字典的成员。
当然，现在有人可能会争辩说，如果我们继续添加更多的字符，比如'e'和'g'（这里我们认为这些字符有一个奇怪的散列），那么这个bucket将非常满，因此如果我们稍后检查'i'是否是成员，我们仍然需要遍历元素。但是，如果元素的数量增加，通常存储桶的数量也会增加，并且字典中的元素将被分配一个新的存储桶。
例如，如果我们现在想将'd'添加到字典中，字典可能会注意到插入后的元素数3大于桶的数量2，因此我们创建了一个新的桶数组：

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

我们重新分配成员'a'和'c'。现在所有具有哈希< cc> > h的元素将被分配给第一个桶，h % 4 == 0到第二个桶，h % 4 == 1到第三个桶，并且h % 4 == 2到最后一个桶。这意味着hashh % 4 == 3的'a'将存储在最后一个bucket中，hash123的'c'将存储在第二个bucket中，因此：

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

然后将hash789的'b'添加到第一个bucket中，这样：

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

因此，如果我们想检查cc的成员数，我们计算散列，知道如果在字典中是cc，我们必须在第三个桶中搜索，并在那里找到它。如果我们寻找456或'a'，也会发生同样的情况（但是使用不同的桶），如果我们寻找'a'（这里用哈希'b'），那么我们将在第三个桶中进行搜索，并且永远不必检查单个元素的相等性，以知道它不是字典的一部分。
如果我们想检查'c'是否是一个成员，那么我们计算'd'的散列（这里是12），并在第二个bucket中搜索。因为bucket不是空的，所以我们开始遍历它。
对于桶中的每个元素（这里只有一个元素），算法首先查看我们搜索的密钥，而节点中的密钥引用相同的对象（两个不同的对象可以是相等的），因为情况并非如此，我们不能声称'e'在字典中。
接下来我们将比较我们搜索的密钥的散列和节点的密钥。大多数字典实现（如果我正确地回忆了），也可以将散列存储在列表节点中。因此，这里检查是否'e'等于< > >，因为事实并非如此，我们知道345和< >是不一样的。如果比较这两个对象比较昂贵，那么我们可以节省一些周期。
如果散列是相等的，这并不意味着元素是相等的，因此，在这种情况下，我们将检查这两个对象是否相等，如果是这样的话，我们知道元素在字典中，否则，我们知道它不是。