处理Python字典中的哈希冲突

Question

我有一堆 python 字典，每个字典都包含用户信息，例如：

NewUserDict={'name': 'John', 'age':27}

我将所有这些用户信息字典收集在一个更大的字典容器中，使用每个字典的哈希值作为键（哈希字典？）。

将新的唯一用户添加到字典时，处理哈希冲突的最佳方法是什么？我打算手动将字典与冲突的哈希值进行比较，然后将一些随机数添加到更新的哈希值中，例如：

if new_hash in larger_dictionary:
    if larger_dictionary[new_hash] != NewUserDict:
        new_hash = new_hash + somerandomnumber

处理这个问题的标准方法是什么？或者，我如何知道我是否应该首先担心碰撞？

Answer 1

通常，您会使用用户记录中最独特的元素。这通常意味着系统通常有一个用户名或每个记录（用户）的唯一ID，保证是唯一的。用户名或 ID 将是记录的唯一键。由于这是由系统本身强制执行的，例如通过数据库表中的自动递增键，因此您可以确保不会发生冲突。

因此，该唯一键应该是地图中的键，以便您查找用户记录。

但是，如果由于某种原因您无法访问这样一个保证唯一的密钥，您当然可以从记录中创建一个哈希（如您所描述的）并使用任何一种哈希表算法来存储可能有冲突键的元素。在这种情况下，您不会避免碰撞，而只是处理它。

一种快速且常用的算法如下：使用记录上的散列来创建密钥，就像您已经做的那样。该键可能不是唯一的。现在将记录列表存储在键指示的位置。我们将这些列表称为“桶”。要存储新元素，请对其进行散列，然后将其附加到存储在该位置的列表（将其添加到存储桶）。要查找某个元素，请对其进行散列，查找该条目，然后按顺序搜索该位置的列表/存储桶以查找所需的条目。

这是一个例子：

mymap[123] = [ {'name':'John','age':27}, {'name':'Bob','age':19} ]
mymap[678] = [ {'name':'Frank','age':29} ]

在示例中，您有哈希表（通过字典实现）。您的哈希键值是 678，存储桶中存储了该哈希键值的一个条目。然后，您的哈希键值是 123，但存在冲突：“John”和“Bob”条目都具有此哈希值。无论如何，您都会找到存储在 mymap[123] 中的存储桶并迭代它以查找值。

这是哈希映射的一种灵活且非常常见的实现，不需要重新分配或其他复杂性。它在很多地方都有描述，例如： https: //www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html（在第 8.3.1 章中）。

通常，只有当发生大量冲突时（当每个存储桶的列表变得非常长时），性能才会成为问题。使用好的哈希函数可以避免这种情况。

但是：您的记录的真正唯一 ID（例如由数据库强制执行）可能仍然是首选方法。