覆写Python字典的哈希函数

Question

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

假设我重写了__hash__方法并最终为一个对象生成了正确的哈希数。那么：

dict = {}
dict[number_here] = value

将值哈希到位置号码number_here，还是在Python的哈希表计算该数字的位置？打印dict只显示项目而不显示它们所在的位置。但是，当我执行hash(4)时，结果是4。所以我认为这意味着整数被哈希到它们各自的位置上？请问有人可以验证我的发现或者解释一下如果我错了吗？

- darksky

---

这个视频可能会让事情变得更加清晰：http://t.co/ZqEWs8MD - Shawn Chin

@ShawnChin: 这就是为什么只有链接的回答（和评论）会被嫌弃的原因。 - RickyA

Answer 1

Python的dict实现使用哈希值来基于键稀疏存储值并避免在存储中出现冲突。它使用hash()的结果作为“起点”，但不是最终位置。因此，尽管hash(4)返回4，但底层C结构中的确切“位置”也取决于哪些其他键已经存在，以及当前表的大小。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以进行==相等运算符。这些对象被认为是hashable。

（对于Python 2.x，实现__cmp__()钩子可以代替实现__eq__()；在Python 3中已删除对此的支持）。

- Martijn Pieters

---

我有一个问题：在我的机器上，hash('abc') == hash(-1600925533)。我可以有一个字典，其中这两个值都是键。难道不应该存在某种哈希冲突吗？或者Python使用了一些其他的哈希函数，而不是内置的hash()函数吗？ - thkang

@MartijnPieters 谢谢。我希望Python处理碰撞，如果重新排序也没关系。但是如果两个不同的对象返回哈希值4，它们肯定会散列到相同的键，对吗？ - darksky

哈希冲突是可能发生的，哈希表实现能够处理这些冲突。 - Tim

@Darksky：不，除非这些键是相等的。hash(key1) == hash(key2) 不足以被视为相同的键。key1 == key2 也必须为真。 - Martijn Pieters

Answer 2

Martijn Pieters给出了一个很好的回答。我只想补充一下，CPython源代码有很好的文档，也是深入了解Python字典实现细节的好地方。最后我检查过，相关注释在33-135行。

- PythonJin

Answer 3

虽然这不会直接改变字典的哈希值，但你可以间接地根据其中一个或多个键自定义哈希你的字典。

将其包装在一个自定义类中：

class Foo:
def __init__(self, foo):
    self.foo_id = foo.get('id') # id is unique for all instances of Foo

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

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

def __getitem__(self, key):
    return self.foo[key]

然后你可以这样做：

foo_dict = {
    'id': 1
    'name': 'George'
    # ..other key values
}

hashable_foo = Foo(foo_dict)

print(hashable_foo['name']) # access like a normal dict

- PrashanD