首页 > 编程语言 > 详细

流畅的python 第三张 字典和集合

时间:2018-09-26 00:50:50      阅读:54      评论:0      收藏:0      [点我收藏+]

标签:形式   mce   contain   接口   行为   字符   同时   值对象   用户创建   

介绍

dict 类型不但在各种程序里广泛使用,它也是 Python 语言的基石。模块的命名空间、实例的属性和函数的关键字参数中都可以看到字典的身影。跟它有关的内置函数都在 __builtins__.__dict__模块中。


正是因为字典至关重要,Python 对它的实现做了高度优化,而散列表则是字典类型性能出众的根本原因。


集合(set)的实现其实也依赖于散列表,因此本章也会讲到它。反过来说,想要进一步理解集合和字典,就得先理解散列表的原理。

泛映射类型

collections.abc 模块中有 Mapping 和 MutableMapping 这两个抽象基类,它们的作用是为 dict 和其他类似的类型定义形式接口(在Python 2.6 到 Python 3.2 的版本中,这些类还不属于 collections.abc
模块,而是隶属于 collections 模块)。

技术分享图片

collections.abc 中的 MutableMapping 和它的超类的UML 类图(箭头从子类指向超类,抽象类和抽象方法的名称以斜体显示)

 

然而,非抽象映射类型一般不会直接继承这些抽象基类,它们会直接对dict 或是 collections.User.Dict 进行扩展。这些抽象基类的主要作用是作为形式化的文档,它们定义了构建一个映射类型所需要的最基
本的接口。然后它们还可以跟 isinstance 一起被用来判定某个数据是不是广义上的映射类型:

>>> my_dict = {}
>>> isinstance(my_dict, abc.Mapping)
True

这里用 isinstance 而不是 type 来检查某个参数是否为 dict 类型,因为这个参数有可能不是 dict,而是一个比较另类的映射类型。

标准库里的所有映射类型都是利用 dict 来实现的,因此它们有个共同的限制,即只有可散列的数据类型才能用作这些映射里的键(只有键有这个要求,值并不需要是可散列的数据类型)。

什么是可散列的数据类型?

如果一个对象是可散列的,那么在这个对象的生命周期中,它的散列值是不变的,而且这个对象需要实现 __hash__() 方法。另外可散列对象还要有 __qe__() 方法,这样才能跟其他键做比较。如果两个可散列对象是相等的,那么它们的散列值一定是一样的……

原子不可变数据类型(str、bytes 和数值类型)都是可散列类型,frozenset 也是可散列的,因为根据其定义,frozenset 里只能容纳可散列类型。元组的话,只有当一个元组包含的所有元素都是可散列类型的情况下,它才是可散列的。来看下面的元组tt、tl 和 tf:

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: list
>>> tf = (1, 2, frozenset([30, 40]))
>>> hash(tf)
-4118419923444501110

一般来讲用户自定义的类型的对象都是可散列的,散列值就是它们
的 id() 函数的返回值,所以所有这些对象在比较的时候都是不相
等的。如果一个对象实现了 __eq__ 方法,并且在方法中用到了这
个对象的内部状态的话,那么只有当所有这些内部状态都是不可变
的情况下,这个对象才是可散列的。

 

一般来讲用户自定义的类型的对象都是可散列的,散列值就是它们的 id() 函数的返回值,所以所有这些对象在比较的时候都是不相等的。如果一个对象实现了 __eq__ 方法,并且在方法中用到了这
个对象的内部状态的话,那么只有当所有这些内部状态都是不可变的情况下,这个对象才是可散列的。

>>> a = dict(one=1, two=2, three=3)
>>> b = {one: 1, two: 2, three: 3}
>>> c = dict(zip([one, two, three], [1, 2, 3]))
>>> d = dict([(two, 2), (one, 1), (three, 3)])
>>> e = dict({three: 3, one: 1, two: 2})
>>> a == b == c == d == e
True

用setdefault处理找不到的键

当字典 d[k] 不能找到正确的键的时候,Python 会抛出异常,这个行为符合 Python 所信奉的“快速失败”哲学。也许每个 Python 程序员都知道可以用 d.get(k, default) 来代替 d[k],给找不到的键一个默认的
返回值(这比处理 KeyError 要方便不少)。但是要更新某个键对应的值的时候,不管使用 __getitem__ 还是 get 都会不自然,而且效率低。dict.get 并不是处理找不到的键的最好方法。

