Python 中具有相同键的哈希字典

在Python3.x中，dict上的.values返回dict_values的实例(该名称未在内置中定义，但这是实例标识自身的方式):

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

此类旨在用作现有基础对象的视图，并且没有定义其自己的__hash__方法.object是直接的超类，所以对__hash__的调用回落到object.__hash__:

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

事实上，dict_values不能明智地实现__hash__，因为it is (indirectly) mutable-作为一个视图，它依赖于底层的字典:

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

因为没有一种明显的通用方法来散列任何也不是非常慢的对象，同时还关心它的实际属性，所以默认的doesn't关心属性，并且简单地基于对象标识.例如，在我的平台上，结果如下所示:

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)对象通常会在相同的内存位置结束.

另一方面，frozenset用于长期存储一些不变的数据.因此，它对它定义__hash__是重要和有用的，它确实做到了:

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

我们可以在GitHub上see the reference implementation for frozenset.__hash__.值在第一次计算后被缓存(毕竟，它是一个不可变的对象，所以除了节省内存外，没有理由重复计算)，否则它会迭代哈希表，对条目进行XOR运算，并执行一些额外的修正.因此，我们可以确信这将是相关任务的正确哈希值.

很难想象再简单地解决问题了，因为对不起作用的代码的唯一更改是单一类型强制.但是，如果日志(log)条目都具有相同的键集，则将其硬编码到散列中可能更有意义:

def hash_log_entry(entry):
    return hash(entry['id']) ^ hash(entry['error']) ^ hash(entry['fruit'])

然而，现有的代码并不是technically正确的；毕竟，散列值只包含有限数量的位，而我们可以对任意大的输入集进行散列.因此，一个完全不同的集合可能会被错误地注册为already_seen(尽管这极不可能).更重要的是，如果我们的散列只关心log中的.values，而不考虑顺序，那么它当然会给另一个log提供相同的散列值，并将相同的值集分配给不同的键-例如{'id': '1234', 'error': None, 'fruit': 'orange'}对{'id': '1234', 'error': 'orange', 'fruit': None}.

要解决这个问题，一种方法是使用dict代替，以便跟踪原始值，并根据匹配的散列将它们绑定(因为我们现在实际上需要考虑冲突):

from collections import defaultdict

# We can't use a set to remember dicts with the same custom hash -
# that's the problem we were trying to work around in the first place!
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)

但这实际上是复制了字典应该为我们实现的判断逻辑.

另一种方法是对日志(log)条目使用我们自己的类型:

from dataclasses import dataclass
from typing import Optional

# It's not very well explained in the documentation, but
# when the type is declared to be immutable using `frozen=True`,
# it will have a __hash__ generated as well.
@dataclass(frozen=True)
class LogEntry:
    id: str
    error: Optional[str]
    fruit: str

# convert existing logs
logs = [LogEntry(**d) for d in logs]

# Now, since the type is hashable, we can directly deduplicate with a set:
set(logs)