python - 可变的用户定义类型和集

Question

我有一个用例，要求我创建一组可变类型对象，像这样:

class abc(object):
    def __init__(self):
        self.a = set(["a"])
    def __eq__(self, o):
        return self.a == o.a
a = abc()
b = abc()
print hash(a)
print hash(b)
print a == b
set([a]) == set([b])

阅读 python 文档，它说

"objects which compare equal have the same hash value"

和

"If a class defines mutable objects and implements a __cmp__() or __eq__() method, it should not implement __hash__(), since hashable collection implementations require that a object’s hash value is immutable"

上面的示例将为相等性打印 true 并为 a 和 b 打印不同的整数哈希值，但对于集合相等性打印 false。文档建议将对象设置为不可散列，但是我无法将其插入集合中。难道是我的用法不对？

Python 中的集合不适合与可变类型一起使用吗？

Answer 1

如果将一个对象插入到集合(或任何语言中的任何基于哈希的数据结构)中，然后对其进行变异，事情将会崩溃，因为新的哈希值可能不再与其在数组中的位置相对应。因此，例如，如果您在突变后插入了另一个与前一个对象相同的对象，python 可能无法找到前一个对象，并且它会让两者都存在于集合中。这同样适用于二叉搜索树。

您需要:

1. 仅允许在构造函数中设置类的值，从而使类不可变。
2. 创建类的第二个不可变版本，第一个版本可以转换为该版本(例如，通过将集合转换为卡住集合并隐藏对成员的访问权限)。
3. 使用列表等数据结构，您可以在其中自由改变对象，但检查成员资格(从而避免重复)需要 O(n) 时间。
4. 使您的对象可散列，但要格外小心:影响其散列和相等性的每个突变都必须将其从所有集合(以及它作为键的字典)中删除，对其进行突变，然后将其放回原处。