"""创建一个从单词到其出现情况的映射"""
import sys
import re
WORD_RE = re.compile(r\w+)
index = {}
with open(sys.argv[1], encoding=utf-8) as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start()+1
            location = (line_no, column_no)
            # 这其实是一种很不好的实现,这样写只是为了证明论点
            occurrences = index.get(word, []) ?
            occurrences.append(location) ?
            index[word] = occurrences ?
           # 以字母顺序打印出结果
for word in sorted(index, key=str.upper): ?
print(word, index[word])

? 提取 word 出现的情况,如果还没有它的记录,返回 []。
? 把单词新出现的位置添加到列表的后面。
? 把新的列表放回字典中,这又牵扯到一次查询操作。
? sorted 函数的 key= 参数没有调用 str.uppper,而是把这个方法的引用传递给 sorted 函数,这样在排序的时候,单词会被规范成统一格式。

通过 dict.setdefault 可以只用一行解决。

"""创建从一个单词到其出现情况的映射"""
import sys
import re
WORD_RE = re.compile(r\w+)
index = {}
with open(sys.argv[1], encoding=utf-8) as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start()+1
            location = (line_no, column_no)
            index.setdefault(word, []).append(location) ?
            # 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
print(word, index[word])

? 获取单词的出现情况列表,如果单词不存在,把单词和一个空列表
放进映射,然后返回这个空列表,这样就能在不进行第二次查找的情况
下更新列表了

也就是说,这样写:

my_dict.setdefault(key, []).append(new_value)

跟这样写:

if key not in my_dict:
my_dict[key] = []
my_dict[key].append(new_value)

二者的效果是一样的,只不过后者至少要进行两次键查询——如果键不存在的话,就是三次,用 setdefault 只需要一次就可以完成整个操作。


在用户创建 defaultdict 对象的时候,就需要给它配置一个为找不到的键创造默认值的方法。
具体而言,在实例化一个 defaultdict 的时候,需要给构造方法提供一个可调用对象,这个可调用对象会在 __getitem__ 碰到找不到的键的时候被调用,让 __getitem__ 返回某种默认值。
比如,我们新建了这样一个字典:dd = defaultdict(list),如果键‘new-key‘ 在 dd 中还不存在的话,表达式 dd[‘new-key‘] 会按照以下的步骤来行事。
(1) 调用 list() 来建立一个新列表。
(2) 把这个新列表作为值,‘new-key‘ 作为它的键,放到 dd 中。
(3) 返回这个列表的引用。
而这个用来生成默认值的可调用对象存放在名为 default_factory 的
实例属性里。

利用 defaultdict 实例而不是setdefault 方法

"""创建一个从单词到其出现情况的映射"""
import sys
import re
import collections
WORD_RE = re.compile(r\w+)
index = collections.defaultdict(list) ?
with open(sys.argv[1], encoding=utf-8) as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start()+1
            location = (line_no, column_no)
            index[word].append(location) ?
            # 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
print(word, index[word])

? 把 list 构造方法作为 default_factory 来创建一个
defaultdict。
? 如果 index 并没有 word 的记录,那么 default_factory 会被调用,为查询不到的键创造一个值。这个值在这里是一个空的列表,然后这个空列表被赋值给 index[word],继而被当作返回值返回,因此
.append(location) 操作总能成功。

如果在创建 defaultdict 的时候没有指定 default_factory,查询不存在的键会触发 KeyError。

defaultdict 里的 default_factory 只会在__getitem__ 里被调用,在其他的方法里完全不会发挥作用。比如,dd 是个 defaultdict,k 是个找不到的键, dd[k] 这个表达式会调用 default_factory 创造某个默认值,而 dd.get(k) 则会返回 None。

所有这一切背后的功臣其实是特殊方法 __missing__。它会在defaultdict 遇到找不到的键的时候调用 default_factory,而实际上这个特性是所有映射类型都可以选择去支持的。

特殊方法__missing__

所有的映射类型在处理找不到的键的时候,都会牵扯到 __missing__方法。这也是这个方法称作“missing”的原因。虽然基类 dict 并没有定义这个方法,但是 dict 是知道有这么个东西存在的。也就是说,如果
有一个类继承了 dict,然后这个继承类提供了 __missing__ 方法,那么在 __getitem__ 碰到找不到的键的时候,Python 就会自动调用它,而不是抛出一个 KeyError 异常。

