Is there a Python equivalent of Java's IdentityHashMap?

Question

I'm walking a data structure and would like to build a dict mapping X->Y, where X is a field in the data structure I'm walking and Y is a field in the data structure I'm building on the fly. X is an unhashable type.

Answer 1

Trivially:

idmap = {}
idmap[id(x)] = y

Use the id of x as the dictionary key

Answer 2

The purpose of Java's IdentityHashMap is to simulate dynamic field. Since Python language already supports dynamic attributes directly, you don't need the map, just assign Y to an X's attribute

x.someSuchRelation = y;

Answer 3

You can just use a regular Python dict for this if you wrap your unhashable objects in another object. Specifically, something like this:

class Wrapper(object):
    def __init__(self, o):
        self.o = o

    def __hash__(self):
        return id(self.o)

    def __eq__(self, o):
        return hash(self) == hash(o)

Then just use it like some_dict[Wrapper(unhashable_object)].

This is a more useful approach than just using id(o) as the key if you also need to be able to access the object itself afterwards (as key.o, obviously). If you don't (and garbage collection isn't an issue), just use that.

Answer 4

Often, the broken solution given to this common problem is to use id. It is broken because id is only unique among existing objects, so the following can randomly happen:

>>> idmap = {}
>>> idmap[id(x)] = 42
>>> del x
>>> z = SomeObject()
>>> z in idmap
True

No explicit del statement has to happen, just adding a key to idmap inside a function could lead to the same result:

>>> def add_smthg(idmap):
>>>     x = SomeObject()
>>>     idmap[id(x)] = 42

>>> idmap = {}
>>> add_smthg(idmap)
>>> z = SomeObject()
>>> z in idmap
True

To avoid this, you have to keep a reference of each object you insert. IMHO the only viable option is to create new dictionnary / set classes:

class IdentitySet:
    def __init__(self, items=None):
        if items is None:
            items = []

        self._identities = {id(item): item for item in items}

    def add(self, item):
        self._identities[id(item)] = item
    
    def __delitem__(self, item):
        del self._identities[id(item)]

    def __contains__(self, item):
        return id(item) in self._identities


class IdentityDict:
    def __init__(self, pairs=None):
        if pairs is None:
            pairs = []

        self._identities = IdentitySet(k for k, _ in pairs)
        self._values = {id(k): v for k, v in pairs}

    def __getitem__(self, item):
        return self._values[id(item)]

    def __setitem__(self, item, value):
        self._identities.add(item)
        self._values[id(item)] = value
    
    def __delitem__(self, item):        
        del self._identities[item]
        del self._values[id(item)]
    
    def __contains__(self, item):
        return item in self._identities