python 字典、集合

时间  2020-08-09 标签 python 字典 集合

可变对象与不可变对象

Python的每一个对象都分为可变和不可变，主要的核心类型中，数字、字符串、元组是不可变的，列表、字典是可变的。程序员

最简单的判断方法就是看这个变量值更新后，内存地址有没有变化。由于可变对象数据都是就地更新，而不可变对象数据修改都是开辟新内存存新数据。web

好比：整数是不可变对象，因此值更新了会新开辟一块内存存新值；而集合是可变对象，会就地更新原内存地址指向的值。算法

a = {1, 2, 3}
print(id(a)) # 139654362815624
a.add(4)
print(id(a)) # 139654362815624


a = 2
print(id(a)) # 10919360
a += 1
print(id(a)) # 10919392

可散列的数据类型

只有可散列的数据类型才能做为字典里的键。数组

什么是可散列的数据类型？若是一个对象是可散列的，那么在这个对象的生命周期中，它的散列值是不变的，并且这个对象须要实现__hash__() 方法。另外可散列对象还要有__eq__()方法，这样才能跟其余键作比较。若是两个可散列对象是相等的，那么它们的散列值必定是同样的。数据结构

通俗点：哈希集合就是不少个桶，但每一个桶里面只能放一个球。__hash__函数的做用就是找到桶的位置，究竟是几号桶。__eq__函数的做用就是当桶里面已经有一个球了，但又来了一个球，它声称它也应该装进这个桶里面（__hash__函数给它说了桶的位置），双方僵持不下，那就得用__eq__函数来判断这两个球是否是相等的（equal），若是是判断是相等的，那么后来那个球就不该该放进桶里，哈希集合维持现状。app

原子不可变数据类型（str、 bytes和数值类型）都是可散列类型，frozenset也是可散列的，由于frozenset里只能容纳可散列类型。元组的话，只有当一个元组包含的全部元素都是可散列类型的状况下，它才是可散列的。svg

通常来说用户自定义的类型的对象都是可散列的，散列值就是它们的id()函数的返回值，因此全部这些对象在比较的时候都是不相等的。函数

字典推导

列表推导和生成器表达式的概念就移植到了字典上，从而有了字典推导。测试

DIAL_CODES = [
    (86, 'China'),
    (91, 'India'),
    (1, 'United States'),
    (62, 'Indonesia'),
    (55, 'Brazil'),
    (92, 'Pakistan'),
    (880, 'Bangladesh'),
    (234, 'Nigeria'),
    (7, 'Russia'),
    (81, 'Japan'),
]
country_code = {country: code for code, country in DIAL_CODES}

用 setdefault 处理找不到的键

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 这个类型而不是普通的 dict，另外一个是给本身定义一个 dict 的子类，而后在子类中实现__missing__方法。

my_dict = collections.defaultdict(list)
  1. my_dict[‘zzxx’].append(‘1’)，若是zzxx这个键在my_dict不存在的时候
  2. 它会调用 list() 来创建一个新列表
  3. 把这个新列表([])做为值， ‘zzxx’ 做为它的键，放到 my_dict 中
  4. 若是在建立 defaultdict 的时候没有指定 default_factory（这里是list），查询不存在的键会触发KeyError

特殊方法__missing__

全部的映射类型在处理找不到的键的时候，都会牵扯到__missing__方法。

若是有一个类继承了 dict，这个继承类就有__missing__方法，在__getitem__碰到找不到的键的时候， Python 就会自动调用它，而不是抛出一个 KeyError 异常。

魔术方法__missing__只会在__getitem__里被调用（即a[‘dd’]）这种类型的访问。若是是a.get(‘dd’)这种直接调用get()方法的访问是不会调用到__missing__的。

例如：若是我须要把非字符串的键转成字符串的键取值

class StrKeyGet(dict):
    def __missing__(self, key):
        # 若是找不到的键自己就是字符串，那就抛出 KeyError 异常。
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]
    
    # get 方法把查找工做用 self[key] 的形式委托给 __getitem__，
    # 这样在宣布查找失败以前，还能经过 __missing__ 再给某个键一个机会
    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()

