覆盖 Python 字典中的哈希函数

Question

我正在尝试为某个对象创建一个自定义哈希函数，我将把它哈希到字典中。哈希函数是唯一的（不是标准的 Python 函数）。这对我来说非常重要：使用独特的功能。每个键的值都是一个列表。

假设我覆盖

__hash__

并最终得出对象的正确哈希值。会：

dict = {}
dict[number_here] = value

将值散列到位置号

number_here

，或者它仍然位于Python的哈希表为该数字计算的位置吗？

打印

dict

仅显示项目，而不显示它们所在的位置。但是，当我执行

hash(4)

时，结果是 4。所以我假设这意味着整数被散列到各自的位置？

有人可以验证我的发现或向我解释如果我错了吗？

Answer 1

python

dict

实现使用哈希值来基于键稀疏存储值并避免该存储中的冲突。它使用

hash()

的结果作为起点，它不是最终位置。

因此，虽然

hash(4)

返回

4

，但底层 C 结构中的确切“位置”也基于已经存在的 other 键以及当前表有多大。例如，Python 哈希表会根据需要调整大小（添加项目）。

由于字典没有顺序，所以这不是您需要担心或希望影响的事情。如果您需要在字典中排序，请改用

collections.OrderedDict()

实现，它会单独跟踪排序。

Python哈希表实现细节

您可能想在 Wikipedia 上了解哈希表的工作原理； Python 使用开放寻址来实现。

在表中选择槽时，会取哈希值（整数）与当前表大小的模，因此在大小为 32 的表上，因此键

45

，哈希值

45

最初为存储在插槽 14 中。

如果存在冲突（槽 14 中已经存储了其他内容，并且它不是整数

45

），则槽值将受到扰乱，直到找到空槽或找到相同的密钥。扰动是通过以下公式完成的：

perturb = slot = hash
while slot_is_full and item_in_slot_is_not_equal_to_key:
    slot = (5*slot) + 1 + perturb
    perturb >>= 5

因此，当发生冲突时，会以逐渐减小的步长选择另一个槽，直到扫描整个表。请注意，如有必要，表格已经调整大小以腾出空间。

为了使其正常工作，自定义类型需要

__hash__()

方法 和 需要实现

__eq__()

来确定两个实例是否表示相同的键。匹配哈希值是不够的。为了让 dict 实现考虑两个实例来表示完全相同的键，它们的哈希值必须匹配，并且对于

==

相等运算符，它们必须返回 True。此类对象被认为是

可哈希

。 （对于 Python 2.x，实现

__cmp__() hook

 可以代替实现 

__eq__()；Python 3 中已删除对此的支持）。

Answer 2

CPython 源代码

有很好的文档记录，也是研究 Python 字典实现细节的绝佳位置。最后我查了一下，相关注释在第 33-135 行。

Answer 3

Dictionary

的哈希值，但当您的

Dictionary

包含唯一的

id

字段时，您可以间接更改。将其包装在自定义类中：

class Foo:
def __init__(self, foo):
    self.foo_id = foo.get('id')

def __eq__(self, other):
    return isinstance(other, Foo) and self.foo_id == other.foo_id

def __hash__(self):
    return hash(self.foo_id)

然后你可以这样做：

custom_hashable_foo = Foo(foo_dict)