python - 在字典中覆盖 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 没有顺序，这不是您需要担心的事情，也不希望影响它。如果您需要在字典中排序，请改用 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 中已删除对此的支持)。