如何以惯用方式伪造字典的__hash__()方法？

Question

编辑：正如@BrenBarn指出的那样，原始文本没有意义。

给定一个字典列表（由csv.DictReader提供--它们都有str键和值），通过将它们全部放入集合中来删除重复项是很好的，但是由于dict不可哈希，因此不能直接这样做。一些现有 问题 探讨了如何为集合/字典伪造__hash__()，但没有解决应该选择哪种方式的问题。

# i. concise but ugly round trip
filtered = [eval(x) for x in {repr(d) for d in pile_o_dicts}]

# ii. wordy but avoids round trip
filtered = []
keys = set()
for d in pile_o_dicts:
    key = str(d)
    if key not in keys:
        keys.add(key)
        filtered.append(d)

# iii. introducing another class for this seems Java-like?
filtered = {hashable_dict(x) for x in pile_o_dicts}

# iv. something else entirely

在Python之禅的精神中，有什么“显而易见的方法”来完成它？

- everial

---

我不确定你在问什么。你是在寻找一个冻结的字典（例如，可以用作另一个字典的键）吗？你的代码示例不太合理（例如，第一个示例只是重新创建了原始的“pile_o_dicts”）。 - BrenBarn

并不是说这是首选解决方案，但在您的第一个示例中，您可以通过使用字典推导式来避免将字典“回传”eval：{repr(d):d for d in pile_o_dicts}.values()，而不是使用set + evals的列表推导式。 - jdi

@BrenBarn 你是对的，编辑成了一些（希望如此！）有意义的东西。 - everial

Answer 1

根据您的示例代码，我认为您的问题与您字面上所说的略有不同。您实际上不想覆盖__hash__() -- 您只想在线性时间内过滤出重复项，对吗？因此，您需要确保每个字典都满足以下条件：1）表示每个键值对，2）以稳定的顺序表示它们。您可以使用按键值对排序的元组，但我建议使用frozenset。frozenset是可哈希的，并且避免了排序的开销，这应该提高性能（正如这个答案似乎证实的那样）。缺点是它们占用的内存比元组多，因此在空间/时间上存在权衡。

此外，您的代码使用集合来进行过滤，但这没有太多意义。如果您使用字典，则不需要进行那些丑陋的eval步骤：

filtered = {frozenset(d.iteritems()):d for d in pile_o_dicts}.values()

在Python 3中，假设您想要的是列表而不是字典视图：

filtered = list({frozenset(d.items()):d for d in pile_o_dicts}.values())

这两种写法都有些笨重。为了易读性，考虑将其拆分成两行：

dict_o_dicts = {frozenset(d.iteritems()):d for d in pile_o_dicts}
filtered = dict_o_dicts.values()

替代方案是一个有序的元组嵌套元组：

filtered = {tuple(sorted(d.iteritems())):d for d in pile_o_dicts}.values()

最后一点提示：不要使用repr。评估为相等的字典可能具有不同的表示形式：

>>> d1 = {str(i):str(i) for i in range(300)}
>>> d2 = {str(i):str(i) for i in range(299, -1, -1)}
>>> d1 == d2
True
>>> repr(d1) == repr(d2)
False

- senderle

Answer 2

通过对它们的items列表进行排序，巧妙命名的pile_o_dicts可以转换为规范形式:

 groups = {}
 for d in pile_o_dicts:
     k = tuple(sorted(d.items()))
     groups.setdefault(k, []).append(d)

这将把相同的字典分组在一起。

顺便说一下，使用sorted(d.items())的技术目前在标准库中用于functools.lru_cache()，以识别具有相同关键字参数的函数调用。换句话说，这种技术是可靠的 :-)

- Raymond Hettinger

---

很难与标准库竞争。 - everial

Answer 3

如果所有的字典都有相同的键，你可以使用一个namedtuple。

>>> from collections import namedtuple
>>> nt = namedtuple('nt', pile_o_dicts[0])
>>> set(nt(**d) for d in pile_o_dicts)

- John La Rooy