Immutable dictionary, only use as a key for another dictionary

Question

I had the need to implement a hashable dict so I could use a dictionary as a key for another dictionary.

A few months ago I used this implementation: Python hashable dicts

However I got a notice from a colleague saying 'it is not really immutable, thus it is not safe. You can use it, but it does make me feel like a sad Panda'.

So I started looking around to create one that is immutable. I have no need to compare the 'key-dict' to another 'key-dict'. Its only use is as a key for another dictionary.

I have come up with the following:

class HashableDict(dict):
    """Hashable dict that can be used as a key in other dictionaries"""

    def __new__(self, *args, **kwargs):
        # create a new local dict, that will be used by the HashableDictBase closure class
        immutableDict = dict(*args, **kwargs)

        class HashableDictBase(object):
            """Hashable dict that can be used as a key in other dictionaries. This is now immutable"""

            def __key(self):
                """Return a tuple of the current keys"""
                return tuple((k, immutableDict[k]) for k in sorted(immutableDict))

            def __hash__(self):
                """Return a hash of __key"""
                return hash(self.__key())

            def __eq__(self, other):
                """Compare two __keys"""
                return self.__key() == other.__key() # pylint: disable-msg=W0212

            def __repr__(self):
                """@see: dict.__repr__"""
                return immutableDict.__repr__()

            def __str__(self):
                """@see: dict.__str__"""
                return immutableDict.__str__()

            def __setattr__(self, *args):
                raise TypeError("can't modify immutable instance")
            __delattr__ = __setattr__

        return HashableDictBase()

I used the following to test the functionality:

d = {"a" : 1}

a = HashableDict(d)
b = HashableDict({"b" : 2})

print a
d["b"] = 2
print a

c = HashableDict({"a" : 1})

test = {a : "value with a dict as key (key a)",
        b : "value with a dict as key (key b)"}

print test[a]
print test[b]
print test[c]

which gives:

{'a': 1}
{'a': 1}
value with a dict as key (key a)
value with a dict as key (key b)
value with a dict as key (key a)

as output

Is this the 'best possible' immutable dictionary that I can use that satisfies my requirements? If not, what would be a better solution?

Answer 1

If you are only using it as a key for another dict, you could go for frozenset(mutabledict.items()). If you need to access the underlying mappings, you could then use that as the parameter to dict.

mutabledict = dict(zip('abc', range(3)))
immutable = frozenset(mutabledict.items())
read_frozen = dict(immutable)
read_frozen['a'] # => 1

Note that you could also combine this with a class derived from dict, and use the frozenset as the source of the hash, while disabling __setitem__, as suggested in another answer. (@RaymondHettinger's answer for code which does just that).

Answer 2

The Mapping abstract base class makes this easy to implement:

import collections

class ImmutableDict(collections.Mapping):
    def __init__(self, somedict):
        self._dict = dict(somedict)   # make a copy
        self._hash = None

    def __getitem__(self, key):
        return self._dict[key]

    def __len__(self):
        return len(self._dict)

    def __iter__(self):
        return iter(self._dict)

    def __hash__(self):
        if self._hash is None:
            self._hash = hash(frozenset(self._dict.items()))
        return self._hash

    def __eq__(self, other):
        return self._dict == other._dict

Answer 3

I realize this has already been answered, but types.MappingProxyType is an analogous implementation for Python 3.3. Regarding the original question of safety, there is a discussion in PEP 416 -- Add a frozendict builtin type on why the idea of a frozendict was rejected.

Answer 4

In order for your immutable dictionary to be safe, all it needs to do is never change its hash. Why don't you just disable __setitem__ as follows:

class ImmutableDict(dict):
    def __setitem__(self, key, value):
        raise Exception("Can't touch this")
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

a = ImmutableDict({'a':1})
b = {a:1}
print b
print b[a]
a['a'] = 0

The output of the script is:

{{'a': 1}: 1}
1
Traceback (most recent call last):
  File "ex.py", line 11, in <module>
    a['a'] = 0
  File "ex.py", line 3, in __setitem__
    raise Exception("Can't touch this")
Exception: Can't touch this

Answer 5

Here is a link to pip install-able implementation of @RaymondHettinger's answer: https://github.com/pcattori/icicle

Simply pip install icicle and you can from icicle import FrozenDict!

Update: icicle has been deprecated in favor of maps: https://github.com/pcattori/maps (documentation, PyPI).

Answer 6

It appears I am late to post. Not sure if anyone else has come up with ideas. But here is my take on it. The Dict is immutable and hashable. I made it immutable by overriding all the methods, magic and otherwise, with a custom '_readonly' function that raises an Exception. This is done when the object is instantiated. To get around the problem of not being able to apply the values I set the 'hash' under '__new__'. I then I override the '__hash__'function. Thats it!

class ImmutableDict(dict):

_HASH = None

def __new__(cls, *args, **kwargs):
    ImmutableDict._HASH = hash(frozenset(args[0].items()))
    return super(ImmutableDict, cls).__new__(cls, args)

def __hash__(self):
    return self._HASH

def _readonly(self, *args, **kwards):
    raise TypeError("Cannot modify Immutable Instance")

__delattr__ = __setattr__ = __setitem__ = pop = update = setdefault = clear = popitem = _readonly

Test:

immutabled1 = ImmutableDict({"This": "That", "Cheese": "Blarg"})

dict1 = {immutabled1: "Yay"}

dict1[immutabled1]

"Yay"

dict1

{{'Cheese': 'Blarg', 'This': 'That'}: 'Yay'}

Answer 7

Variation of Raymond Hettinger's answer by wrapping the self._dict with types.MappingProxyType.

class ImmutableDict(collections.Mapping):
    """
    Copies a dict and proxies it via types.MappingProxyType to make it immutable.
    """
    def __init__(self, somedict):
        dictcopy = dict(somedict) # make a copy
        self._dict = MappingProxyType(dictcopy) # lock it
        self._hash = None

    def __getitem__(self, key):
        return self._dict[key]

    def __len__(self):
        return len(self._dict)

    def __iter__(self):
        return iter(self._dict)

    def __hash__(self):
        if self._hash is None:
            self._hash = hash(frozenset(self._dict.items()))
        return self._hash

    def __eq__(self, other):
        return self._dict == other._dict

    def __repr__(self):
        return str(self._dict)

Answer 8

You can use an enum:

import enum

KeyDict1 = enum.Enum('KeyDict1', {'InnerDictKey1':'bla', 'InnerDictKey2 ':2})

d = { KeyDict1: 'whatever', KeyDict2: 1, ...}

You can access the enums like you would a dictionary:

KeyDict1['InnerDictKey2'].value  # This is 2

You can iterate over the names, and get their values... It does everything you'd expect.

Answer 9

You can try using https://github.com/Lightricks/freeze

It provides recursively immutable and hashable dictionaries

from freeze import FDict

a_mutable_dict = {
    "list": [1, 2],
    "set": {3, 4},
}

a_frozen_dict = FDict(a_mutable_dict)

print(a_frozen_dict)
print(hash(a_frozen_dict))

# FDict: {'list': FList: (1, 2), 'set': FSet: {3, 4}}
# -4855611361973338606