如何使用一组通用键正确散列字典以实现重复数据删除目的？

Question

我有一些日志数据，例如：

logs = [
 {'id': '1234', 'error': None, 'fruit': 'orange'},
 {'id': '12345', 'error': None, 'fruit': 'apple'}
]

每个字典都有相同的键：'id'、'error'和'fruit'（在本例中）。

我想从此列表中删除重复项，但直接dict且set基于基础的方法不起作用，因为我的元素本身就是dicts，不可散列：

>>> set(logs)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'

另一种方法是排序并使用 itertools.groupby - 但字典也不具有可比性，因此这也不起作用：

>>> from itertools import groupby
>>> [k for k, _ in groupby(sorted(logs))]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'

我的想法是计算每个日志条目的哈希值，并将其存储在 a 中set进行比较，如下所示：

def compute_hash(log_dict: dict):
    return hash(log_dict.values())

def deduplicate(logs):
    already_seen = set()
    for log in logs:
        log_hash = compute_hash(log)
        if log_hash in already_seen:
            continue
        already_seen.add(log_hash)
        yield log

然而，我发现这compute_hash会给不同的词典提供相同的哈希值，即使是那些内容完全虚假的词典：

>>> logs = [{'id': '123', 'error': None, 'fruit': 'orange'}, {}]
>>> # The empty dict will be removed; every dict seems to get the same hash.
>>> list(deduplicate(logs))
[{'id': '123', 'error': None, 'fruit': 'orange'}]

compute_hash经过一些实验，我似乎能够通过如下修改来解决问题：

def compute_hash(log_dict: dict):
    return hash(frozenset(log_dict.values()))

但是，我不明白为什么这会产生影响。为什么原始版本似乎为每个输入字典提供相同的哈希值？为什么将.values结果转换为frozenset第一个可以解决问题？除此之外：这个算法正确吗？或者是否有一些反例可以删除错误的值？

---

_{本问题深入讨论了 Python 中的散列如何工作，并考虑了可能比字典更适合列表元素的其他数据结构。如果您只想从字典列表中删除重复项，请参阅唯一字典列表。}

Answer 1

什么地方出了错

关于最初的尝试，我想指出的第一件事是它似乎过度设计。当输入是可散列的时，手动迭代只需要保留 order，即使如此，在 3.7 及更高版本中我们也可以依赖dicts 的 order-preserving 属性。

仅仅因为它是可散列的并不意味着散列是有用的

hash打电话也不是特别有用log_dict.values()。虽然log_dict不可散列，但它.values()（在 3.x 中）是该类型的实例dict_values（该名称未在内置函数中定义，但这就是实例标识自身的方式），它是可散列的：

>>> dv = {1:2, 3:4}.values()
>>> dv
dict_values([2, 4])
>>> {dv}
{dict_values([2, 4])}

所以我们可以很容易地直接使用.values()作为“哈希”：

def compute_hash(log_dict: dict):
    return log_dict.values()

...但这会带来一个新的错误 - 现在每个哈希都会不同：

>>> {1:2}.values() == {1:2}.values()
False

但为什么？

因为dict_valuestype 不定义__hash__，也不定义__eq__。object是直接超类，因此对这些方法的调用会回退到object默认值：

>>> dv.__class__.__bases__
(<class 'object'>,)
>>> dv.__class__.__hash__
<slot wrapper '__hash__' of 'object' objects>
>>> dv.__class__.__eq__
<slot wrapper '__eq__' of 'object' objects>

事实上，dict_values无法明智地实现这些方法，因为它是（间接）可变的- 作为视图，它依赖于底层字典：

>>> d = {1:2}
>>> dv = d.values()
>>> d[3] = 4
>>> dv
dict_values([2, 4])

由于没有一种明显的通用方法来对任何对象进行哈希处理，而且速度也不是非常慢，同时还关心其实际属性，因此默认值根本不关心属性，而只是基于对象标识。例如，在我的平台上，结果如下所示：

Python 3.8.10 (default, Nov 14 2022, 12:59:47) 
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> dv = {1:2, 3:4}.values()
>>> bin(id(dv))
'0b11111110101110011010010110000001010101011110000'
>>> bin(hash(dv))
'0b1111111010111001101001011000000101010101111'

换句话说：

>>> hash(dv) == id(dv) // 16
True

因此，如果compute_hash在原始代码中使用临时对象重复调用，它不会给出有用的结果 - 结果不依赖于对象的内容，并且通常与临时对象相同（即立即GCd）循环中的对象通常会位于同一内存位置。

（是的，这意味着对象默认是可散列和可相等比较的。类型dict本身会重写__hash__以显式禁止它，而奇怪的是，会重写__eq__以比较内容。）

frozenset有一个有用的哈希值

另一方面，frozenset旨在长期存储一些不可变数据。因此，定义 a 非常重要且有用__hash__，它确实：

>>> f = frozenset(dv)
>>> bin(id(f))
'0b11111110101110011010001011101000110001011100000'
>>> bin(hash(f))
'0b101111010001101001001111100001000001100111011101101100000110001'

