我正在尝试为我将散列到字典中的某个对象创建自定义散列函数。散列函数是唯一的(不是标准的 Python 函数)。这对我来说非常重要:使用独特的功能。每个键的值都是一个列表。
假设我重写了 __hash__
并最终得到了对象的正确哈希值。会:
dict = {}
dict[number_here] = value
将值散列到位置编号 number_here
中,还是它仍然位于 Python 的散列表将为该数字计算的位置?
打印 dict
只显示项目而不是它们所在的位置。但是,当我执行 hash(4)
时,结果是 4。所以我假设这意味着整数被散列到它们各自的位置?
如果我错了,有人可以验证我的发现或向我解释吗?
最佳答案
python dict
实现使用散列值来基于键稀疏地存储值并避免在该存储中发生冲突。它使用 hash()
的结果作为起点,它不是最终位置。
因此,尽管 hash(4)
返回 4
,但底层 C 结构中的确切“位置”也基于其他键已经存在,以及当前表有多大。例如,python 哈希表会根据需要调整大小(添加项目)。
由于 dict 没有顺序,这不是您需要担心的事情,也不希望影响它。如果您需要在字典中排序,请改用 collections.OrderedDict()
实现,它会单独跟踪排序。
python哈希表实现细节
您可能想阅读哈希表如何在 Wikipedia 上工作; Python 在其实现中使用开放寻址。
在表中选择槽时,取哈希值(整数)与当前表大小的模,因此在大小为32的表上,所以键45
,hash值 45
最初将存储在插槽 14 中。
如果发生冲突(插槽 14 中已经存储了其他内容,并且不是整数 45
),则插槽值扰动直到出现空插槽找到或找到相同的 key 。扰动是用公式完成的:
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__()
hook 可以代替实现 __eq__()
;在 Python 3 中已删除对此的支持)。
关于python - 在字典中覆盖 Python 的哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13514716/