深入理解Python的dict和set

dict的abc继承关系

dict属于Python的mapping类型

from collections.abc import Mapping, MutableMapping
a = {}
print(isinstance(a, MutableMapping))
# 结果
True

我们看下dict的继承关系

class MutableMapping(Mapping):

    __slots__ = ()

    """A MutableMapping is a generic container for associating
    key/value pairs.

    This class provides concrete generic implementations of all
    methods except for __getitem__, __setitem__, __delitem__,
    __iter__, and __len__.

    """

    @abstractmethod
    def __setitem__(self, key, value):
        raise KeyError

    @abstractmethod
    def __delitem__(self, key):
        raise KeyError
        
class Mapping(Collection):

    __slots__ = ()

    """A Mapping is a generic container for associating key/value
    pairs.

    This class provides concrete generic implementations of all
    methods except for __getitem__, __iter__, and __len__.

    """

    @abstractmethod
    def __getitem__(self, key):
        raise KeyError
        
class Collection(Sized, Iterable, Container):

    __slots__ = ()

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Collection:
            return _check_methods(C,  "__len__", "__iter__", "__contains__")
        return NotImplemented

以上就是dict的继承关系，我们看到很多和list有重复的，也就是说他们有很多相同方法。

dict的常用方法

我们查看源码对应的方法

我们看下fromkeys方法，是将一个可迭代的序列生成为一个字典的键。

new_list = ["key1", "key2"]
# 可以为字典设置默认值
new_dict = dict.fromkeys(new_list, "test")
new_dict = dict.fromkeys(new_list, {"test": "test"})

我们查找一个不存在的值使用setdefault将会返回默认值，然后插入到字典。

In [27]: new_dict = dict()

In [28]: new_dict.setdefault("learn", "learn")
Out[28]: 'learn'

In [29]: new_dict
Out[29]: {'learn': 'learn'}

set和frozenset

set 集合 fronzenset (不可变集合) 无序，不重复

1	s = frozenset("abcde") #frozenset 可以作为dict的key

frozenset是不可变的不像set有add方法，因此可以作为字典的key。

#向set添加数据
another_set = set("cef")
re_set = s.difference(another_set)
re_set = s - another_set
re_set = s & another_set

# 可以使用issubset判断一个几个是否是另一个集合的子集
def issubset(self, *args, **kwargs): # real signature unknown
""" Report whether another set contains this set. """
pass

dict和set的实现原理

校验规则查看老师的源码：https://github.com/liyaopinner/AdvancePython_resource

这里只是总结：

dict查找的性能远远大于list
在list中随着list数据的增大查找时间会增大
在dict中查找元素不会随着dict的增大而增大

dict的key或者set的值都必须是可以hash的不可变对象都是可hash的， str， fronzenset， tuple，自己实现的类 __hash__
dict的内存花销大，但是查询速度快，自定义的对象或者python内部的对象都是用dict包装的
dict的存储顺序和元素添加顺序有关
添加数据有可能改变已有数据的顺序

dict的实现原理（哈希表）:

数组根据偏移量的查询复杂度为O(1)