构建

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']

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

哈希

frozenmap 实例可以像 tuple 对象一样是可哈希的

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

类型标注

可以使用标准的类型标注来表示 frozenmaps

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

HAMT

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

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

在 [5] 中阅读更多关于 HAMT 的信息。CPython 实现 [1] 也有一个相当详细的算法描述。

性能

以上图表表明

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

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

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

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

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

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

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

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

提议的 frozenmap 不具备上述属性。相反，frozenmap 的设置/获取操作成本为 O(log N)，并且它只实现了 abc.Mapping 协议。