231
  • A frozen set is a frozenset.
  • A frozen list could be a tuple.
  • What would a frozen dict be? An immutable, hashable dict.

I guess it could be something like collections.namedtuple, but that is more like a frozen-keys dict (a half-frozen dict). Isn't it?

A "frozendict" should be a frozen dictionary, it should have keys, values, get, etc., and support in, for, etc.

update :
* there it is : https://www.python.org/dev/peps/pep-0603

2

13 Answers 13

153

Python doesn't have a builtin frozendict type. It turns out this wouldn't be useful too often (though it would still probably be useful more often than frozenset is).

The most common reason to want such a type is when memoizing function calls for functions with unknown arguments. The most common solution to store a hashable equivalent of a dict (where the values are hashable) is something like tuple(sorted(kwargs.items())).

This depends on the sorting not being a bit insane. Python cannot positively promise sorting will result in something reasonable here. (But it can't promise much else, so don't sweat it too much.)


You could easily enough make some sort of wrapper that works much like a dict. It might look something like (In Python 3.10 and later, replace collections.Mapping with collections.abc.Mapping):

import collections

class FrozenDict(collections.Mapping):
    """Don't forget the docstrings!!"""
    
    def __init__(self, *args, **kwargs):
        self._d = dict(*args, **kwargs)
        self._hash = None

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

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

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

    def __hash__(self):
        # It would have been simpler and maybe more obvious to 
        # use hash(tuple(sorted(self._d.iteritems()))) from this discussion
        # so far, but this solution is O(n). I don't know what kind of 
        # n we are going to run into, but sometimes it's hard to resist the 
        # urge to optimize when it will gain improved algorithmic performance.
        if self._hash is None:
            hash_ = 0
            for pair in self.items():
                hash_ ^= hash(pair)
            self._hash = hash_
        return self._hash

It should work great:

>>> x = FrozenDict(a=1, b=2)
>>> y = FrozenDict(a=1, b=2)
>>> x is y
False
>>> x == y
True
>>> x == {'a': 1, 'b': 2}
True
>>> d = {x: 'foo'}
>>> d[y]
'foo'
28
  • 11
    I don't know what level of thread safety people worry about with this kind of thing, but in that respect your __hash__ method could be slightly improved. Simply use a temporary variable when calculating the hash, and only set self._hash once you have the final value. That way another thread getting a hash while the first is calculating will simply do redundant calculation, rather than getting an incorrect value.
    – Jeff DQ
    Commented Jun 2, 2011 at 17:02
  • 30
    @Jeff As a rule, all code everywhere is not thread-safe, and you should wrap it around some synchronization structures in order to safely use that code. Also, your particular notion of thread safety relies on the atomicity of object attribute assignment, which is far from guaranteed. Commented Jun 3, 2011 at 1:07
  • 9
    @Anentropic, That's not true at all. Commented Nov 10, 2011 at 14:08
  • 29
    Be warned: This "FrozenDict" is not necessarily frozen. There is nothing to stop you from putting a mutable list as a value, in which case hashing will throw an error. There's nothing necessarily wrong with that, but users should be aware. Another thing: This hashing algorithm is poorly chosen, very prone to hash collisions. For example {'a':'b'} hashes the same as {'b':'a'} and {'a':1, 'b':2} hashes the same as {'a':2, 'b':1}. Better choice would be self._hash ^= hash((key, value)) Commented Nov 11, 2012 at 18:20
  • 9
    If you add a mutable entry in an immutable object, the two possible behaviors are to throw an error on creating the object, or throw an error on hashing the object. Tuples do the latter, frozenset does the former. I definitely think you made a good decision to take the latter approach, all things considered. Nevertheless, I think that people might see that FrozenDict and frozenset have similar names, and jump to a conclusion that they should behave similarly. So I think it is worth warning people about this difference. :-) Commented Nov 11, 2012 at 19:52
105

Curiously, although we have the seldom useful frozenset, there's still no frozen mapping. The idea was rejected in PEP 416 -- Add a frozendict builtin type. This idea may be revisited in a later Python release, see PEP 603 -- Adding a frozenmap type to collections.

So the Python 2 solution to this:

def foo(config={'a': 1}):
    ...

Still seems to be the usual:

def foo(config=None):
    if config is None:
        config = {'a': 1}  # default config
    ...

In Python 3 you have the option of this:

from types import MappingProxyType

default_config = {'a': 1}
DEFAULTS = MappingProxyType(default_config)

def foo(config=DEFAULTS):
    ...

