What would a “frozen dict” be?

by

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.iteritems())).

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

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'

More Related Contents:

  1. How do I sort a list of dictionaries by a value of the dictionary?
  2. What is the best way to implement nested dictionaries?
  3. How are Python’s Built In Dictionaries Implemented?
  4. In Python, when to use a Dictionary, List or Set?
  5. Hashable, immutable
  6. merging Python dictionaries
  7. What is the purpose of collections.ChainMap?
  8. Key-ordered dict in Python
  9. Creating a tree/deeply nested dict from an indented text file in python
  10. Using a Python Dictionary as a Key (Non-nested)
  11. Recursive diff of two dictionaries (keys and values)?
  12. How to make a dictionary that returns key for keys missing from the dictionary instead of raising KeyError?
  13. How expensive are Python dictionaries to handle?
  14. Adding counters deletes keys
  15. How to sort a list of dictionaries by a value of the dictionary in Python?
  16. Why must dictionary keys be immutable?
  17. Delete an element from a dictionary
  18. Modifying a Python dict while iterating over it
  19. Inverting a dictionary with list values
  20. How to print a dictionary’s key?
  21. What is the right way to treat Python argparse.Namespace() as a dictionary?
  22. How to print a dictionary line by line in Python?
  23. How to create a dictionary from a line of text?
  24. Convert list of strings to dictionary
  25. How to implement a binary search tree in Python?
  26. Is there a difference between using a dict literal and a dict constructor?
  27. Python Pickling Dictionary EOFError
  28. Using Python class as a data container [closed]
  29. How can I convert string values from a dictionary, into int/float datatypes?
  30. sorting list of nested dictionaries in python

Leave a Comment