Python 字典的原理及高级用法

May 12, 2018
1949
#Python#字典

本文最近一次更新于 5 年 10 个月前,其中的内容很可能已经有所发展或是发生改变。

https://ae01.alicdn.com/kf/HTB1b.u_ajvuK1Rjy0Fa7602aVXaM.png

算算时间有段时间没写技术类的文章了,部分原因是最近过得确实比较忙。当然,也并没有忙到完全抽不出时间写博客,根本原因还是没有找到啥好的写作素材,随随便便糊弄一篇我又有点不好意思发上来,于是乎,就一直搁置到现在。

对于字典这一基础的数据结构来说,其对 Python 的程序重要性是无可替代的,在《代码之美》一书中,作者是这么描述的:

字典这个数据结构活跃在所有 Python 程序的背后,即便你的源码里并没有直接用到它。——A.M.Kuchling

在 Python 程序里,无论是模块、函数、还是对象,均有自己的「命名空间」,而这命名空间即为一个字典(dict),key 就是变量名,value 就是变量值,除去「命名空间外」,对象的函数(方法)关键字也是存放在字典中,此时的 key 就是函数(方法)名,value 就是该函数(方法)的引用。可以采用 __builtins__.__dict__ 来查看这些函数(方法)。

字典的原理

Python 的字典是依据散列表(也叫哈希表)来实现的,首先简单介绍一下散列表的原理。

散列表中的每一个单元称为表元。在 dict 的实现里,每个 key-value 均占用一个表元,其中 key 为键的引用(这里是键的引用,而不是键本身,因为 key 可以为任意可散列对象),value 为值的引用。因为是引用:表元大小均一致,所以可通过偏移量来读取某个表元。

在 Python 中,散列函数由 hash() 方法出任,当我们查询 my_dict[search_key] 时,Python 会调用 hash(search_key) 来计算 search_key 的散列值,并将这个值的低几位数字当作偏移量,在散列表中查找表元,具体是几位,需要根据散列表的大小来决定。若表元为空,则说明 search_key 不存在,抛出 KeyError 异常。若非空,则表元会有一对 found_key:found_value,这时若 search_key == found_key 为真,那么就返回 found_value。

如果 search_key 和 found_key 不相等,这种情况成为散列冲突,发生这种情况是因为散列表只把该元素映射到了只有几位数字上。为了解决散列冲突,算法会在散列值中另外取几位,用新得到的数字做偏移量再次寻找。

创建字典

创建一个字典有许多方式:

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

在刚刚的原理中说到,由于字典的索引是根据 hash() 函数来获得的,所以 dict 其实是无序的,这也解释了为什么上面代码中的等式会成立。

字典推导

没错,在 Python3+ 里,推导式不再是列表的特性了。

numbers = range(5)
numbers_square = {number: number ** 2 for number in numbers}

键查询

最简单的方法是采用下标方式来查询。即:my_dict[key],这也是推荐的方法,但这是 key 存在的情况,而现实中,一定会遇到 key 不存在的时候,这时就会 raise 一个 KeyError。以下有几种解决办法:

用 get 来获取

my_id = {'name': 'wincer'}
>>> my_id.get('name')
'wincer'
>>> my_id.get('age', 'default')
'default'

若 key 存在,则返回对应的 value,若 key 不存在,且传入第二个参数,那么返回该参数,若无第二个参数,则返回 None。

用 defaultdict 预先设置缺省(推荐)

from collections import defaultdict

my_id = defaultdict(list)
my_id.update({'name': 'wincer'})
>>> mydict['name']
'wincer'
>>> mydict['age']
[]

defaultdict 需要指定一个 factory,当查询 key 不存在时,会创建一个空的 factory 返回。推荐使用这种方式来处理 key 不存在的情况,因为该方法不仅可用于读取 value 值,还可随时用 append 来更新 value。同时需注意:defaultdict 中的参数只会在 __getitem__ 中被调用。如 dd 是一个 defaultdict,k 是一个不存在的键,dd[k] 用 factory 来创造一个默认值,但 dd.get(k) 却仍会返回 None。

