为什么Python中字典的key必须是不可变的?

2020/09/27 08:25

为什么字典的key必须是不可变的?

字典的哈希表实现使用从键值计算的哈希值来查找键。

如果键是可变对象,则其值可能会发生变化,因此其哈希值也会发生变化。

但是,由于无论谁更改键对象都无法判断它是否被用作字典键值,因此无法在字典中修改条目。

然后,当你尝试在字典中查找相同的对象时,将无法找到它,因为其哈希值不同。

如果你尝试查找旧值,也不会找到它,因为在该哈希表中找到的对象的值会有所不同。

如果你想要一个用列表索引的字典,只需先将列表转换为元组;用函数 tuple(L) 创建一个元组,其条目与列表 L相同。元组是不可变的,因此可以用作字典键。

已经提出的一些不可接受的解决方案:

哈希按其地址(对象ID)列出。这不起作用,因为如果你构造一个具有相同值的新列表,它将无法找到;例如:

mydict = {[1, 2]: '12'}
print(mydict[[1, 2]])

会引发一个 KeyError 异常,因为第二行中使用的 [1, 2] 的 id 与第一行中的 id 不同。换句话说,应该使用 == 来比较字典键,而不是使用 is 。

使用列表作为键时进行复制。这没有用的,因为作为可变对象的列表可以包含对自身的引用,然后复制代码将进入无限循环。

允许列表作为键,但告诉用户不要修改它们。当你意外忘记或修改列表时,这将产生程序中的一类难以跟踪的错误。它还使一个重要的字典不变量无效:d.keys() 中的每个值都可用作字典的键。

将列表用作字典键后,应标记为其只读。问题是,它不仅仅是可以改变其值的顶级对象;你可以使用包含列表作为键的元组。将任何内容作为键关联到字典中都需要将从那里可到达的所有对象标记为只读 —— 并且自引用对象可能会导致无限循环。

如果需要,可以使用以下方法来解决这个问题,但使用它需要你自担风险:你可以将一个可变结构包装在一个类实例中,该实例同时具有 __eq__() 和 __hash__() 方法。

然后,你必须确保驻留在字典(或其他基于 hash 的结构)中的所有此类包装器对象的哈希值在对象位于字典(或其他结构)中时保持固定。

class ListWrapper:
    def __init__(self, the_list):
        self.the_list = the_list
    def __eq__(self, other):
        return self.the_list == other.the_list
    def __hash__(self):
        l = self.the_list
        result = 98767 - len(l)*555
        for i, el in enumerate(l):
            try:
                result = result + (hash(el) % 9999999) * 1001 + i
            except Exception:
                result = (result % 7777777) + i * 333
        return result

注意,哈希计算由于列表的某些成员可能不可用以及算术溢出的可能性而变得复杂。

此外,必须始终如此,如果 o1 == o2 (即 o1.__eq__(o2) is True )则 hash(o1) == hash(o2)``(即``o1.__hash__() == o2.__hash__() ),无论对象是否在字典中。如果你不能满足这些限制,字典和其他基于 hash 的结构将会出错。

对于 ListWrapper ,只要包装器对象在字典中,包装列表就不能更改以避免异常。除非你准备好认真考虑需求以及不正确地满足这些需求的后果,否则不要这样做。请留意。

更多python知识,请关注Python视频教程!!

免费直播

    精选课程 更多

    注册电脑版

    版权所有 2003-2020 广州环球青藤科技发展有限公司