Python key error - for key in dictionary: dictionary[key]

Question

I am programming a Graph class to handle pathing in a game. Graphs have one field, mapping, which is a dictionary that maps nodes to edges. In one of my functions, I have the following bit of code:

for key in self.mapping:
    connected_edges = self.mapping[key]

At one point in my program, I call this code and I get the following error:

KeyError: <node.Node instance at 0x00000000026F3088>

How is this even possible? I'm only looping through the keys that are in the dictionary, so how can a key not be in it? For a sanity check, I took the length of the dictionary and saw it was 5, ie: not 0. Any ideas? Thanks!

I do implement my own eq and hash method for both Node and Edge. Here are those parts of the classes:

class Node:
    """
    A node connects to other nodes via Edges to form a graph

    Each node has a unique identifier (ID) so they can be mathematically distinct. Optionally, a node also has an x and
    y coordinate.
    """
    n_nodes = 0
    def __init__(self, x=0, y=0):
        """
        Create a node with its own unique identifier.

        :param x: x coordinate
        :param y: y coordinate
        :return: an initialized Node object
        """
        Node.n_nodes += 1
        self.ID = Node.n_nodes
        self.x = x  # x position
        self.y = y  # y position

    def __eq__(self, other):
        return (self.ID, self.x, self.y) == (other.ID, other.x, other.y)

    def __hash__(self):
        return hash((self.ID, self.x, self.y))



class Edge:
    """
    An edge is a connection between two nodes.

    Edges have a unique identifier and a list of two nodes. Optionally, an edge can have a numerical weight. Edges can
    also be directed, in which case it is only possible to traverse the edge in one direction, not both.
    """
    n_edges = 0
    def __init__(self, node1, node2, weight=1, directed=False):
        """
        Create an edge with its own unique identifier

        :param node1: node at first end of the edge
        :param node2: node at second end of the edge
        :param weight: numerical weight of the connection between node1 and node2
        :param directed: if True, the edge is oriented from node1 to node 2
        :return: an initialized Edge object
        """
        Edge.n_edges += 1
        self.ID = Edge.n_edges
        self.weight = weight
        self.nodes = frozenset([node1, node2])
        self.directed = directed

    def __eq__(self, other):
        return (self.ID, self.weight, self.nodes, self.directed) == (other.ID, other.weight, other.nodes, other.directed)

    def __hash__(self):
        return hash((self.ID, self.weight, self.nodes, self.directed))

Answer 1

If your objects implement __eq__ and __hash__, you have to make sure that the hash value does not change after the object is created. If you mutate your objects after creating them, you can get them into an inconsistent state where the hash value stored for them in a dictionary is inconsistent with their current hash value. Here's an example:

class Foo(object):
    def __init__(self, x):
        self.x = x
    def __eq__(self, other):
        return self.x == other.x
    def __hash__(self):
        return self.x

a, b, c = Foo(1), Foo(2), Foo(3)

x = {a: 1, b: 2, c: 3}

for key in x:
    print(x[key])

a.x = 100

for key in x:
    print(x[key])

The result is a KeyError similar to the one you received. Presumably you are mutating your Node objects somewhere along the line.

Mutable objects cannot be hashed (or at least, their hash value cannot depend on any of their mutable state).