在字典中重写Python的哈希函数

Question

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

假设我重写__hash__并最终为对象提供了正确的哈希号。将：

dict = {}
dict[number_here] = value

将值哈希到位置编号中number_here，还是将其保留在Python哈希表将为该编号计算的位置上？

打印dict仅显示项目，而不显示项目的位置。但是，当我这样做时hash(4)，结果为4。因此，我假设这意味着将整数哈希到各自的位置？

有人可以核实我的发现，或者如果我做错了请向我解释？

Answer 1

pythondict实现使用哈希值既基于键稀疏地存储值，又避免在该存储中发生冲突。它以的结果hash()作为 起点 ，而不是确定的位置。

因此，尽管hash(4)返回4了，但底层C结构中的确切“位置”也基于已经存在的 其他
键以及当前表的大小。例如，可以根据需要调整python哈希表的大小（添加项目）。

由于字典没有顺序，因此您无需担心或希望影响。如果您需要按字典排序，请改用collections.OrderedDict()实现，它可以单独跟踪排序。

python哈希表实现的详细信息

您可能需要阅读Wikipedia上哈希表的工作原理；Python对其实现使用开放式寻址。

在表中选择一个插槽时，将使用哈希值的模数（整数）和当前表的大小，从而在大小为32的表上进行，因此key 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中已删除对此钩子的支持）。