Now the default config can be updated dynamically, but remain immutable where you want it to be immutable by passing around the proxy instead.

So changes in the default_config will update DEFAULTS as expected, but you can't write to the mapping proxy object itself.

Admittedly it's not really the same thing as an "immutable, hashable dict", but it might be a decent substitute for some use cases of a frozendict.

2
  • 5
    Is there any particular reason to store the proxy in a module variable? Why not just def foo(config=MappingProxyType({'a': 1})):? Your example still allows global modification through default_config, too.
    – jpmc26
    Commented May 26, 2018 at 3:20
  • It's not hashable. hash(MappingProxyType({'a':1})) yeilds TypeError: unhashable type: 'mappingproxy'. (This is mentioned in the last sentence. Just further emphasizing this.) Commented Jun 25 at 15:06
27

Assuming the keys and values of the dictionary are themselves immutable (e.g. strings) then:

>>> d
{'forever': 'atones', 'minks': 'cards', 'overhands': 'warranted', 
 'hardhearted': 'tartly', 'gradations': 'snorkeled'}
>>> t = tuple((k, d[k]) for k in sorted(d.keys()))
>>> hash(t)
1524953596
7
  • 1
    This is a good, canonical, immutable representation of a dict (barring insane comparison behavior messing up the sort). Commented Apr 24, 2010 at 16:06
  • 6
    @devin: agreed in full, but I'll let my post stand as an example that there's often an even better way.
    – msw
    Commented May 9, 2010 at 0:03
  • 19
    Even better would be to put it in a frozenset, which does not require the keys or values to have a consistent ordering defined.
    – asmeurer
    Commented May 22, 2012 at 22:09
  • 12
    Only one problem with this: you no longer have a mapping. That would be the whole point of having the frozen dict in the first place. Commented Jul 29, 2016 at 13:19
  • 4
    This method is really nice when going back to a dict. simply dict(t) Commented Aug 14, 2018 at 2:13
26

There is no frozendict in plain Python, but you can use types.MappingProxyType that was added to the standard library in Python 3.3:

>>> from types import MappingProxyType
>>> foo = MappingProxyType({'a': 1})
>>> foo['a'] = 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> foo
mappingproxy({'a': 1})
>>> # This is unhashable
>>> hash(foo)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'mappingproxy'
2
  • 3
    with the caveat: TypeError: can't pickle mappingproxy objects
    – Radu
    Commented Sep 2, 2019 at 17:35
  • 16
    Issue with this is MappingProxyType is still unhashable.
    – Jab
    Commented Jul 26, 2020 at 20:40
21

Install frozendict

pip install frozendict

Use it!

from frozendict import frozendict

def smth(param = frozendict({})):
    pass
1
  • This is also nice because it is hashable and one can inherit from frozendict as a base class. Neither of those is possible if you use MappingProxyType.
    – spacether
    Commented Aug 23, 2021 at 20:37
12

I think of frozendict everytime I write a function like this:

def do_something(blah, optional_dict_parm=None):
    if optional_dict_parm is None:
        optional_dict_parm = {}
6
  • 10
    Easier formulation: optional_dict_parm = optional_dict_parm or {}
    – Emmanuel
    Commented Jun 13, 2012 at 12:08
  • 2
    In this case you can use types.MappingProxyType({}) as default value for argument. Commented Apr 10, 2015 at 19:50
  • @GingerPlusPlus could you write that up as an answer?
    – jonrsharpe
    Commented Jun 4, 2015 at 7:30
  • @jonrsharpe: it seems like @wim already did that. Commented Jun 13, 2015 at 14:38
  • 4
    @Emmanuel You want the is None check to catch falsy arguments, like for example MappingProxyType({}), or if someone made a typo, 0 for example.
    – wjandrea
    Commented Nov 2, 2021 at 20:38
11

Here is the code I've been using. I subclassed frozenset. The advantages of this are the following.

  1. This is a truly immutable object. No relying on the good behavior of future users and developers.
  2. It's easy to convert back and forth between a regular dictionary and a frozen dictionary. FrozenDict(orig_dict) --> frozen dictionary. dict(frozen_dict) --> regular dict.

Update Jan 21 2015: The original piece of code I posted in 2014 used a for-loop to find a key that matched. That was incredibly slow. Now I've put together an implementation which takes advantage of frozenset's hashing features. Key-value pairs are stored in special containers where the __hash__ and __eq__ functions are based on the key only. This code has also been formally unit-tested, unlike what I posted here in August 2014.

