集合（Set）和字典（Dict）
《Python3高级核心技术97讲，bobby》学习笔记，第五章：理解集合和字典。
352阅读 · 2020-6-10 23:29发布
5.1 dict的abc继承关系
- 可以通过collections下abc类中的MutableMapping学习dict。
- MutalbeMapping继承Mapping。
MutableMapping抽象基类：
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 __marker = object() def pop(self, key, default=__marker): '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. If key is not found, d is returned if given, otherwise KeyError is raised. ''' try: value = self[key] except KeyError: if default is self.__marker: raise return default else: del self[key] return value def popitem(self): '''D.popitem() -> (k, v), remove and return some (key, value) pair as a 2-tuple; but raise KeyError if D is empty. ''' try: key = next(iter(self)) except StopIteration: raise KeyError from None value = self[key] del self[key] return key, value def clear(self): 'D.clear() -> None. Remove all items from D.' try: while True: self.popitem() except KeyError: pass def update(self, other=(), /, **kwds): ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. If E present and has a .keys() method, does: for k in E: D[k] = E[k] If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v In either case, this is followed by: for k, v in F.items(): D[k] = v ''' if isinstance(other, Mapping): for key in other: self[key] = other[key] elif hasattr(other, "keys"): for key in other.keys(): self[key] = other[key] else: for key, value in other: self[key] = value for key, value in kwds.items(): self[key] = value def setdefault(self, key, default=None): 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' try: return self[key] except KeyError: self[key] = default return default MutableMapping.register(dict)
5.2 dict常用方法
在pycharm中，通过ctrl+鼠标左键点击dict()，可以查看dict源码（以代码形式展示文档）。源码如下：
class dict(object): """ dict() -> new empty dictionary dict(mapping) -> new dictionary initialized from a mapping object's (key, value) pairs dict(iterable) -> new dictionary initialized as if via: d = {} for k, v in iterable: d[k] = v dict(**kwargs) -> new dictionary initialized with the name=value pairs in the keyword argument list. For example: dict(one=1, two=2) """ def clear(self): # real signature unknown; restored from __doc__ """ D.clear() -> None. Remove all items from D. """ pass def copy(self): # real signature unknown; restored from __doc__ """ D.copy() -> a shallow copy of D """ pass @staticmethod # known case def fromkeys(*args, **kwargs): # real signature unknown """ Create a new dictionary with keys from iterable and values set to value. """ pass def get(self, *args, **kwargs): # real signature unknown """ Return the value for key if key is in the dictionary, else default. """ pass def items(self): # real signature unknown; restored from __doc__ """ D.items() -> a set-like object providing a view on D's items """ pass def keys(self): # real signature unknown; restored from __doc__ """ D.keys() -> a set-like object providing a view on D's keys """ pass def pop(self, k, d=None): # real signature unknown; restored from __doc__ """ D.pop(k[,d]) -> v, remove specified key and return the corresponding value. If key is not found, d is returned if given, otherwise KeyError is raised """ pass def popitem(self, *args, **kwargs): # real signature unknown """ Remove and return a (key, value) pair as a 2-tuple. Pairs are returned in LIFO (last-in, first-out) order. Raises KeyError if the dict is empty. """ pass def setdefault(self, *args, **kwargs): # real signature unknown """ Insert key with a value of default if key is not in the dictionary. Return the value for key if key is in the dictionary, else default. """ pass def update(self, E=None, **F): # known special case of dict.update """ D.update([E, ]**F) -> None. Update D from dict/iterable E and F. If E is present and has a .keys() method, then does: for k in E: D[k] = E[k] If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v In either case, this is followed by: for k in F: D[k] = F[k] """ pass def values(self): # real signature unknown; restored from __doc__ """ D.values() -> an object providing a view on D's values """ pass def __contains__(self, *args, **kwargs): # real signature unknown """ True if the dictionary has the specified key, else False. """ pass def __delitem__(self, *args, **kwargs): # real signature unknown """ Delete self[key]. """ pass def __eq__(self, *args, **kwargs): # real signature unknown """ Return self==value. """ pass def __getattribute__(self, *args, **kwargs): # real signature unknown """ Return getattr(self, name). """ pass def __getitem__(self, y): # real signature unknown; restored from __doc__ """ x.__getitem__(y) <==> x[y] """ pass def __ge__(self, *args, **kwargs): # real signature unknown """ Return self>=value. """ pass def __gt__(self, *args, **kwargs): # real signature unknown """ Return self>value. """ pass def __init__(self, seq=None, **kwargs): # known special case of dict.__init__ """ dict() -> new empty dictionary dict(mapping) -> new dictionary initialized from a mapping object's (key, value) pairs dict(iterable) -> new dictionary initialized as if via: d = {} for k, v in iterable: d[k] = v dict(**kwargs) -> new dictionary initialized with the name=value pairs in the keyword argument list. For example: dict(one=1, two=2) # (copied from class doc) """ pass def __iter__(self, *args, **kwargs): # real signature unknown """ Implement iter(self). """ pass def __len__(self, *args, **kwargs): # real signature unknown """ Return len(self). """ pass def __le__(self, *args, **kwargs): # real signature unknown """ Return self<=value. """ pass def __lt__(self, *args, **kwargs): # real signature unknown """ Return self<value. """ pass @staticmethod # known case of __new__ def __new__(*args, **kwargs): # real signature unknown """ Create and return a new object. See help(type) for accurate signature. """ pass def __ne__(self, *args, **kwargs): # real signature unknown """ Return self!=value. """ pass def __repr__(self, *args, **kwargs): # real signature unknown """ Return repr(self). """ pass def __reversed__(self, *args, **kwargs): # real signature unknown """ Return a reverse iterator over the dict keys. """ pass def __setitem__(self, *args, **kwargs): # real signature unknown """ Set self[key] to value. """ pass def __sizeof__(self): # real signature unknown; restored from __doc__ """ D.__sizeof__() -> size of D in memory, in bytes """ pass __hash__ = None
- clear方法：清空dict中的元素。
- copy方法：浅拷贝，值拷贝的是对象地址。（深拷贝可以使用内置的copy.deepcopy）
- fromkeys方法：将可迭代对象转换成dict。dict.fromkeys(new_list,"default value")
- setdefault方法：先查询get是否存在，如果不存在则set。new_dict.setdefault('qqfhkey','qqfhvalue')
- update方法：将两个dict合并。new_dict.update({'test1':'test2'})
5.3 dict的子类
- 如果需要继承dict自定义方法，可以继承collections下的UserDict。
- 如果继承dict，有些情况下不会调用我们覆盖的方法。
- collections.defaultdict可以为字典提供默认值。
- defaultdict的missing会在找不到key时被调用。
5.4 set和frozenset
- set（集合）和fronzenset（不可变集合）。特点：无序，不重复，使用的hash，性能较高。
- set初始化接收可迭代对象。
- frozenset可以作为dict的key。
- 拥有集合运算：& | -（交并差）
- issubset方法：判断一个set是否为另一个set的一部分。
5.5 dict和set的实现原理
- 查找性能比较：dict/set > list。
- 内存花销比较：dict > set。
- dict/set 的存储是基于哈希表（又称散列表）。
- dict的key或set的值必须是可hash（不可变对象都是可hash，如str,fronzenset,tuple，实现hash返回固定值的类）。
- list中随着list数据增大，查找时间会加大。dict/set中查找元素的时间不会随着数据增大而增大。
- hash查找数据流程：计算键的散列值->使用散列值的一部分来定位散列表中的一个表元->表元是否为空? 抛出KeyError : 判断键是否相等 -> 相等则返回，否则（发生散列冲突）再使用散列值的另一部分来定位散列表的另一行。