哈希在 Python 中做什么？

我看到一个代码示例，其中 hash函数应用于元组。结果它返回一个负整数。我想知道这个函数是做什么的？谷歌帮不上忙。我找到一个页面，解释如何散列计算，但它没有解释为什么我们需要这个函数。

155021 次浏览
小开

Python hash()的文件状态:

散列值是整数。它们用于在字典查找过程中快速比较字典键。

Python 字典实现为散列表。因此，任何时候使用字典时，都会对传入用于赋值或查找的键调用 hash()。

此外，dict类型的文档状态:

不是 散列的的值，即包含列表、字典或其他可变类型(通过值而不是通过对象标识进行比较)的值不能用作键。

小开

字典和集合使用哈希来快速查找对象。一个很好的起点是维基百科关于 哈希桌的文章。

小开
最佳答案

散列是一个固定大小的整数，用于标识特定的值 。每个值都需要有自己的散列，因此对于相同的值，即使不是同一个对象，也会得到相同的散列。

>>> hash("Look at me!")
4343814758193556824
>>> f = "Look at me!"
>>> hash(f)
4343814758193556824

散列值的创建方式需要使得结果值均匀分布，以减少所得到的散列冲突的数量。散列冲突是指两个不同的值具有相同的散列。因此，相对较小的变化通常会导致非常不同的散列。

>>> hash("Look at me!!")
6941904779894686356

这些数字非常有用，因为它们可以快速查找大量值集合中的值。两个使用它们的例子是 Python 的 set和 dict。在 list中，如果您想检查某个值是否在列表中，那么对于 if x in values:，Python 需要遍历整个列表，并将 x与列表 values中的每个值进行比较。这可能需要很长的时间为一个长的 list。在 set中，Python 会跟踪每个哈希值，当您键入 if x in values:时，Python 将获得 x的哈希值，在内部结构中查找，然后只将 x与具有与 x相同哈希值的值进行比较。

字典查找也使用相同的方法。这使得 set和 dict中的查找非常快，而 list中的查找非常慢。这也意味着您可以在 list中使用非散列对象，但在 set中不能使用，在 dict中也不能使用。非散列对象的典型例子是任何可变的对象，这意味着您可以更改它的值。如果您有一个可变的对象，那么它不应该是散列的，因为它的散列随后将在其生命周期中发生变化，这将导致很多混淆，因为一个对象可能最终在字典中出现错误的散列值。

注意，值的哈希值只需要在一次 Python 运行中相同。在 Python 3.3中，它们实际上会随着 Python 的每一次新运行而改变:

$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21)
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
1849024199686380661
>>>
$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21)
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
-7416743951976404299

这使得猜测某个字符串的散列值变得更加困难，这是 Web 应用程序等的一个重要安全特性。

因此，不应该永久存储哈希值。如果你需要永久地使用哈希值，你可以看看更“严重”的哈希值类型，加密哈希函数加密哈希函数，它可以用来对文件进行可验证的校验和等。

小开

译者:

请参考 词汇表: hash()是比较对象的快捷方式，如果一个对象可以与其他对象进行比较，那么它就被认为是散列的。这就是为什么我们使用 hash()。它还用于访问实现为 CPython 中可调整大小的哈希表的 dict和 set元素。

技术上的考虑

  • 通常比较对象(可能涉及几个递归级别)是昂贵的。
  • 优选地，hash()功能是一个数量级(或几个)较便宜。
  • 比较两个散列要比比较两个对象容易，这就是快捷方式所在。

如果您阅读有关 字典是如何使用的的内容，它们使用散列表，这意味着从对象派生一个键是在 O(1)的字典中检索对象的基石。然而，这非常依赖于您的散列函数是 防碰撞。字典中的 最坏的情况下得到一个项目实际上是 O(n)。

在这一点上，可变对象通常不是散列的。散列属性意味着您可以使用对象作为键。如果哈希值被用作键，同一对象的内容发生变化，那么哈希函数应该返回什么？是同一把钥匙还是不同的？它 看情况介绍了如何定义散列函数。

以身作则:

想象一下我们有这样一门课:

>>> class Person(object):
...     def __init__(self, name, ssn, address):
...         self.name = name
...         self.ssn = ssn
...         self.address = address
...     def __hash__(self):
...         return hash(self.ssn)
...     def __eq__(self, other):
...         return self.ssn == other.ssn
...

请注意: 这一切都是基于这样的假设，即 SSN 永远不会为个人更改(甚至不知道在哪里可以从权威来源实际验证这一事实)。

还有鲍勃:

>>> bob = Person('bob', '1111-222-333', None)

鲍勃去见一位法官改名换姓:

>>> jim = Person('jim bo', '1111-222-333', 'sf bay area')

这就是我们所知道的:

>>> bob == jim
True

但这是两个不同的对象，分配了不同的内存，就像同一个人的两个不同记录:

>>> bob is jim
False

现在到了 hash ()方便的部分:

>>> dmv_appointments = {}
>>> dmv_appointments[bob] = 'tomorrow'

你猜怎么着:

>>> dmv_appointments[jim] #?
'tomorrow'

您可以从两个不同的记录访问相同的信息。 现在试试这个:

>>> dmv_appointments[hash(jim)]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 9, in __eq__
AttributeError: 'int' object has no attribute 'ssn'
>>> hash(jim) == hash(hash(jim))
True

刚才发生了什么？那是碰撞。因为 hash(jim) == hash(hash(jim))都是整数，所以我们需要比较 __getitem__的输入和所有碰撞的项目。内建的 int没有 ssn属性，所以它跳过。

>>> del Person.__eq__
>>> dmv_appointments[bob]
'tomorrow'
>>> dmv_appointments[jim]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: <__main__.Person object at 0x7f611bd37110>

在最后一个示例中，我展示了即使发生冲突，也会执行比较，对象不再相等，这意味着它成功地引发了 KeyError。

小开

可以在 python 中使用 Dictionary数据类型。它非常非常类似于 hash ーー而且它还支持嵌套，类似于 to 嵌套 hash。

例如:

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School" # Add new entry


print ("dict['Age']: ", dict['Age'])
print ("dict['School']: ", dict['School'])

欲了解更多信息，请参考此 关于字典数据类型的教程。


提交答案