代码之家 › 专栏 › 技术社区 › Olivier Melançon iacob

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

hashmap hash dictionary python-3.x python

Olivier Melançon iacob · 技术社区 · 8 年前

我需要一个类似字典的结构,它可以获取不可修改的键并将它们映射到一个值。我需要这个有两个原因:

检查是否已在中看到项目 O(1) 遍历列表时
将每个项映射到标识符,例如一个字符

创建的DICT类结构将在该过程之后被丢弃,因此,一旦密钥发生突变,就不能使用它。

例子

d = MutableKeyDict()

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

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

实施

tl;dr i实现了一些不起作用的东西。如果你看到了实现这一点的规范方法,请跳过这一部分。

现在,我编写了一个包装类,它实现了 __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))

这允许我编写一个自定义dict类的草稿,该类使用 ForcedHashable 把钥匙包起来。

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'

打印([1,2,3]在D中)真
打印(D中的(1,2,3)假

但是在嵌套对象本身时遇到了一些问题。

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

问题

我希望上面的方法至少能适用于内置类型。

有没有什么聪明的办法来解决这个问题 递归错误 ?如果没有,是否有一种规范的方法将相等的项(仅限内置类型)与临时散列相关联?其他方法也非常受欢迎。

1 回复 | 直到 8 年前

abarnert 8 年前

没有理由 deepcopy 解决递归问题的技术是行不通的。

我想你可能会错过的是 深拷贝 的备忘录是基于 id 价值观。您只需要捕获包含 他们自己 ,相同,而不是包含 相等但不同 物体。毕竟,你不能有无限深的不同但相等的物体,那将需要无限的记忆。

事实上,你可以让这件事比 深拷贝 和 pickle ,因为这并不重要什么返回一个重复的对象,只要它是散列的和唯一的。 ^一

例如:

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。除非你想让它们像奎因原子一样工作,在这种情况下,你希望它是可哈希的,并由所有其他类型的奎因原子共享,这同样容易。}