dict & set

新建 dict：

新建 dict （无序）

字典推导：

字典推导

常见方法

• fromkeys(iter, [initial])

  
  fromkeys

• items()、keys()、values()

  
  items、keys、values

• iter(d)

  
  iter

• get(k, [default])、pop(k, [default])
• popitem() 随机返回一个键值对并删除它，对于 OrderedDict 先进先出，故先删最先插入的元素，其中有个可选参数 last 默认 False，设为 True 则是后进先出
• _getitem_(k) 是 d[k] 的背后。对于 defaultdict ，找不到对应键时调用 _missing_(k)，_missing_中又会调用 default_factory（可调用对象） 对未找到的键设置值
• _setitem_(k, v) 是 d[k] = v 的背后
• setdefault(k, [default]) 若 k 不存在，相当 setitem 返回 default，若 k 存在，则返回 k 对应的值
• update(m, [**kwarg]) m 可以是映射或键值对迭代器。鸭子类型，只有 m 有方法 keys，就可看作映射
• setdefault

my_dict.setdefault(key, []).append(new_value)  # 只有一次键查询

if key not in my_dict:   # 第一次查询
  my_dict[key] = []      # 可能又一次查询
my_dict[key].append(new_value)  # 又一次查询

dict 变种

• defaultdict
  新建 dd = defaultdict(list)，当 new_key不存在时，表达式 dd['new_key'] 执行如下：
  调用 list()，生成一个新列表，作为键 new_key 的值，返回这个列表的引用
  这里 list 为一个可调用对象，称为 default_factory

  
  defaullt_factory

• OrderedDict

  
  OrderedDict

• Counter

  
  Counter
• UserDict
  • 这个类用纯 Python 把标准 dict 又实现了一遍
  • 这个类有一个 data 属性，是 dict 实例，也是 UserDict 存放数据的地方

• MappingProxyType
  只读的映射视图，但是它是动态的，即对原映射修改，可以通过这个映射视图实时观察

  
  MappingProxyType

set

set 不可散列，frozenset 可散列。set 中元素要求可散列。
基于散列表，极快的查找速度，对 in 运算符优化
中缀运算符：|并、&交、-差

字典的散列表

散列表是一个稀疏数组（总有一些空白元素称为稀疏）
散列表单元称为表元（bucket），存放键和值的引用
Python 保证 1/3 表元是空的，快到这个阈值时散列表将会被复制到更大空间
要把一个对象放入散列表，首先要计算这个对象的散列值，即哈希值 hash()
CPython 一条实现细则：一个整型对象能被存入一个机器字中，那么它的散列值就是它本身
为让散列值能充当索引这角色，散列值之间应尽量分散开，即越是相似不等的对象，散列值相差越大
如果两个对象用 == 比较相等的，那么它们的散列值也应相等

散列表算法

散列表算法

dict 的实现及其特点

• 键必须可散列
  可散列对象要求：
  （1）支持 hash()，且 _hash_() 得到的值不变
  （2）支持 _eq_()
  （3）若 a == b为真，则 hash(a) == hash(b) 也为真
• dict 内存开销大
  散列表是稀疏的，导致内存开销巨大
• 键查询很快

• 键的次序取决于添加顺序
  包含的数据一样，字典相等

  
  键的次序取决于添加顺序
• 往字典中添加新键可能改变已有键顺序
  添加新键、字典扩容、散列冲突、键顺序改变
  一个小技巧
  不要迭代字典的同时又对字典进行修改，这样可能跳过一些键
  应该迭代的同时，得出要修改的内容添加到新字典中，迭代后才修改

set 的实现及其特点

set 与 frozenset 都依赖于散列表，特点与 dict 类似
（1）散列表里存放的是元素的引用，就像字典里存放的只有键，散列表才存放值的引用
（2）set 元素必须可散列
（3）in 运算符很高效
（4）很耗内存
（5）元素次序取决于添加次序
（6）往 set 中添加新元素可能改变原有元素次序

杂谈

dict 优化目标：更好的实现对随机键的读取
JSON：瘦身版XML，从 JavaScript 发展而来，而 JavaScript 从 Python 里偷师使用了：（字面量句法），故除了 true、false、null 这几个值拼写有出入之外，其余 JSON 与 Python 是完全兼容的。dict 和 list 使 JSON 成为交换数据格式的主流。