Using non-hashable Python objects as keys in dictionaries

Question

Python doesn't allow non-hashable objects to be used as keys in other dictionaries. As pointed out by Andrey Vlasovskikh, there is a nice workaround for the special case of using non-nested dictionaries as keys:

frozenset(a.items())#Can be put in the dictionary instead

Is there a method of using arbitrary objects as keys in dictionaries?

Example:

How would this be used as a key?

{"a":1, "b":{"c":10}}

It is extremely rare that you will actually have to use something like this in your code. If you think this is the case, consider changing your data model first.

Exact use case

The use case is caching calls to an arbitrary keyword only function. Each key in the dictionary is a string (the name of the argument) and the objects can be quite complicated, consisting of layered dictionaries, lists, tuples, ect.

Related problems

This sub-problem has been split off from the problem here. Solutions here deal with the case where the dictionaries is not layered.

Answer 1

With recursion!

def make_hashable(h):
    items = h.items()
    for item in items:
        if type(items) == dict:
            item = make_hashable(item)
    return frozenset(items)

You can add other type tests for any other mutable types you want to make hashable. It shouldn't be hard.

Answer 2

Don't. I agree with Andreys comment on the previous question that is doesn't make sense to have dictionaries as keys, and especially not nested ones. Your data-model is obviously quite complex, and dictionaries are probably not the right answer. You should try some OO instead.

Answer 3

If you really must, make your objects hashable. Subclass whatever you want to put in as a key, and provide a __hash__ function which returns an unique key to this object.

To illustrate:

>>> ("a",).__hash__()
986073539
>>> {'a': 'b'}.__hash__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable

If your hash is not unique enough you will get collisions. May be slow as well.

Answer 4

Based off solution by Chris Lutz. This solves it for every case I am aware of except objects like streams that are changed by iteration.

import collections

def make_hashable(obj):
    """WARNING: This function only works on a limited subset of objects
    Make a range of objects hashable. 
    Accepts embedded dictionaries, lists or tuples (including namedtuples)"""
    if isinstance(obj, collections.Hashable):
        #Fine to be hashed without any changes
        return obj
    elif isinstance(obj, collections.Mapping):
        #Convert into a frozenset instead
        items=list(obj.items())
        for i, item in enumerate(items):
                items[i]=make_hashable(item)
        return frozenset(items)
    elif isinstance(obj, collections.Iterable):
        #Convert into a tuple instead
        ret=[type(obj)]
        for i, item in enumerate(obj):
                ret.append(make_hashable(item))
        return tuple(ret)
    #Use the id of the object
    return id(obj)

Answer 5

I totally disagree with comments & answers saying that this shouldn't be done for data model purity reason.

A dictionary associates an object with another object using the former one as a key. Dictionaries can't be used as keys because they're not hashable. This doesn't make any less meaningful/practical/necessary to map dictionaries to other objects.

As I understand the Python binding system, you can bind any dictionary to a number of variables (or the reverse, depends on your terminology) which means that these variables all know the same unique 'pointer' to that dictionary. Wouldn't it be possible to use that identifier as the hashing key ? If your data model ensures/enforces that you can't have two dictionaries with the same content used as keys then that seems to be a safe technique to me.

I should add that I have no idea whatsoever of how that can/should be done though.

I'm not entirely whether this should be an answer or a comment. Please correct me if needed.