Construction

frozenmap implements adict-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 passedcollection object. The passedcollection object can be:
  • adict,
  • anotherfrozenmap,
  • an object with anitems() method that is expected to returna series of key/value tuples, or
  • an iterable of key/value tuples.

Data Access

frozenmap implements thecollection.abc.Mapping protocol.Therefore, getters, membership checks, and iteration work the sameway that they would for adict:

m=frozenmap(foo='bar')assertm['foo']=='bar'assertm.get('foo')=='bar'assert'foo'inmassert'baz'notinmassertm.get('baz','missing')=='missing'assertm==massertm!=frozenmap()# m is not equal to an empty frozenmapassertlen(m)==1# etc.

Mutation

frozenmap instances are immutable. That said, it is possibleto efficiently produce mutatedcopies of the immutable instance.

The complexity of mutation operations is O(log N) and the resultingfrozenmap copies often consume very little additional memory dueto 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)foriinrange(1_000_000))withnumbers.mutating()ascopy:foriinnumbers:ifnot(numbers[i]%997):delcopy[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.foriinnumbers:ifnot(numbers[i]%593):delcopy[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

Asfrozenmap implements the standardcollections.abc.Mappingprotocol, so all expected methods of iteration are supported:

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

Iteration infrozenmap, unlike indict, does not preserve theinsertion order.

Hashing

frozenmap instances can be hashable just liketuple objects:

hash(frozenmap(foo='bar'))# workshash(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 predictablevalue when given the hash of akey. For a pair ofkey andvalue,the hash of thekey can be used to determine the location ofvalue in the hash map tree.

Immutable mappings implemented with HAMT have O(log N) performanceforset() andget() operations. This efficiency is possiblebecause 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 afairly detailed description of the algorithm as well.

Performance

The above chart demonstrates that:

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

Figure 2 compares the lookup costs ofdict versus a HAMT-basedimmutable mapping. HAMT lookup time is ~30% slower than Python dictlookups on average. This performance difference exists since traversinga shallow tree is less efficient than lookup in a flat continuous array.

Further to that, quoting[6]: “[using HAMT] means that in practicewhile insertions, deletions, and lookups into a persistent hash arraymapped trie have a computational complexity of O(log n), for mostapplications they are effectively constant time, as it would requirean extremely large number of entries to make any operation take morethan a dozen steps.”

Why “frozenmap” and not “FrozenMap”

The lower-case “frozenmap” resonates well with thefrozensetbuilt-in as well as with types likecollections.defaultdict.

Why “frozenmap” and not “frozendict”

“Dict” has a very specific meaning in Python:

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

The proposedfrozenmap does not have these mentionedproperties. Instead,frozenmap has an O(log N) cost of set/getoperations, and it only implements theabc.Mapping protocol.