_missing__ 方法只会被 __getitem__ 调用(比如在表达式 d[k] 中)。提供 __missing__ 方法对 get 或者__contains__(in 运算符会用到这个方法)这些方法的使用没有影响。这也是我在上一节最后的警告中提到,defaultdict 中的default_factory 只对 __getitem__ 有作用的原因。

Tests for item retrieval using `d[key]` notation::
>>> d = StrKeyDict0([(2, two), (4, four)])
>>> d[2]
two
>>> d[4]
four
>>> d[1]
Traceback (most recent call last):
...
KeyError: 1
Tests for item retrieval using `d.get(key)` notation::
>>> d.get(2)
two
>>> d.get(4)
four
>>> d.get(1, N/A)
N/A
Tests for the `in` operator::
>>> 2 in d
True
>>> 1 in d
False

 

StrKeyDict0 在查询的时候把非字符串的键转换为字符串

class StrKeyDict0(dict): ?
    def __missing__(self, key):
        if isinstance(key, str): ?
            raise KeyError(key)
        return self[str(key)] ?
    def get(self, key, default=None):
        try:
            return self[key] ?
        except KeyError:
            return default ?
    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys() ?

? StrKeyDict0 继承了 dict。
? 如果找不到的键本身就是字符串,那就抛出 KeyError 异常。
? 如果找不到的键不是字符串,那么把它转换成字符串再进行查找。
? get 方法把查找工作用 self[key] 的形式委托给 __getitem__,这样在宣布查找失败之前,还能通过 __missing__ 再给某个键一个机会。
? 如果抛出 KeyError,那么说明 __missing__ 也失败了,于是返回default。
? 先按照传入键的原本的值来查找(我们的映射类型中可能含有非字符串的键),如果没找到,再用 str() 方法把键转换成字符串再查找一次。

如果没有这个测试,只要 str(k) 返回的是一个存在的键,那么__missing__ 方法是没问题的,不管是字符串键还是非字符串键,它都能正常运行。但是如果 str(k) 不是一个存在的键,代码就会陷入无
限递归。这是因为 __missing__ 的最后一行中的 self[str(key)] 会调用 __getitem__,而这个 str(key) 又不存在,于是 __missing__又会被调用。

为了保持一致性,__contains__ 方法在这里也是必需的。这是因为 kin d 这个操作会调用它,但是我们从 dict 继承到的 __contains__方法不会在找不到键的时候调用 __missing__ 方法。__contains__
里还有个细节,就是我们这里没有用更具 Python 风格的方式——k in my_dict——来检查键是否存在,因为那也会导致 __contains__ 被递归调用。为了避免这一情况,这里采取了更显式的方法,直接在这个
self.keys() 里查询。

像 k in my_dict.keys() 这种操作在 Python 3 中是很快的,而且即便映射类型对象很庞大也没关系。这是因为dict.keys() 的返回值是一个“视图”。视图就像一个集合,而且跟字典类似的是,在视图里查找一个元素的速度很快。

不可变映射类型

标准库里所有的映射类型都是可变的,但有时候你会有这样的需求,比如不能让用户错误地修改某个映射。

从 Python 3.3 开始,types 模块中引入了一个封装类名叫MappingProxyType。如果给这个类一个映射,它会返回一个只读的映射视图。虽然是个只读视图,但是它是动态的。这意味着如果对原映射
做出了改动,我们通过这个视图可以观察到,但是无法通过这个视图对原映射做出修改。

用 MappingProxyType 来获取字典的只读实例mappingproxy

>>> from types import MappingProxyType
>>> d = {1:A}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({1: A})
>>> d_proxy[1] ?
A
>>> d_proxy[2] = x ?
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: mappingproxy object does not support item assignment
>>> d[2] = B
>>> d_proxy ?
mappingproxy({1: A, 2: B})
>>> d_proxy[2]
B
>>>

? d 中的内容可以通过 d_proxy 看到。
? 但是通过 d_proxy 并不能做任何修改。
? d_proxy 是动态的,也就是说对 d 所做的任何改动都会反馈到它上面。

集合论

