In python, how can you retrieve a key from a dictionary?

Question

I have a hashable identifier for putting things in a dictionary:

class identifier():
    def __init__(self, d):
        self.my_dict = d
        self.my_frozenset = frozenset(d.items())
    def __getitem__(self, item):
        return self.my_dict[item]
    def __hash__(self):
        return hash(self.my_frozenset)
    def __eq__(self, rhs):
        return self.my_frozenset == rhs.my_frozenset
    def __ne__(self, rhs):
       return not self == rhs

I have a node type that encapsulates identifer for purposes of hashing and equality:

class node:
    def __init__(self, id, value):
        # id is of type identifier
        self.id = id
        self.value = value
        # define other data here...
    def __hash__(self):
        return hash(self.id)
    def __eq__(self, rhs):
        if isinstance(rhs, node):
            return self.id == rhs.id
        ### for the case when rhs is an identifier; this allows dictionary
        ### node lookup of a key without wrapping it in a node
        return self.id == rhs
    def __ne__(self, rhs):
        return not self == rhs

I put some nodes into a dictionary:

d = {}
n1 = node(identifier({'name':'Bob'}), value=1)
n2 = node(identifier({'name':'Alex'}), value=2)
n3 = node(identifier({'name':'Alex', 'nationality':'Japanese'}), value=3)
d[n1] = 'Node 1'
d[n2] = 'Node 2'
d[n3] = 'Node 3'

Some time later, I have only an identifier:

my_id = identifier({'name':'Alex'})

Is there any way to efficiently lookup the node that has been stored with this identifier in this dictionary?

Please note that this is a little trickier than it sounds; I know that I can trivially use d[my_id] to retrieve the associated item 'Node 2', but I want to efficiently return a reference to n2.

I know that I could do it by looking at every element in d, but I've tried that and it's much too slow (the dictionary has thousands of items in it and I do this a fair number of times).

I know that internally dict is using the hash and eq operators for that identifier to store node n2 and its associated item, 'Node 2'. In fact, using my_id to lookup 'Node 2' actually needs to lookup n2 as an intermediate step, so this should definitely be possible.

I am using this to store data in a graph. The nodes have a lot of additional data (where I put value) that is not used in the hash. I didn't create the graph package I'm using (networkX), but I can see the dictionary that stores my nodes. I could also keep an extra dictionary around of identifiers to nodes, but this would be a pain (I'd need to wrap the graph class and rewrite all add node, remove node, add nodes from list, remove nodes from list, add edge, etc. type functions to keep that dictionary up to date).

This is quite the puzzle. Any help would be really appreciated!

Answer 1

Instead of

d[n1] = 'Node 1'

use:

d[n1] = ('Node 1', n1)

Then you have access to n1 no matter how you found the value.

I don't believe there is a way with dictionaries to retrieve the original key k1 if all you have is a k2 equal to k1.

Answer 2

Have two dictionaries. - Whenever you add a key/value to the primary dictionary, also add them to the reverse dictionary, but with the key/value swapped.

For example:

# When adding a value:
d[n2] = value;
# Must also add to the reverse dictionary:
rev[value] = d

# This means that:
value = d[n2]
# Will be able to efficiently find out the key used with:
key = rev[value]