构造

frozenmap 实现了类似 dict 的构造 API

• frozenmap() 创建一个新的空不可变映射；
• frozenmap(**kwargs) 从 **kwargs 创建一个映射，例如 frozenmap(x=10, y=0, z=-1)
• frozenmap(collection) 从传递的 collection 对象创建一个映射。传递的 collection 对象可以是
  • 一个 dict，
  • 另一个 frozenmap，
  • 一个具有 items() 方法的对象，该方法预计会返回一系列键/值元组，或者
  • 一个键/值元组的可迭代对象。

数据访问

frozenmap 实现了 collection.abc.Mapping 协议。因此，getter、成员资格检查和迭代的工作方式与 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.

修改

frozenmap 实例是不可变的。也就是说，可以有效地生成不可变实例的修改副本。

修改操作的复杂度为 O(log N)，并且由于使用了结构共享，生成的 frozenmap 副本通常消耗很少的额外内存（有关更多详细信息，请阅读[6]）。

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.

迭代

由于 frozenmap 实现了标准 collections.abc.Mapping 协议，因此支持所有预期的迭代方法

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

与 dict 不同，frozenmap 中的迭代不会保留插入顺序。

散列

frozenmap 实例可以像 tuple 对象一样可散列

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

类型提示

可以使用标准类型提示语法为 frozenmap 进行类型提示

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

HAMT

HAMT 的关键设计约定是保证在给定键的哈希值时获得可预测的值。对于一对键和值，键的哈希值可用于确定哈希映射树中值的位置。

使用 HAMT 实现的不可变映射对于 set() 和 get() 操作具有 O(log N) 的性能。这是可能的，因为修改操作仅影响树的一个分支，从而可以重用未修改的分支，因此避免复制未修改的数据。

在[5] 中了解更多关于 HAMT 的信息。CPython 实现[1] 也对算法进行了相当详细的描述。

性能

上图表明

• 使用 HAMT 实现的 frozenmap 对所有基准测试的字典大小都显示接近 O(1) 的性能。
• dict.copy() 在使用大约 100-200 个项目时效率降低。

图 2 比较了 dict 与基于 HAMT 的不可变映射的查找成本。HAMT 查找时间平均比 Python dict 查找慢约 30%。这种性能差异存在，因为遍历浅层树的效率低于在平面连续数组中查找。

此外，引用[6]：“（使用 HAMT）意味着在实践中，虽然对持久哈希数组映射 Trie 的插入、删除和查找具有 O(log n) 的计算复杂度，但对于大多数应用程序来说，它们实际上是常数时间，因为需要极大量的条目才能使任何操作花费超过十几步。”

为什么是“frozenmap”而不是“FrozenMap”

小写“frozenmap”与内置的 frozenset 以及 collections.defaultdict 等类型很好地共鸣。

为什么是“frozenmap”而不是“frozendict”

“Dict”在 Python 中具有非常具体的含义

• dict 是 abc.MutableMapping 的具体实现，具有 O(1) 的 get 和 set 操作（frozenmap 的复杂度为 O(log N)）；
• Python 字典保留插入顺序。

提议的 frozenmap 没有这些特性。相反，frozenmap 的 set/get 操作的复杂度为 O(log N)，并且它只实现了 abc.Mapping 协议。