Python: Can a custom mutable class be used as a key for a dictionary?

Question

Let's say we have a custom node class like this:

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

I have a node object that I'd like to use as a key for a dictionary.
My understanding is that an object should be immutable and hashable for it to be reliably used as a dictionary key, because a mutable object could result in a changing hash values and this object is mutable.

I know python does allow custom mutable objects to be used as dictionary keys, how does that work?

Update: Referenced links do not touch upon the mutability aspect of the custom object. They just provide a method to override the default implementation of the hash function. This question should be reopened as it is different from the referenced "duplicate" questions.

Answer: Default implementation of hash method for custom mutable object uses identity, which is guaranteed to be unique and constant for object's lifetime. A mutable custom object SHOULD NOT be overriding the default implementation of hash function. More detailed answer is provided below.

It partially answers my questions as it takes a very specific example where class has only one attribute of 'str' type which is immutable. I will answer this question as I figured how a class object with multiple attributes can be used as a key for dictionary even if it has attributes that are mutable. — Mr Matrix, Nov 27 '19 at 20:26
Possible duplicate of [What's a correct and good way to implement \_\_hash\_\_()?](https://stackoverflow.com/questions/2909106/whats-a-correct-and-good-way-to-implement-hash) — Mr Matrix, Nov 27 '19 at 20:58
@Anatolii I am afraid this question will have to be opened as reference links are not accurate answers for my question. Can it be done ? — Mr Matrix, Jan 05 '20 at 20:24
Sure, but, in your question, you should explain why those links are not proper answers. Otherwise, you won't get enough upvotes (besides me) for reopening the question. — Anatolii, Jan 05 '20 at 20:38
Done, I updated the question and also added a better improved answer. — Mr Matrix, Jan 06 '20 at 00:35

Mr Matrix · Accepted Answer · 2020-01-06T00:34:30.877

Node custom object is mutable from its class definition and any mutable object should not override the default implementation of hash method as default method uses identity, which is guaranteed to be unique and constant for object's lifetime. Doing so might cause the hash value of the object to change and it can cause lot of problems.

For example:

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.

But we can go ahead and override the hash method for an immutable object. Answer on this thread helped me understand how it works. For the following, we are going to assume that attributes of Node object will never change once the object has been created.

Idea here is to make sure your custom object implements hash and equality methods.

Equality method should be implemented in such a way that two logical equivalent object are always considered equal. For the given Node object here, two nodes would be considered equal if all their attributes are same. So we can build a key which is a tuple of all attributes. This works because tuples are immutable, so we are basically creating an immutable object containing all the attributes for the object and are going to use this for calculating hash.

Following implementation ensures that two logically equivalent nodes (having same attributes) have the same key and hence will generate the same hash value for two equal nodes.

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

Python: Can a custom mutable class be used as a key for a dictionary?

1 Answers1