8

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

假设我覆盖__hash__并最终得出一个对象的正确哈希数。将：

dict = {}
dict[number_here] = value

将值散列到位置 number number_here，还是仍然在 Python 的哈希表将为该数字计算的位置？

打印dict只显示项目而不是它们的位置。但是，当我这样做时hash(4)，结果是 4。所以我假设这意味着整数被散列到它们各自的位置？

如果我错了，有人可以验证我的发现或向我解释吗？

4

2 回答 2

17

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

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

由于 dict 没有顺序，这不是你需要担心的事情，也不需要影响。如果您需要在 dict 中排序，请改用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 中已删除对此的支持）。

于 2012-11-22T14:26:12.617 回答
1

Martijn Pieters 给出了一个很好的答案。我只是想补充一点，CPython 源代码有很好的文档记录，也是查看 Python Dictionary 实现细节的好地方。最后我检查了一下，相关的评论在第 33-135 行。

于 2013-12-18T14:46:28.063 回答