如果我们还需要检查每个项目,hash的含义是什么？

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在这种情况下,如果为了检查唯一性(例如,在构建集合时),我们仍然必须检查集合中的任何迭代中的每个单独项目吗？

我们知道两个对象可以具有相同的hash值,但仍然不同.所以,hash仅仅不足以比较对象.那么,哈希的重点是什么？为什么不直接检查迭代中的每个项目？

我的直觉是它可能是其中一个原因

1. hash只是一个(很快)的初步比较.如果hashes不同,我们知道对象是不同的.
2. hash确定一个对象是可变的.这应该足以在与其他对象进行比较时引发异常:在该特定时间,对象可能相等,但可能稍后,它们不是.

我是朝着正确的方向吗？或者我错过了重要的一部分？

谢谢

Answer 1

现在,在这个上下文中hash的含义是什么,如果为了检查唯一性(例如在构建集合时),我们仍然必须检查集合中的每个单独项目是否仍然存在？

是的,但如果两个对象可以相等,则哈希用于进行保守估计,并且还用于为项目分配"桶".如果小心地设计了散列函数,那么很可能(不确定)大多数(如果不是全部)最终都在另一个桶中,因此,我们因此制作了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'哈希123将存储在最后一个桶中,并且'c'哈希789将存储在第二个桶中,因此:

+---+
|   |
| 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'(这里使用哈希12),那么我们将在第三个桶中搜索,并且永远不必检查与单个元素的相等性以便知道它不是字典的一部分.

如果我们想检查是否'e'是成员,那么我们计算'e'(这里345)的哈希值,并在第二个桶中搜索.由于该存储桶不为空,我们开始迭代它.

对于桶中的每个元素(这里只有一个),算法将首先查看我们搜索的密钥,并且节点中的密钥引用同一个对象(但是两个不同的对象可以相等),因为这是不是这样,我们还不能声称这'e'是在字典里.

接下来,我们将比较我们搜索的密钥的哈希值和节点的密钥.大多数字典实现(如果我没记错的话,CPython的字典和集合也是如此),然后也将哈希存储在列表节点中.所以在这里检查是否345等于789,因为事实并非如此,我们知道'c'并且'e'不一样.如果比较两个对象是昂贵的,那么我们可以节省一些周期.

如果散列相等,那并不意味着元素是相等的,所以在这种情况下,我们将检查这两个对象是否相等,如果是这种情况,我们知道该元素在字典中,否则,我们知道不是.