具有可哈希键的自定义dict无法处理递归结构

Question

我需要一个类似字典的结构，该结构可以采用无法散列的键并将它们映射为一个值。我需要这样做有两个原因：在遍历列表时检查是否已在O（1）中看到项目将每个项目映射到一个标识符，例如一个字符所创建的类似dict的结构将在处理之后被丢弃，因此一旦可以对键进行突变，就无法使用它。例子d = MutableKeyDict()d[[1, 2, 3]] = 'a'print([1, 2, 3] in d)  # Trueprint((1, 2, 3) in d)  # False执行tl; dr我实现了一些行不通的方法。如果您看到实现此目标的规范方法，请跳过该部分。现在，我编写了一个包装器类，该包装器实现了一个__hash__方法，该方法依赖于等同于哈希其数据的不可变类型。class ForcedHashable:    @staticmethod    def hashable(obj):        try:            hash(obj)            return obj        except TypeError:            if isinstance(obj, (list, tuple)):                return tuple(ForcedHashable.hashable(o) for o in obj)            elif isinstance(obj, set):                return frozenset(ForcedHashable(o) for o in obj)            elif isinstance(obj, dict):                return tuple((k, ForcedHashable.hashable(v)) for k, v in obj.items())            ...    def __init__(self, data):        self.data = data    def __eq__(self, other):        return self.data == other.data    def __hash__(self):        return hash(self.hashable(self.data))这使我能够编写使用ForcedHashable来包装其键的自定义dict类的草稿。class MutableKeyDict(UserDict):    def __setitem__(self, key, value):        self.data[ForcedHashable(key)] = value    def __getitem__(self, item):        return self.data[ForcedHashable(item)]    def __contains__(self, item):        return ForcedHashable(item) in self.data它适用于基本情况...d = MutableKeyDict()d[[1, 2, 3]] = 'a'print([1, 2, 3] in d)  # Trueprint((1, 2, 3) in d)  # False但是遇到一些嵌套在其自身中的对象的问题。d = MutableKeyDict()x = []x.append(x)d[x] = 'foo' # raises a 'RecursionError: maximum recursion depth exceeded'当然，递归源自该语句：if isinstance(obj, (list, tuple)):    return tuple(ForcedHashable.hashable(o) for o in obj)我在使用进行修复的过程中途memo很像，就像copy.deepcopy使用的那样，但是后来我意识到即使我这样做了，该方法也将引发RecursionError。def __eq__(self, other):    return self.data == other.data问题我希望以上内容至少适用于内置类型。会有一个聪明的办法解决这个问题RecursionError吗？如果没有，是否存在将相等项（仅内置类型）关联到临时哈希的规范方法？非常欢迎使用其他方法。

Answer 1

没有理由该deepcopy技术对您来说无法解决递归问题。

我认为您可能会遗漏的是deepcopy的备注基于id值的。你只需要包含捕捞对象本身，相同的，而不是对象包含平等的，但不同的对象。毕竟，您不能拥有无穷无尽但相等的对象的深度；那将需要无限的记忆。

事实上，你可以比这更简单deepcopy和pickle，因为它并没有真正的问题是什么，你返回重复的对象，只要它是可哈希的和独特的。1个

因此，例如：

def hashable(obj, *, memo=None):

    if memo is None:

        memo = set()

    if id(obj) in memo:

        return (..., id(obj))

    memo.add(id(obj))

    try:

        hash(obj)

        return obj

    except TypeError:

        if isinstance(obj, (list, tuple)):

            return tuple(ForcedHashable.hashable(o, memo=memo) for o in obj)

        elif isinstance(obj, set):

            return frozenset(ForcedHashable(o, memo=memo) for o in obj)

        elif isinstance(obj, dict):

            return frozenset((k, ForcedHashable.hashable(v, memo=memo)) for k, v in obj.items())

        raise

现在：

>>> x = []

>>> x.append(x)

>>> ForcedHashable.hashable(x)

((Ellipsis, 4658316360),)

>>> d = MutableKeyDict()

>>> d[x] = d

>>> d[x]

{<__main__.ForcedHashable object at 0x115855240>: 2, <__main__.ForcedHashable object at 0x115a247f0>: {...}}

在执行此操作时，请执行以下操作：

elif isinstance(obj, (dict, MutableKeyDict)):

    return frozenset((k, ForcedHashable.hashable(v, memo=memo)) for k, v in obj.items())

… 现在：

>>> d = MutableKeyDict()

>>> d[d] = d

>>> d

{<__main__.ForcedHashable object at 0x11584b320>: {...}}

1.除非您希望它们像Quine原子一样工作，否则您希望它可以被散列并由相同类型的所有其他Quine原子共享，这是一样容易的。