Construction

frozenmap implements a dict-like construction API:

• frozenmap() creates a new empty immutable mapping;
• frozenmap(**kwargs) creates a mapping from **kwargs, e.g. frozenmap(x=10, y=0, z=-1)
• frozenmap(collection) creates a mapping from the passed collection object. The passed collection object can be:
  • a dict,
  • another frozenmap,
  • an object with an items() method that is expected to return a series of key/value tuples, or
  • an iterable of key/value tuples.

Data Access

frozenmap implements the collection.abc.Mapping protocol. Therefore, getters, membership checks, and iteration work the same way that they would for a dict:

m = frozenmap(foo='bar')

assert m['foo'] == 'bar'
assert m.get('foo') == 'bar'
assert 'foo' in m

assert 'baz' not in m
assert m.get('baz', 'missing') == 'missing'

assert m == m
assert m != frozenmap()  # m is not equal to an empty frozenmap

assert len(m) == 1

# etc.

Mutation

frozenmap instances are immutable. That said, it is possible to efficiently produce mutated copies of the immutable instance.

The complexity of mutation operations is O(log N) and the resulting frozenmap copies often consume very little additional memory due to the use of structural sharing (read [6] for more details.)

m = frozenmap(foo=1)
m2 = m.including('bar', 100)

print(m)   # will print frozenmap({'foo': 1})
print(m2)  # will print frozenmap({'foo': 1, 'bar': 100})

m = frozenmap(foo=1, bar=100)

m2 = m.excluding('foo')

print(m)   # will print frozenmap({'foo': 1, 'bar': 100})
print(m2)  # will print frozenmap({'bar': 1})

m3 = m.excluding('spam')  # will throw a KeyError('spam')

m = frozenmap(foo=1)

m2 = m.union({'spam': 'ham'})
print(m2)  # will print frozenmap({'foo': 1, 'spam': 'ham'})

m3 = m.union(foo=100, y=2)
print(m3)  # will print frozenmap({'foo': 100, 'y': 2})

print(m)   # will print frozenmap({'foo': 1})

numbers = frozenmap((i, i ** 2) for i in range(1_000_000))

with numbers.mutating() as copy:
    for i in numbers:
        if not (numbers[i] % 997):
            del copy[i]

    numbers_without_997_multiples = frozenmap(copy)

    # at this point, *numbers* still has 1_000_000 key/values, and
    # *numbers_without_997_multiples* is a copy of *numbers* without
    # values that are multiples of 997.

    for i in numbers:
        if not (numbers[i] % 593):
            del copy[i]

    numbers_without_593_multiples = frozenmap(copy)

    print(copy[10])  # will print 100.

print(copy[10])  # This will throw a ValueError as *copy*
                 # has been closed when the "with" block
                 # was executed.

Iteration

As frozenmap implements the standard collections.abc.Mapping protocol, so all expected methods of iteration are supported:

assert list(m) == ['foo']
assert list(m.items()) == [('foo', 'bar')]
assert list(m.keys()) == ['foo']
assert list(m.values()) == ['bar']

Iteration in frozenmap, unlike in dict, does not preserve the insertion order.

Hashing

frozenmap instances can be hashable just like tuple objects:

hash(frozenmap(foo='bar'))  # works
hash(frozenmap(foo=[]))     # will throw an error

Typing

It is possible to use the standard typing notation for frozenmaps:

m: frozenmap[str, int] = frozenmap()

HAMT

The key design contract of HAMT is the guarantee of a predictable value when given the hash of a key. For a pair of key and value, the hash of the key can be used to determine the location of value in the hash map tree.

Immutable mappings implemented with HAMT have O(log N) performance for set() and get() operations. This efficiency is possible because mutation operations only affect one branch of the tree, making it possible to reuse non-mutated branches, and, therefore, avoiding copying of unmodified data.

Read more about HAMT in [5]. The CPython implementation [1] has a fairly detailed description of the algorithm as well.

Performance

The above chart demonstrates that:

• frozenmap implemented with HAMT displays near O(1) performance for all benchmarked dictionary sizes.
• dict.copy() becomes less efficient when using around 100-200 items.

Figure 2 compares the lookup costs of dict versus a HAMT-based immutable mapping. HAMT lookup time is ~30% slower than Python dict lookups on average. This performance difference exists since traversing a shallow tree is less efficient than lookup in a flat continuous array.

Further to that, quoting [6]: “[using HAMT] means that in practice while insertions, deletions, and lookups into a persistent hash array mapped trie have a computational complexity of O(log n), for most applications they are effectively constant time, as it would require an extremely large number of entries to make any operation take more than a dozen steps.”

Why “frozenmap” and not “FrozenMap”

The lower-case “frozenmap” resonates well with the frozenset built-in as well as with types like collections.defaultdict.

Why “frozenmap” and not “frozendict”

“Dict” has a very specific meaning in Python:

• a dict is a concrete implementation of abc.MutableMapping with O(1) get and set operations (frozenmap has O(log N) complexity);
• Python dicts preserve insertion order.

The proposed frozenmap does not have these mentioned properties. Instead, frozenmap has an O(log N) cost of set/get operations, and it only implements the abc.Mapping protocol.