MIT-style license.

if 3 / 2 == 1:
    version = 2
elif 3 / 2 == 1.5:
    version = 3

def col(i):
    ''' For binding named attributes to spots inside subclasses of tuple.'''
    g = tuple.__getitem__
    @property
    def _col(self):
        return g(self,i)
    return _col

class Item(tuple):
    ''' Designed for storing key-value pairs inside
        a FrozenDict, which itself is a subclass of frozenset.
        The __hash__ is overloaded to return the hash of only the key.
        __eq__ is overloaded so that normally it only checks whether the Item's
        key is equal to the other object, HOWEVER, if the other object itself
        is an instance of Item, it checks BOTH the key and value for equality.

        WARNING: Do not use this class for any purpose other than to contain
        key value pairs inside FrozenDict!!!!

        The __eq__ operator is overloaded in such a way that it violates a
        fundamental property of mathematics. That property, which says that
        a == b and b == c implies a == c, does not hold for this object.
        Here's a demonstration:
            [in]  >>> x = Item(('a',4))
            [in]  >>> y = Item(('a',5))
            [in]  >>> hash('a')
            [out] >>> 194817700
            [in]  >>> hash(x)
            [out] >>> 194817700
            [in]  >>> hash(y)
            [out] >>> 194817700
            [in]  >>> 'a' == x
            [out] >>> True
            [in]  >>> 'a' == y
            [out] >>> True
            [in]  >>> x == y
            [out] >>> False
    '''

    __slots__ = ()
    key, value = col(0), col(1)
    def __hash__(self):
        return hash(self.key)
    def __eq__(self, other):
        if isinstance(other, Item):
            return tuple.__eq__(self, other)
        return self.key == other
    def __ne__(self, other):
        return not self.__eq__(other)
    def __str__(self):
        return '%r: %r' % self
    def __repr__(self):
        return 'Item((%r, %r))' % self

class FrozenDict(frozenset):
    ''' Behaves in most ways like a regular dictionary, except that it's immutable.
        It differs from other implementations because it doesn't subclass "dict".
        Instead it subclasses "frozenset" which guarantees immutability.
        FrozenDict instances are created with the same arguments used to initialize
        regular dictionaries, and has all the same methods.
            [in]  >>> f = FrozenDict(x=3,y=4,z=5)
            [in]  >>> f['x']
            [out] >>> 3
            [in]  >>> f['a'] = 0
            [out] >>> TypeError: 'FrozenDict' object does not support item assignment

        FrozenDict can accept un-hashable values, but FrozenDict is only hashable if its values are hashable.
            [in]  >>> f = FrozenDict(x=3,y=4,z=5)
            [in]  >>> hash(f)
            [out] >>> 646626455
            [in]  >>> g = FrozenDict(x=3,y=4,z=[])
            [in]  >>> hash(g)
            [out] >>> TypeError: unhashable type: 'list'

        FrozenDict interacts with dictionary objects as though it were a dict itself.
            [in]  >>> original = dict(x=3,y=4,z=5)
            [in]  >>> frozen = FrozenDict(x=3,y=4,z=5)
            [in]  >>> original == frozen
            [out] >>> True

        FrozenDict supports bi-directional conversions with regular dictionaries.
            [in]  >>> original = {'x': 3, 'y': 4, 'z': 5}
            [in]  >>> FrozenDict(original)
            [out] >>> FrozenDict({'x': 3, 'y': 4, 'z': 5})
            [in]  >>> dict(FrozenDict(original))
            [out] >>> {'x': 3, 'y': 4, 'z': 5}   '''

    __slots__ = ()
    def __new__(cls, orig={}, **kw):
        if kw:
            d = dict(orig, **kw)
            items = map(Item, d.items())
        else:
            try:
                items = map(Item, orig.items())
            except AttributeError:
                items = map(Item, orig)
        return frozenset.__new__(cls, items)

    def __repr__(self):
        cls = self.__class__.__name__
        items = frozenset.__iter__(self)
        _repr = ', '.join(map(str,items))
        return '%s({%s})' % (cls, _repr)

    def __getitem__(self, key):
        if key not in self:
            raise KeyError(key)
        diff = self.difference
        item = diff(diff({key}))
        key, value = set(item).pop()
        return value

    def get(self, key, default=None):
        if key not in self:
            return default
        return self[key]

    def __iter__(self):
        items = frozenset.__iter__(self)
        return map(lambda i: i.key, items)

    def keys(self):
        items = frozenset.__iter__(self)
        return map(lambda i: i.key, items)

    def values(self):
        items = frozenset.__iter__(self)
        return map(lambda i: i.value, items)

    def items(self):
        items = frozenset.__iter__(self)
        return map(tuple, items)

    def copy(self):
        cls = self.__class__
        items = frozenset.copy(self)
        dupl = frozenset.__new__(cls, items)
        return dupl

    @classmethod
    def fromkeys(cls, keys, value):
        d = dict.fromkeys(keys,value)
        return cls(d)

    def __hash__(self):
        kv = tuple.__hash__
        items = frozenset.__iter__(self)
        return hash(frozenset(map(kv, items)))

    def __eq__(self, other):
        if not isinstance(other, FrozenDict):
            try:
                other = FrozenDict(other)
            except Exception:
                return False
        return frozenset.__eq__(self, other)

    def __ne__(self, other):
        return not self.__eq__(other)