字典的变种

collections.OrderedDict

这个类型在添加键的时候会保持顺序，所以键的迭代次序老是一致的。

collections.ChainMap

该类型能够容纳数个不一样的映射对象，而后在进行键查找操做的时候，这些对象会被看成一个总体被逐个查找，直到键被找到为止。

Python 变量查询规则的代码片断：

import builtins
from collections import ChainMap

pylookup = ChainMap(locals(), globals(), vars(builtins))
print(pylookup)

多个字典数据查询：

from collections import ChainMap
d1 = dict(a=1, b=2, c=3)
d2 = dict(a=22, b=2244, d=555)
d3 = dict(f=6666)

lookup = ChainMap(d1, d2, d3)
print(lookup['a'])
print(lookup['f'])

colllections.Counter

这个映射类型会给键准备一个整数计数器。每次更新一个键的时候都会增长这个计数器，Counter 实现了 + 和 - 运算符用来合并记录。

a = Counter({'a': 1, 'b':2})
print(a) # Counter({'b': 2, 'a': 1})

a.update({'a': 222})
print(a) # Counter({'a': 223, 'b': 2})

a.update({'b': 10})
print(a) # Counter({'a': 223, 'b': 12})

子类化UserDict

就创造自定义映射类型来讲，以 UserDict 为基类，总比以普通的 dict 为基类要来得方便。

UserDict 并非 dict 的子类，可是 UserDict 有一个叫做 data 的属性，是 dict 的实例，这个属性其实是 UserDict 最终存储数据的地方。

import collections
class StrKeyGet(collections.UserDict):
    def __missing__(self, key):
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):
        return str(key) in self.data

    def __setitem__(self, key, item):
        self.data[str(key)] = item

不可变映射类型

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

从 Python 3.3 开始， types 模块中引入了一个封装类名叫MappingProxyType。若是给这个类一个映射，它会返回一个只读的映射视图。虽然是个只读视图，可是它是动态的。这意味着若是对原映射作出了改动，咱们经过这个视图能够观察到。

from types import MappingProxyType
a = {'a': 123, 'b': 456}
a_proxy = MappingProxyType(a)
print(a_proxy['a']) # 123

a['c'] = 5
print(a_proxy) # {'a': 123, 'c': 5, 'b': 456}

集合论

“集”或者“集合”既指 set，也指 frozenset。集合的本质是许多惟一对象的汇集。所以，集合能够用于去重。集合中的元素必须是可散列的，set类型自己是不可散列的，可是 frozenset 能够。所以能够建立一个包含不一样 frozenset 的 set。

l = ['spam', 'spam', 'eggs', 'spam']
set(l)

除了保证惟一性，集合还实现了不少基础的中缀运算符。给定两个集合 a 和 b， a | b 返回的是它们的合集， a & b 获得的是交集，而 a - b 获得的是差集。

集合字面量

空集合set()，字面量集合{1}、 {1, 2}。像 {1, 2, 3} 这种字面量句法相比于构造方法set([1, 2, 3])要更快且更易读。

不要忘了，若是要建立一个空集，你必须用不带任何参数的构造方法 set()。若是只是写成 {} 的形式，跟之前同样，你建立的实际上是个空字典。

像 {1, 2, 3} 这种字面量句法相比于构造方法（set([1, 2, 3])）要更快且更易读，由于Python 会利用一个专门的叫做 BUILD_SET 的字节码来建立集合。

集合推导

from unicodedata import name
a = {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i),'')}
print(a)

dict和set的背后

一个关于效率的实验

全部的 Python 程序员都从经验中得出结论，认为字典和集合的速度是很是快的。

为了对比容器的大小对 dict、 set 或 list 的 in 运算符效率的影响，我建立了一个有1000 万个双精度浮点数的数组，名叫 haystack。另外还有一个包含了 1000 个浮点数的needles 数组，其中 500 个数字是从 haystack 里挑出来的，另外 500 个确定不在haystack 里。

