118

我看到了一个将hash函数应用于元组的代码示例。结果它返回一个负整数。我想知道这个功能有什么作用？谷歌没有帮助。我找到了一个解释如何计算哈希的页面，但它没有解释为什么我们需要这个函数。

4

5 回答 5

201

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

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

哈希值的创建方式需要使结果值均匀分布，以减少您获得的哈希冲突的数量。哈希冲突是指两个不同的值具有相同的哈希。因此，相对较小的更改通常会导致非常不同的哈希值。

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

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

相同的方法用于字典查找。这使得查找速度非常快，而查找set速度很慢。这也意味着您可以在 a 中拥有不可散列的对象，但不能在 a 中或作为 a 中的键。不可散列对象的典型示例是任何可变对象，这意味着您可以更改其值。如果你有一个可变对象，它不应该是可散列的，因为它的散列会在其生命周期内发生变化，这会导致很多混乱，因为一个对象最终可能会在字典中使用错误的散列值。dictlistlistsetdict

请注意，一个值的哈希值只需要与 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 应用程序等的重要安全功能。

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

于 2013-07-11T06:03:27.033 回答
50

TL;博士：

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

技术考虑

  • 通常比较对象（可能涉及多个级别的递归）是昂贵的。
  • 优选地，该hash()功能是便宜一个（或几个）数量级的。
  • 比较两个哈希比比较两个对象更容易，这就是捷径所在。

如果您了解字典是如何实现的，它们使用哈希表，这意味着从对象派生一个键是检索字典中对象的基石O(1)。但是，这非常依赖于您的哈希函数是否具有抗碰撞性。在字典中获取项目的最坏情况实际上是O(n).

在那一点上，可变对象通常是不可散列的。hashable 属性意味着您可以将对象用作键。如果哈希值被用作键并且同一个对象的内容发生了变化，那么哈希函数应该返回什么？是同一个钥匙还是不同的钥匙？这取决于您如何定义散列函数。

以身作则：

想象一下我们有这个类：

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

于 2013-07-11T07:13:33.743 回答
3

状态的 Python文档hash()：

哈希值是整数。它们用于在字典查找期间快速比较字典键。

Python 字典被实现为哈希表。因此，每当您使用字典时，hash()都会调用您传入的键以进行分配或查找。

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

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

于 2013-07-11T05:39:13.867 回答
1

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

于 2013-07-11T05:39:53.213 回答
-1

您可以Dictionary在 python 中使用数据类型。它与散列非常相似——它也支持嵌套，类似于嵌套散列。

例子：

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

有关更多信息，请参阅有关字典数据类型的本教程。

于 2019-04-02T02:47:38.763 回答