if version == 2:
    #Here are the Python2 modifications
    class Python2(FrozenDict):
        def __iter__(self):
            items = frozenset.__iter__(self)
            for i in items:
                yield i.key

        def iterkeys(self):
            items = frozenset.__iter__(self)
            for i in items:
                yield i.key

        def itervalues(self):
            items = frozenset.__iter__(self)
            for i in items:
                yield i.value

        def iteritems(self):
            items = frozenset.__iter__(self)
            for i in items:
                yield (i.key, i.value)

        def has_key(self, key):
            return key in self

        def viewkeys(self):
            return dict(self).viewkeys()

        def viewvalues(self):
            return dict(self).viewvalues()

        def viewitems(self):
            return dict(self).viewitems()

    #If this is Python2, rebuild the class
    #from scratch rather than use a subclass
    py3 = FrozenDict.__dict__
    py3 = {k: py3[k] for k in py3}
    py2 = {}
    py2.update(py3)
    dct = Python2.__dict__
    py2.update({k: dct[k] for k in dct})

    FrozenDict = type('FrozenDict', (frozenset,), py2)
3
  • 3
    Note that you have also licensed it under CC BY-SA 3.0, by posting it here. At least that's the prevalent view. I guess the legal basis for that is agreeing to some T&Cs when you first signed up. Commented Nov 1, 2015 at 1:44
  • 2
    I broke my brain trying to think of a way to look up the key hash without a dict. Redefining the hash of the Item to be the hash of the key is a neat hack!
    – clacke
    Commented Jul 28, 2016 at 13:20
  • 1
    Unfortunately, the run time of diff(diff({key})) is still linear in the size of the FrozenDict, while regular dict access time is constant in the average case.
    – Dennis
    Commented Dec 31, 2018 at 3:12
8

Subclassing dict

i see this pattern in the wild (github) and wanted to mention it:

class FrozenDict(dict):
    def __init__(self, *args, **kwargs):
        self._hash = None
        super(FrozenDict, self).__init__(*args, **kwargs)

    def __hash__(self):
        if self._hash is None:
            self._hash = hash(tuple(sorted(self.items())))  # iteritems() on py2
        return self._hash

    def _immutable(self, *args, **kws):
        raise TypeError('cannot change object - object is immutable')

    # makes (deep)copy alot more efficient
    def __copy__(self):
        return self

    def __deepcopy__(self, memo=None):
        if memo is not None:
            memo[id(self)] = self
        return self

    __setitem__ = _immutable
    __delitem__ = _immutable
    pop = _immutable
    popitem = _immutable
    clear = _immutable
    update = _immutable
    setdefault = _immutable

example usage:

d1 = FrozenDict({'a': 1, 'b': 2})
d2 = FrozenDict({'a': 1, 'b': 2})
d1.keys() 
assert isinstance(d1, dict)
assert len(set([d1, d2])) == 1  # hashable

Pros

  • support for get(), keys(), items() (iteritems() on py2) and all the goodies from dict out of the box without explicitly implementing them
  • uses internally dict which means performance (dict is written in c in CPython)
  • elegant simple and no black magic
  • isinstance(my_frozen_dict, dict) returns True - although python encourages duck-typing many packages uses isinstance(), this can save many tweaks and customizations

Cons

  • any subclass can override this or access it internally (you cant really 100% protect something in python, you should trust your users and provide good documentation).
  • if you care for speed, you might want to make __hash__ a bit faster.