“集”这个概念在 Python 中算是比较年轻的,同时它的使用率也比较低。set 和它的不可变的姊妹类型 frozenset 直到 Python 2.3 才首次以模块的形式出现,然后在 Python 2.6 中它们升级成为内置类型。

集合的本质是许多唯一对象的聚集。因此,集合可以用于去重:

>>> l = [spam, spam, eggs, spam]
>>> set(l)
{eggs, spam}
>>> list(set(l))
[eggs, spam]

集合中的元素必须是可散列的,set 类型本身是不可散列的,但是frozenset 可以。因此可以创建一个包含不同 frozenset 的 set。除了保证唯一性,集合还实现了很多基础的中缀运算符。给定两个集合
a 和 b,a | b 返回的是它们的合集,a & b 得到的是交集,而 a - b得到的是差集。合理地利用这些操作,不仅能够让代码的行数变少,还能减少 Python 程序的运行时间。这样做同时也是为了让代码更易读,从
而更容易判断程序的正确性,因为利用这些运算符可以省去不必要的循环和逻辑操作。

例如,我们有一个电子邮件地址的集合(haystack),还要维护一个
较小的电子邮件地址集合(needles),然后求出 needles 中有多少地
址同时也出现在了 heystack 里。借助集合操作,我们只需要一行代码
就可以了

needles 的元素在 haystack 里出现的次数,两个变量都是 set 类型

found = len(needles & haystack)

如果不使用交集操作的话,代码可能就变成了

found = 0
for n in needles:
if n in haystack:
found += 1

使用集合的内置方法会比用循环速度快

不要忘了,如果要创建一个空集,你必须用不带任何参数的构造方法 set()。如果只是写成 {} 的形式,跟以前一样,你创建的其实是个空字典。

>>> s = {1}
>>> type(s)
<class set>
>>> s
{1}
>>> s.pop()
1
>>> s
set()

 

集合的操作

列出了可变和不可变集合所拥有的方法的概况,其中不少是运算符重载的特殊方法。包含了数学里集合的各种操作在 Python 中所对应的运算符和方法。
技术分享图片

集合的数学运算

技术分享图片

dict和set的背后

想要理解 Python 里字典和集合类型的长处和弱点,它们背后的散列表是绕不开的一环。

  • Python 里的 dict 和 set 的效率有多高?
  • 为什么它们是无序的?
  • 为什么并不是所有的 Python 对象都可以当作 dict 的键或 set 里的元素?
  • 为什么 dict 的键和 set 元素的顺序是跟据它们被添加的次序而定的,以及为什么在映射对象的生命周期中,这个顺序并不是一成不变的
  • 为什么不应该在迭代循环 dict 或是 set 的同时往里添加元素?

 一个关于效率的实验

为了对比容器的大小对 dict、set 或 list 的 in 运算符效率的影响,我创建了一个有 1000 万个双精度浮点数的数组,名叫 haystack。另外还有一个包含了 1000 个浮点数的 needles 数组,其中 500 个数字是从
haystack 里挑出来的,另外 500 个肯定不在 haystack 里。作为 dict 测试的基准,我用 dict.fromkeys() 来建立了一个含有1000 个浮点数的名叫 haystack 的字典,并用 timeit 模块测试示例 3-14(与示例 3-11 相同)里这段代码运行所需要的时间。

在 haystack 里查找 needles 的元素,并计算找到的元素的个数

found = 0
for n in needles:
    if n in haystack:
        found += 1

技术分享图片

也就是说,在从 1000 个字典键里搜索 1000 个浮点数所需的时间是 0.000202 秒,把同样的搜索在含有 10 000 000 个元素的字典里进行一遍,只需要 0.000337 秒。换句话说,在一个有 1000 万个键的
字典里查找 1000 个数,花在每个数上的时间不过是 0.337 微秒——没错,相当于平均每个数差不多三分之一微秒。作为对比,我把 haystack 换成了 set 和 list 类型,重复了同样的增长大小的实验。对于 set,除了上面的那个循环的运行时间,我还测量了示例 3-15 那行代码,这段代码也计算了 needles 中出现在
haystack 中的元素的个数。

利用交集来计算 needles 中出现在 haystack 中的元素的个数

found = len(needles & haystack)

 列出了所有测试的结果。

 技术分享图片

字典中的散列表

