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

Question

我需要一个类似字典的结构，该结构可以采用无法散列的键并将它们映射为一个值。我需要这样做有两个原因：

1. 在遍历列表时检查是否已在O（1）中看到项目

2. 将每个项目映射到一个标识符，例如一个字符

所创建的类似dict的结构将在处理之后被丢弃，因此一旦可以对键进行突变，就无法使用它。

例子

d = MutableKeyDict()

d[[1, 2, 3]] = 'a'

print([1, 2, 3] in d)  # True

print((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)  # True

print((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):&nbsp; &nbsp; if memo is None:&nbsp; &nbsp; &nbsp; &nbsp; memo = set()&nbsp; &nbsp; if id(obj) in memo:&nbsp; &nbsp; &nbsp; &nbsp; return (..., id(obj))&nbsp; &nbsp; memo.add(id(obj))&nbsp; &nbsp; try:&nbsp; &nbsp; &nbsp; &nbsp; hash(obj)&nbsp; &nbsp; &nbsp; &nbsp; return obj&nbsp; &nbsp; except TypeError:&nbsp; &nbsp; &nbsp; &nbsp; if isinstance(obj, (list, tuple)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return tuple(ForcedHashable.hashable(o, memo=memo) for o in obj)&nbsp; &nbsp; &nbsp; &nbsp; elif isinstance(obj, set):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return frozenset(ForcedHashable(o, memo=memo) for o in obj)&nbsp; &nbsp; &nbsp; &nbsp; elif isinstance(obj, dict):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return frozenset((k, ForcedHashable.hashable(v, memo=memo)) for k, v in obj.items())&nbsp; &nbsp; &nbsp; &nbsp; 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)):&nbsp; &nbsp; 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原子共享，这是一样容易的。