2
  • 2
    I did a speed comparison in another thread and it turns out, overriding __setitem__ and inheriting dict is insanely fast compared to many alternatives.
    – Torxed
    Commented Jun 10, 2020 at 11:44
  • 2
    You can inherit from collections.UserDict. It was intended for that purpose, normal dict has lots of flaws when subclassed
    – Andrey
    Commented Mar 31, 2021 at 16:23
6

You may use frozendict from utilspie package as:

>>> from utilspie.collectionsutils import frozendict

>>> my_dict = frozendict({1: 3, 4: 5})
>>> my_dict  # object of `frozendict` type
frozendict({1: 3, 4: 5})

# Hashable
>>> {my_dict: 4}
{frozendict({1: 3, 4: 5}): 4}

# Immutable
>>> my_dict[1] = 5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/mquadri/workspace/utilspie/utilspie/collectionsutils/collections_utils.py", line 44, in __setitem__
    self.__setitem__.__name__, type(self).__name__))
AttributeError: You can not call '__setitem__()' for 'frozendict' object

As per the document:

frozendict(dict_obj): Accepts obj of dict type and returns a hashable and immutable dict

5

The main disadvantage of namedtuple is that it needs to be specified before it is used, so it's less convenient for single-use cases.

However, there is a practical workaround that can be used to handle many such cases. Let's say that you want to have an immutable equivalent of the following dict:

MY_CONSTANT = {
    'something': 123,
    'something_else': 456
}

This can be emulated like this:

from collections import namedtuple

MY_CONSTANT = namedtuple('MyConstant', 'something something_else')(123, 456)

It's even possible to write an auxiliary function to automate this:

def freeze_dict(data):
    from collections import namedtuple
    keys = sorted(data.keys())
    frozen_type = namedtuple(''.join(keys), keys)
    return frozen_type(**data)

a = {'foo':'bar', 'x':'y'}
fa = freeze_dict(data)
assert a['foo'] == fa.foo

Of course this works only for flat dicts, but it shouldn't be too difficult to implement a recursive version.

1
  • 2
    Same problem as with the other tuple answer: you have to do getattr(fa, x) instead of fa[x], no keys method at your finger tips, and all the other reasons a mapping can be desirable. Commented Jul 29, 2016 at 13:32
4

Yes, this is my second answer, but it is a completely different approach. The first implementation was in pure python. This one is in Cython. If you know how to use and compile Cython modules, this is just as fast as a regular dictionary. Roughly .04 to .06 micro-sec to retrieve a single value.

This is the file "frozen_dict.pyx"

import cython
from collections import Mapping

cdef class dict_wrapper:
    cdef object d
    cdef int h

    def __init__(self, *args, **kw):
        self.d = dict(*args, **kw)
        self.h = -1

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

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

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

    def __hash__(self):
        if self.h == -1:
            self.h = hash(frozenset(self.d.iteritems()))
        return self.h

class FrozenDict(dict_wrapper, Mapping):
    def __repr__(self):
        c = type(self).__name__
        r = ', '.join('%r: %r' % (k,self[k]) for k in self)
        return '%s({%s})' % (c, r)

__all__ = ['FrozenDict']

Here's the file "setup.py"

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules = cythonize('frozen_dict.pyx')
)

If you have Cython installed, save the two files above into the same directory. Move to that directory in the command line.

python setup.py build_ext --inplace
python setup.py install

And you should be done.

0
1

freeze implements frozen collections (dict, list and set) that are hashable, type-hinted and will recursively freeze the data you give them (when possible) for you.

pip install frz

Usage:

from freeze import FDict

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

a_frozen_dict = FDict(a_mutable_dict)

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

I needed to access fixed keys for something at one point for something that was a sort of globally-constanty kind of thing and I settled on something like this:

class MyFrozenDict:
    def __getitem__(self, key):
        if key == 'mykey1':
            return 0
        if key == 'mykey2':
            return "another value"
        raise KeyError(key)

Use it like

a = MyFrozenDict()
print(a['mykey1'])

WARNING: I don't recommend this for most use cases as it makes some pretty severe tradeoffs.

2
  • The following would be equal in power without the performance scarifices. However, this is just a simplification of the accepted answer... ``` class FrozenDict: def __init__(self, data): self._data = data def __getitem__(self, key): return self._data[key] ```
    – Yuval
    Commented Jun 26, 2019 at 9:41
  • @Yuval that answer is not equivalent. For starters the api is different as it needs data to init. This also implies it is no longer globally-accessible. Furthermore, if _data is mutated, your return value changes. I am aware that there are significant tradeoffs - like I said, I don't recommend this for most use cases.
    – Adverbly
    Commented Jun 26, 2019 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.