测试结果代表：最快的时间来自“集合交集花费时间”这一列，这一列的结果是利用集合&操做的代码的效果。不出所料的是，最糟糕的表现来自“列表花费时间”这一列。因为列表的背后没有散列表来支持 in 运算符，每次搜索都须要扫描一次完整的列表，致使所需的时间跟据 haystack 的大小呈线性增加。

字典中的散列表

散列表实际上是一个稀疏数组（老是有空白元素的数组称为稀疏数组），在通常的数据结构教材中，散列表里的单元一般叫做表元（bucket）。

在dict的散列表当中，每一个键值对都占用一个表元，每一个表元都有两个部分，一个是对键的引用，另外一个是对值的引用。由于全部表元的大小一致，因此能够经过偏移量来读取某个表元。

Python 会设法保证大概还有三分之一的表元是空的，因此在快要达到这个阈值的时候，原有的散列表会被复制到一个更大的空间里面。

若是要把一个对象放入散列表，那么首先要计算这个元素键的散列值。Python中能够用hash()方法来作这件事情。内置的hash()方法能够用于全部的内置类型对象。若是是自定义对象调用 hash()的话，实际上运行的是自定义的__hash__，若是两个对象在比较的时候是相等的那么 hash(a) == hash(b) 也相等。例如，若是 1 == 1.0 为真，那么 hash(1) == hash(1.0) 也必须为真。

为了让散列值可以胜任散列表索引这一角色，它们必须在索引空间中尽可能分散开来。这意味着在最理想的情况下，越是类似但不相等的对象，它们散列值的差异应该越大。

散列表算法

为了获取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 键必须是可散列的

一个可散列的对象必须知足如下要求

  1. 支持 hash() 函数，而且经过 hash() 方法所获得的散列值是不变的
  2. 支持经过__eq__()方法来检测相等性
  3. 若 a == b 为真，则 hash(a) == hash(b) 也为真

全部由用户自定义的对象默认都是可散列的，由于它们的散列值由 id() 来获取，并且它们都是不相等的。

若是你实现了一个类的__eq__方法，而且但愿它是可散列的，那么它必定要有个恰当的__hash__方法，保证在 a == b 为真的状况下 hash(a) ==hash(b) 也一定为真。

字典在内存上的开销巨大

因为字典使用了散列表，而散列表又必须是稀疏的，这致使它在空间上的效率低下。

若是你须要存放数量巨大的记录，那么放在由元组或是具名元组构成的列表中会是比较好的选择；最好不要用由字典组成的列表来存放这些记录。

在用户自定义的类型中，__slots__属性能够改变实例属性的存储方式，由 dict 变成 tuple。

记住咱们如今讨论的是空间优化。若是你手头有几百万个对象，而你的机器有几个GB的内存，那么空间的优化工做能够等到真正须要的时候再开始计划，由于优化每每是可维护性的对立面。

键查询很快

dict 的实现是典型的空间换时间，字典类型有着巨大的内存开销，但它们提供了无视数据量大小的快速访问——只要字典能被装在内存里。

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

不管什么时候往字典里添加新的键， Python 解释器均可能作出为字典扩容的决定。扩容致使的结果就是要新建一个更大的散列表，并把字典里已有的元素添加到新表里。

若是你在迭代一个字典的全部键的过程当中同时对字典进行修改，那么这个循环颇有可能会跳过一些键——甚至是跳过那些字典中已经有的键。由此可知，不要对字典同时进行迭代和修改。

set的实现以及致使的结果

set 和 frozenset 的实现也依赖散列表，但在它们的散列表里存放的只有元素的引用。

前面所提到的字典和散列表的几个特色，对集合来讲几乎都是适用的。

  1. 集合里的元素必须是可散列的。
  2. 集合很消耗内存。
  3. 能够很高效地判断元素是否存在于某个集合。
  4. 元素的次序取决于被添加到集合里的次序。
  5. 往集合里添加元素，可能会改变集合里已有元素的次序。
联系我们 沪ICP备2021010478号-7