如何正确哈希含共同键的字典以实现去重？

DevOps 小满

2026-8-6

字典列表去重的哈希问题

我有如下日志数据：

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

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

我想从该列表中去除重复项，但直接用dict和set的方法不可行，因为dict是不可哈希的：

>>> 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'

我尝试为每个日志条目计算哈希值，用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'}, {}]
>>> # 空字典会被移除；似乎每个字典的哈希值都相同。
>>> 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就能解决问题？
这个修改后的算法是否正确？有没有错误移除元素的反例？

问题解答

1. 原`compute_hash`失效的原因

Python中dict.values()返回的是字典视图对象（dict_values类型），它的哈希值并非基于元素内容计算，而是依赖对象本身的标识（类似id()的逻辑）。也就是说，不同字典的values()视图，哪怕内容完全不同，只要视图对象的哈希计算逻辑导致结果碰撞，就会得到相同的哈希值；甚至同一个字典多次调用values()，返回的视图哈希也可能变化。你遇到的所有字典哈希值相同，就是这种视图哈希碰撞导致的。

2. `frozenset`解决问题的原理

frozenset是不可变的可哈希集合，它的哈希值由集合内所有元素的哈希值组合计算而来。将dict.values()转换为frozenset后，哈希计算会基于字典的实际值内容，这样不同值内容的字典就能生成不同的哈希值。

但要注意：frozenset是无序的，且会自动去重集合内的元素，这也为后续的错误埋下了伏笔。

3. 算法的正确性与反例

修改后的算法并不完全正确，存在错误去重的场景：

反例1：值集合相同但键值对不同的字典

假设所有字典都包含k1、k2、k3三个键：

log1 = {'k1': 'a', 'k2': 'b', 'k3': 'c'}
log2 = {'k1': 'b', 'k2': 'a', 'k3': 'c'}

这两个字典是完全不同的条目，但它们的values()转换为frozenset后都是{'a','b','c'}，哈希值完全相同，会被错误判定为重复，最终只保留第一个字典。

反例2：含重复值的不同字典

log1 = {'id': '1', 'error': 'test', 'fruit': 'test'}
log2 = {'id': '2', 'error': 'test', 'fruit': 'other'}

log1的values()转成frozenset后是{'1','test'}，log2的是{'2','test','other'}，这个场景没问题；但如果是：

log1 = {'id': '1', 'error': 'x', 'fruit': 'x'}
log2 = {'id': '2', 'error': 'x', 'fruit': 'x'}

哦，这个场景下两者值集合不同，哈希不同。但如果是：

log1 = {'key1': 5, 'key2': 6}
log2 = {'key1': 6, 'key2': 5}

这两个字典内容不同，但frozenset(values)都是{5,6}，会被错误去重。

更可靠的哈希方案

如果要基于字典完整内容计算哈希，应该把键值对转换为有序的可哈希结构，比如tuple(sorted(log_dict.items()))，这样既考虑键也考虑值，还能避免无序集合带来的问题：

def compute_hash(log_dict: dict):
    return hash(tuple(sorted(log_dict.items())))

这个方案下，上面的反例都会生成不同的哈希值，不会出现错误去重的情况。

内容的提问来源于stack exchange，提问作者dCoder

如何正确哈希含共同键的字典以实现去重？

问题解答 #

1. 原compute_hash失效的原因 #

2. frozenset解决问题的原理 #

3. 算法的正确性与反例 #