使用 __missing__ 方法

当我们调用 my_dict[key] 时,如果 key 是一个字符串,我们会需要用 my_dict[’name’] 来获取,如果你觉得比较麻烦,想直接用 my_dict[name] 的话,可以采用如下方法:

from collections import UserDict


class StrKeyDict(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

d = StrKetDict([('1', 'one'), ('2', 'two')])
>>> d[2]
'two'

使用 __getattr__ 方法(不推荐)

有时我们可能更懒,想要用类属性类似的 my_dict.name 方法来获取 value,这时,可以使用 __getattr__ 方法:

from collections import UserDict


class AttrDict(UserDict):
    def __getattr__(self, attr):
        return self[attr]
    
d = AttrDict([('name', 'wincer'), ('age', '20')])

>>> d.name
'wincer'

并不推荐这样做,因为在 dict 实现中,并没有要求 key 一定为合法标识符,只需要是可散列对象即可,而上面的写法一旦 key 不为合法标识符,会 raise 一个 SyntaxError:

d.update({(0): 'zero'})
>>> d[(0)]
'zero'
>>> d.0
SyntaxError: invalid syntax

如果非常想使用 . 来获取 value 的话,建议使用 namedtuple

当然这也就意味着必须使用合法标识符了:

from collections import namedtuple
ID = namedtuple('ID', 'name age')
me = ID('wincer', 20)
>>> me.name
'wincer'

ID = namedtuple('ID', '(1, 0) age')
ValueError: Type names and field names must be valid identifiers: '(1'

实现 switch … case 结构

同样借助键查询,可以实现 Python 中没有的 switch … case 结构:

def foo(x):
    data = {
        0: 'zero',
        1: 'one',
        2: 'two',
    }
    return data.get(x, None)

所以说 Python 不设计 switch … case 语句是有原因的,看上面的实现,比 switch … case 不知道高到哪里去了。

dict 和它的小伙伴们

OrderedDict

在添加键的时候会按顺序添加,同时 .popitem 是会删除并返回字典的最后一个元素而不是像 dict 里面一样可能会删除任意元素。

Counter

这个映射会给键一个计数器,每次更新键时都会增加这个计时器,所以这个类型可以用以给可迭代类型计数:

from collections import Counter

ct = Counter('hfkjahfkakhf')
>>> ct

Counter({'a': 2, 'f': 3, 'h': 3, 'j': 1, 'k': 3})
ct.update('fdjlahkla')
>>> ct
Counter({'a': 4, 'd': 1, 'f': 4, 'h': 4, 'j': 2, 'k': 4, 'l': 2})

>>> ct.most_common(2)
[('h', 4), ('f', 4)]

UserDict

用法见键查询。

不可变映射

在 Python 3.3 后的版本,types 模块引入一个名为 MappingProxyType 的类。如果给这个类一个映射,它会返回一个只读的映射视图。但它是动态的,如果原映射改动,那么它也会相应改动。

>>> int.__dict__
mappingproxy({'__abs__': <slot wrapper="" '__abs__'="" of="" 'int'="" objects="">,
              '__add__': <slot wrapper="" '__add__'="" of="" 'int'="" objects="">,
              ...})

from types import MappingProxyType
d = {1: 'A'}
d_proxy = MappingProxyType(d)

>>> d_proxy[2] = 'x'
TypeError: 'mappingproxy' object does not support item assignment

d[2] = 'B'
>>> d_proxy[2]
'B'</slot></slot>

Python 字典的原理及高级用法

https://blog.itswincer.com/posts/4f2b4bfb/

作者

Wincer

更新于

May 12, 2018

许可协议

CC BY-NC-ND 4.0
  1. Sep 29, 2020

    Python 并发之痛:线程,协程?
  2. Oct 21, 2018

    Python 知多少(二)——继承
  3. Aug 8, 2018

    Python 知多少(一)——不常见的数据结构
  4. Jul 19, 2017

    Python 实现多线程下载器
  5. Jul 1, 2017

    导出 QQ 聊天记录
  6. Apr 5, 2023

    OpenCore 引导安装 macOS Ventura 教程