集合(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 : 判断键是否相等 -> 相等则返回,否则(发生散列冲突)再使用散列值的另一部分来定位散列表的另一行。