散列表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。在一般的数据结构教材中,散列表里的单元通常叫作表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用。因为所有表元的大小一致,所以可以通过偏移量来读取某个表元。

因为 Python 会设法保证大概还有三分之一的表元是空的,所以在快要达
到这个阈值的时候,原有的散列表会被复制到一个更大的空间里面。
如果要把一个对象放入散列表,那么首先要计算这个元素键的散列值。Python 中可以用 hash() 方法来做这件事情,接下来会介绍这一点。


散列值和相等性

内置的 hash() 方法可以用于所有的内置类型对象。如果是自定义对象调用 hash() 的话,实际上运行的是自定义的 __hash__。如果两个对象在比较的时候是相等的,那它们的散列值必须相等,否
则散列表就不能正常运行了。例如,如果 1 == 1.0 为真,那么hash(1) == hash(1.0) 也必须为真,但其实这两个数字(整型和浮点)的内部结构是完全不一样的.

 

为了让散列值能够胜任散列表索引这一角色,它们必须在索引空间中尽量分散开来。这意味着在最理想的状况下,越是相似但不相等的对象,它们散列值的差别应该越大。示例 3-16 是一段代码输
出,这段代码被用来比较散列值的二进制表达的不同。注意其中 1和 1.0 的散列值是相同的,而 1.0001、1.0002 和 1.0003 的散列值则非常不同。

从 Python 3.3 开始,str、bytes 和 datetime 对象的散列值计算过程中多了随机的“加盐”这一步。所加盐值是 Python进程内的一个常量,但是每次启动 Python 解释器都会生成一个不同的盐值。随机盐值的加入是为了防止 DOS 攻击而采取的一种安全措施。

散列表算法

为了获取 my_dict[search_key] 背后的值,Python 首先会调用
hash(search_key) 来计算 search_key 的散列值,把这个值最低
的几位数字当作偏移量,在散列表里查找表元(具体取几位,得看
当前散列表的大小)。若找到的表元是空的,则抛出 KeyError 异
常。若不是空的,则表元里会有一对 found_key:found_value。
这时候 Python 会检验 search_key == found_key 是否为真,如
果它们相等的话,就会返回 found_value。


如果 search_key 和 found_key 不匹配的话,这种情况称为散列
冲突。发生这种情况是因为,散列表所做的其实是把随机的元素映
射到只有几位的数字上,而散列表本身的索引又只依赖于这个数字
的一部分。为了解决散列冲突,算法会在散列值中另外再取几位,
然后用特殊的方法处理一下,把新得到的数字再当作索引来寻找表
元。 若这次找到的表元是空的,则同样抛出 KeyError;若非
空,或者键匹配,则返回这个值;或者又发现了散列冲突,则重复
以上的步骤。下图展示了这个算法的示意图。

技术分享图片

添加新元素和更新现有键值的操作几乎跟上面一样。只不过对于前
者,在发现空表元的时候会放入一个新元素;对于后者,在找到相
对应的表元后,原表里的值对象会被替换成新值。


另外在插入新值时,Python 可能会按照散列表的拥挤程度来决定是
否要重新分配内存为它扩容。如果增加了散列表的大小,那散列值
所占的位数和用作索引的位数都会随之增加,这样做的目的是为了
减少发生散列冲突的概率。


表面上看,这个算法似乎很费事,而实际上就算 dict 里有数百万
个元素,多数的搜索过程中并不会有冲突发生,平均下来每次搜索
可能会有一到两次冲突。在正常情况下,就算是最不走运的键所遇
到的冲突的次数用一只手也能数过来。


了解 dict 的工作原理能让我们知道它的所长和所短,以及从它衍
生而来的数据类型的优缺点。下面就来看看 dict 这些特点背后的
原因。

dict的实现及其导致的结果

使用散列表给 dict 带来的优势和限制都有哪些。

键必须是可散列的

(1) 支持 hash() 函数,并且通过 __hash__() 方法所得到的散列值是不变的。
(2) 支持通过 __eq__() 方法来检测相等性。
(3) 若 a == b 为真,则 hash(a) == hash(b) 也为真。所有由用户自定义的对象默认都是可散列的,因为它们的散列值由id() 来获取,而且它们都是不相等的。

字典在内存上的开销巨大

