Frozen dictionaries (Python recipe) by Oren Tirosh

ActiveState Code (http://code.activestate.com/recipes/414283/)

Ooops. I forgot about keyword args:

    def __new__(cls, *args, **kw):
        new = dict.__new__(cls)
        dict.__init__(new, *args, **kw)
        return new

    def __init__(self, *args, **kw):
        pass

>>> set([frozendict(a=1,b=2), frozendict(a=5), frozendict(b=2,a=1)])
set([frozendict({'a': 1, 'b': 2}), frozendict({'a': 5})])

Dictionaries in arbitrary order. Is not the order consistent, as long as the dictionary is not modified in the meantime? This is what I get from the (version 2.3) Library Reference, section 2.3.7: Mappings, and it is consistent with my experience. If so, you really don't need to sort the items.

Dictionary order consistency. If you iterate over the same dictionary object two times in a row without changing it in the middle the order will stay the same. Python makes no guarantees that two different dictionaries testing as equal will have the same item order.

The __init__ method can be removed, and maybe the __hash__ method can be faster (and use less memory) using a .sort() instead of sorted(), and using if "_cached_hash" in self.__dict__: instead of the the try-except.

Nope. __init__ is there for a reason.

dict.__init__ is essentially equivalent to dict.update and could be used to modify the frozen dictionary. It's ignored rather than raising an exception because it will be called once on initialization.

Doesn't work when dict's values are mutable.

>>> hash(frozendict({'k': [1,2,3]}))

Traceback (most recent call last):
  File "", line 1, in
    hash(frozendict({'k': [1,2,3]}))
  File "C:/pydev\frozendict.py", line 21, in __hash__
    h = self._cached_hash = hash(tuple(sorted(self.items())))
TypeError: list objects are unhashable

Extended version of frozent dict. This extended version of the code above will also "freeze" dictionaries and lists stored as values of the dictionary. If dictionaries/lists are found among the values, they will be handled recursively.

class frozendict(dict):
    def _blocked_attribute(obj):
        raise AttributeError, "A frozendict cannot be modified."
    _blocked_attribute = property(_blocked_attribute)

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

    def __new__(cls, *args, **kw):
        new = dict.__new__(cls)

        args_ = []
        for arg in args:
            if isinstance(arg, dict):
                arg = copy.copy(arg)
                for k, v in arg.items():
                    if isinstance(v, dict):
                        arg[k] = frozendict(v)
                    elif isinstance(v, list):
                        v_ = list()
                        for elm in v:
                            if isinstance(elm, dict):
                                v_.append( frozendict(elm) )
                            else:
                                v_.append( elm )
                        arg[k] = tuple(v_)
                args_.append( arg )
            else:
                args_.append( arg )

        dict.__init__(new, *args_, **kw)
        return new

    def __init__(self, *args, **kw):
        pass

    def __hash__(self):
        try:
            return self._cached_hash
        except AttributeError:
            h = self._cached_hash = hash(tuple(sorted(self.items())))
            return h

    def __repr__(self):
        return "frozendict(%s)" % dict.__repr__(self)

The hash function relies on sorting, but many data types (e.g. sets) do not sort consistently. A more reliable alternative is:

h = self._cached_hash = hash(frozenset(self.items()))

(In addition, for large data sets this ought to run in O(n) time rather than the O(n log n) of the original.)