在字典中覆盖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结构中的确切"位置"也基于其他键已经存在的位置以及当前表的大小.例如,根据需要调整python哈希表(添加项目).

由于dict没有排序,这不是你需要担心或者希望影响的东西.如果您需要在dict中进行排序,请使用collections.OrderedDict()实现,它会单独跟踪排序.

python哈希表实现的细节

您可能想要了解哈希表如何在维基百科上运行 ; 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__()钩子不会实现__eq__();在Python 3中已经删除了对此的支持).