由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空
间上的效率低下。举例而言,如果你需要存放数量巨大的记录,那
么放在由元组或是具名元组构成的列表中会是比较好的选择;最好
不要根据 JSON 的风格,用由字典组成的列表来存放这些记录。用
元组取代字典就能节省空间的原因有两个:其一是避免了散列表所
耗费的空间,其二是无需把记录中字段的名字在每个元素里都存一
遍。


在用户自定义的类型中,__slots__ 属性可以改变实例属性的存储
方式,由 dict 变成 tuple。
记住我们现在讨论的是空间优化。如果你手头有几百万个对象,而
你的机器有几个 GB 的内存,那么空间的优化工作可以等到真正需
要的时候再开始计划,因为优化往往是可维护性的对立面。

 

键查询很快

dict 的实现是典型的空间换时间:字典类型有着巨大的内存开
销,但它们提供了无视数据量大小的快速访问——只要字典能被装
在内存里。正如表 3-5 所示,如果把字典的大小从 1000 个元素增
加到 10 000 000 个,查询时间也不过是原来的 2.8 倍,从 0.000163
秒增加到了 0.00456 秒。这意味着在一个有 1000 万个元素的字典
里,每秒能进行 200 万个键查询。

 

键的次序取决于添加顺序

当往 dict 里添加新键而又发生散列冲突的时候,新键可能会被安
排存放到另一个位置。于是下面这种情况就会发生:由
dict([key1, value1), (key2, value2)] 和 dict([key2,
value2], [key1, value1]) 得到的两个字典,在进行比较的时
候,它们是相等的;但是如果在 key1 和 key2 被添加到字典里的
过程中有冲突发生的话,这两个键出现在字典里的顺序是不一样
的。

# 世界人口数量前10位国家的电话区号
DIAL_CODES = [
    (86, China),
    (91, India),
    (1, United States),
    (62, Indonesia),
    (55, Brazil),
    (92, Pakistan),
    (880, Bangladesh),
    (234, Nigeria),
    (7, Russia),
    (81, Japan),
]
d1 = dict(DIAL_CODES) ?
print(d1:, d1.keys())
d2 = dict(sorted(DIAL_CODES)) ?
print(d2:, d2.keys())
d3 = dict(sorted(DIAL_CODES, key=lambda x:x[1])) ?
print(d3:, d3.keys())
assert d1 == d2 and d2 == d3 ?

? 创建 d1 的时候,数据元组的顺序是按照国家的人口排名来决定的。
? 创建 d2 的时候,数据元组的顺序是按照国家的电话区号来决定的。
? 创建 d3 的时候,数据元组的顺序是按照国家名字的英文拼写来决定的。
? 这些字典是相等的,因为它们所包含的数据是一样的。

往字典里添加新键可能会改变已有键的顺序

无论何时往字典里添加新的键,Python 解释器都可能做出为字典扩
容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字
典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲
突,导致新散列表中键的次序变化。要注意的是,上面提到的这些
变化是否会发生以及如何发生,都依赖于字典背后的具体实现,因
此你不能很自信地说自己知道背后发生了什么。如果你在迭代一个
字典的所有键的过程中同时对字典进行修改,那么这个循环很有可
能会跳过一些键——甚至是跳过那些字典中已经有的键。


由此可知,不要对字典同时进行迭代和修改。如果想扫描并修改一
个字典,最好分成两步来进行:首先对字典迭代,以得出需要添加
的内容,把这些内容放在一个新字典里;迭代结束之后再对原有字
典进行更新。

 

set的实现以及导致的结果

set 和 frozenset 的实现也依赖散列表,但在它们的散列表里存放的
只有元素的引用(就像在字典里只存放键而没有相应的值)。在 set 加
入到 Python 之前,我们都是把字典加上无意义的值当作集合来用的。
在 节中所提到的字典和散列表的几个特点,对集合来说几乎都是
适用的。为了避免太多重复的内容,这些特点总结如下。

  • 集合里的元素必须是可散列的。
  • 集合很消耗内存。
  • 可以很高效地判断元素是否存在于某个集合。
  • 元素的次序取决于被添加到集合里的次序。
  • 往集合里添加元素,可能会改变集合里已有元素的次序。

流畅的python 第三张 字典和集合

标签:形式   mce   contain   接口   行为   字符   同时   值对象   用户创建   

原文:https://www.cnblogs.com/chenxuming/p/9704179.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号