Python：自定义可变类可以用作字典的键吗？

Question

假设我们有一个像这样的自定义节点类：

class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random

我有一个节点对象，我想将其用作字典的键。
我的理解是，一个对象应该是不可变和可散列的，才能可靠地用作字典键，因为可变对象可能会导致散列值发生变化，并且该对象是可变的。

我知道 python 确实允许将自定义可变对象用作字典键，这是如何工作的？

更新：引用的链接不涉及自定义对象的可变性方面。他们只是提供了一种方法来覆盖哈希函数的默认实现。这个问题应该重新打开，因为它与引用的“重复”问题不同。

答案：自定义可变对象的哈希方法的默认实现使用identity，它保证在对象的生命周期内是唯一且恒定的。可变的自定义对象不应该覆盖哈希函数的默认实现。下面提供了更详细的答案。

Answer 1

Node 自定义对象从其类定义来看是可变的，并且 任何可变对象不应覆盖哈希方法的默认实现，因为默认方法使用 identity，保证在对象的生命周期中是唯一且恒定的。这样做可能会导致对象的哈希值发生变化，并可能导致很多问题。

例如：

Node node = new Node(5, None, None)
cache = {}
cache[node] = "Node added"
node.val = 5

# If we override default implementation of hash function, we have to
# make sure hashing function does not use object attributes else
# accessing cache[node] now would cause problem as a different hashed 
# value would be computed and we won't be able to retrieve "Node added" 
# value. 

# Default implementation uses identity and would always hash 
# to same value even if the object mutates.

但是我们可以继续重写不可变对象的哈希方法。 this 线程上的回答帮助我理解了它是如何工作的。对于以下内容，我们假设 Node 对象的属性一旦创建就永远不会改变。

这里的想法是确保您的自定义对象实现哈希和相等方法。

平等方法应该以这样的方式实现：两个逻辑相等的对象始终被认为是相等的。对于此处给定的 Node 对象，如果两个节点的所有属性都相同，则它们将被视为相等。所以我们可以构建一个键，它是所有属性的元组。这是可行的，因为元组是不可变的，所以我们基本上创建一个包含该对象的所有属性的不可变对象，并将使用它来计算哈希值。

以下实现确保两个逻辑上等效的节点（具有相同的属性）具有相同的密钥，因此将为两个相等的节点生成相同的哈希值。

class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random

    def __key(self):
        return (self.val, self.next, self.random)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, Node):
            return self.__key() == other.__key()
        return NotImplemented

Answer 2

如果节点确实是可变的，那么这样的事情就可以工作：

from dataclasses import dataclass
from typing import Any
import numpy as np


class MutableHashable:

    def __hash__(self):
        """ make hash depend on identity, not on value """
        return hash(id(self))

    def __eq__(self, other):
        """ make equality mean identity """
        return id(self) == id(other)


def test_example_usage():

    """ any class inheriting MutableHashable can be used as a key in a dictionary """

    class ExampleUsage(MutableHashable):
        def __init__(self, arr: np.array):
            self.arr = arr

    e1 = ExampleUsage(np.zeros(100))
    d: dict = {e1: 'foo'}
    assert e1 in d and d[e1] == 'foo'

    e1.a = np.ones(100)
    assert e1 in d and d[e1] == 'foo'


class Mapping:

    """ a mapping which allows mutable keys, by using MutableHashable objects,
     at the cost of forgoing the use of the standard equality operator directly
     over the MutableHashable objects """

    def __init__(self):
        self._dict = dict[MutableHashable, Any]()

    def __getitem__(self, key: MutableHashable):
        return self._dict[key]

    def __setitem__(self, key: MutableHashable, value) -> MutableHashable:
        assert isinstance(key, MutableHashable)
        self._dict[key] = value
        return key

    def __contains__(self, key: MutableHashable):
        return key in self._dict

    def __len__(self):
        return len(self._dict)

    def __iter__(self):
        return iter(self._dict)

    def __repr__(self):
        return repr(self._dict)


def test():

    # need to be careful not to introduce an eq method in classes inheriting MutableHashable
    @dataclass(eq=False)
    class Foo(MutableHashable):
        a: int
        b: int
        def equals(self, other):
            return self.a == other.a and self.b == other.b

    mapping = Mapping()
    k1 = Foo(1, 2)
    mapping[k1] = 'foo'
    assert k1 in mapping and mapping[k1] == 'foo'

    k2 = Foo(1, 2)
    mapping[k2] = 'bar'
    assert k1 in mapping and k2 in mapping
    assert k1.equals(k2)