字典、散列和冲突检测

尽管多年来进行了许多调整和优化，但 Pythondict和set类型从根本上来说都是基于哈希表的。当插入一个值时，首先计算它的哈希值（通常是整数值），然后将该值减少（通常使用模）到底层表存储的索引中。类似地，当查找某个值时，会计算并减少哈希值，以确定在表中的何处查找该值。

当然，该位置可能已经存储了一些其他值。有多种可能的策略来处理这个问题（最后我查了一下，文献中关于它们的命名不一致）。但对于我们的目的来说最重要的是：当通过键查找 a 中的值dict，或检查 a 中是否存在值时set，容器在弄清楚要查找的位置后还必须进行相等性检查，以确认实际上已经找到了正确的事情。

因此，任何简单地手动计算哈希值并将这些哈希值与原始值关联起来的方法都会失败。两个输入字典很容易具有相同的计算哈希值，即使实际上正在考虑它们的内容。例如， a 的哈希值frozenset 基于元素 的哈希值的异或。因此，如果我们的两个输入字典以不同的顺序将所有相同的值分配给键，则哈希将是相同的：

>>> def show_hash(d):
...     return bin(hash(frozenset(d.values())))
... 
>>> show_hash({'id': '1', 'error': None, 'value': 'apple'})
'0b101010010100001000111001000001000111101111110100010000010101110'
>>> # Changing a value changes the hash...
>>> show_hash({'id': '1', 'error': None, 'value': 'orange'})
'0b11111111001000011101011001001011100010100100010010110000100100'
>>> # but rearranging them does not:
>>> show_hash({'id': '1', 'error': 'orange', 'value': None})
'0b11111111001000011101011001001011100010100100010010110000100100'

这种哈希冲突也有可能与完全不相关的值同时发生。对于 64 位哈希来说，这是极不可能的（因为无论名称如何，该值都不会被减少并用作哈希表索引）

明确修复它

因此，为了获得正确的代码，我们需要事后进行自己的检查，明确检查散列到我们集合中的某些值是否already_seen实际上等于具有该散列的先前值。理论上可能有多个，所以我们必须记住每个外部哈希的多个值，也许可以使用 fordict来already_seen代替。就像是：

from collections import defaultdict

def deduplicate(logs):
    already_seen = defaultdict(list)
    for log in logs:
        log_hash = compute_hash(log)
        if log in already_seen.get(log_hash, ()):
            continue
        already_seen[log_hash].append(log)
        yield log

希望这立即看起来不令人满意。通过这种方法，我们本质上是重新实现集合和字典的核心逻辑 - 我们自己计算哈希值，从内部存储中检索相应的值 ( already_seen) ，然后手动检查是否相等 ( if log in ...)。

从另一个角度来看

我们首先做所有这些的原因 - 寻找一个哈希值来表示我们自己的存储中的原始字典 - 是因为该字典不可哈希。但我们可以通过显式地将数据转换为可散列形式（保留所有信息）来直接解决这个问题，而不是尝试将可散列值与数据关联起来。

换句话说，让我们使用不同的类型来表示数据，而不是dict.

由于我们所有的输入dict都具有相同的键，因此自然的做法是将它们转换为用户定义的类的属性。在 3.7 及更高版本中，一种简单、自然且明确的方法是使用 dataclass ，如下所示：

from dataclasses import dataclass
from typing import Optional

@dataclass(frozen=True, slots=True)
class LogEntry:
    id: str
    error: Optional[str]
    fruit: str

文档中没有很好地解释它，但使用frozen=True（主要目的是使实例不可变）也会导致__hash__生成 a ，并根据需要考虑字段。也使用为类型生成的slots=True原因，避免内存开销。__slots__

从这里开始，转换现有日志就很简单了：

logs = [LogEntry(**d) for d in logs]

我们可以直接使用以下方法进行重复数据删除set：

set(logs)

或者，使用 a 保留顺序dict（在 3.7 及更高版本中）：

list(dict.fromkeys(logs))

当然，还有其他选择。最简单的方法是tuple从.values- 假设每个日志字典的键具有相同的顺序（再次假设 Python 3.7 及更高版本，其中键具有顺序），这会保留所有有用的信息 - 这.keys只是为了方便。稍微复杂一点，我们可以使用collections.namedtuple：

from collections import namedtuple

LogEntry = namedtuple('LogEntry', 'id error fruit')
# from here, use the LogEntry type as before

这比该dataclass方法更简单，但不太明确（并且没有提供记录字段类型的优雅方法）。

Answer 2

您有一些可行的答案，但我认为您可能使事情变得过于复杂。这是我对您的原始代码所做的快速修复。

logs = [
    {'id': '1234', 'error': None, 'fruit': 'orange'},
    {'id': '1234', 'error': None, 'fruit': 'orange'},
    {'id': '12345', 'error': None, 'fruit': 'apple'}, 
]

def get_values(log: dict):
    return tuple(log.values())

unique_logs = set(map(get_values, logs))
for log in unique_logs:
    print(log)

（'12345'，无，'苹果'）
（'1234'，无，'橙色'）