python - 处理 python 字典中的哈希冲突

Question

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

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

我将所有这些用户信息字典收集在一个更大的字典容器中，使用每个字典的哈希值作为键 (Hashing a dictionary?)。

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

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

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

Answer 1

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

因此，该唯一键应该是您 map 中的键，以允许您查找用户记录。

但是，如果出于某种原因您无法访问此类保证唯一的 key ，您当然可以从记录中创建一个散列(如您所述)并使用许多散列中的任何一个表算法来存储具有可能冲突键的元素。在这种情况下，您不会避免碰撞，而只是处理它。

一个快速且常用的算法是这样的:使用记录上的散列来创建一个 key ，就像您已经做的那样。此 key 可能不是唯一的。现在将记录列表存储在键指示的位置。我们称这些列表为“桶”。要存储一个新元素，对其进行哈希处理，然后将其附加到存储在该位置的列表中(将其添加到存储桶中)。要查找一个元素，对其进行哈希处理，找到条目，然后按顺序搜索该位置的列表/存储桶以找到您想要的条目。

这是一个例子:

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

在示例中，您有哈希表(通过字典实现)。您有散列键值 678，其中一个条目存储在存储桶中。然后你有散列键值 123，但是有一个冲突:'John' 和 'Bob' 条目都有这个散列值。不管怎样，您找到存储在 mymap[123] 的存储桶并对其进行迭代以查找值。

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

性能通常只有在发生大量冲突时才会成为问题(当每个桶的列表变得很长时)。使用良好的哈希函数可以避免一些事情。

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