《Python源码剖析》读书笔记-5 Dict对象


第5章 Python中的Dict对象

  • Dict对象定义为:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    typedef struct {
    /* Cached hash code of me_key. Note that hash codes are C longs.
    * We have to use Py_ssize_t instead because dict_popitem() abuses
    * me_hash to hold a search finger.
    */

    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
    } PyDictEntry;

    typedef struct _dictobject PyDictObject;
    struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill; /* # Active + # Dummy */
    Py_ssize_t ma_used; /* # Active */

    /* The table contains ma_mask + 1 slots, and that's a power of 2.
    * We store the mask instead of the size because the mask is more
    * frequently needed.
    */

    Py_ssize_t ma_mask;

    /* ma_table points to ma_smalltable for small tables, else to
    * additional malloc'ed memory. ma_table is never NULL! This rule
    * saves repeated runtime null-tests in the workhorse getitem and
    * setitem calls.
    */

    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
    };
  • Dict对象不像其他键值类对象(如STL的map)那样采用红黑树而是采用了散列值,这是因为后者效率更高(同时也更耗内存);而PyDictObject也经常被用在Python的C代码中,因此需要使用更高效的实现。
  • 使用散列来存储,就不可避免的会出现哈希冲突。PyDictObject采用的处理冲突的方式是开放定址法(wiki),即当插入出现冲突时,通过一个固定的函数去获取下一个可能的位置,直到没有冲突为止。但是采用这种方法,删除一个键值对时,就不能直接删除,而是必须为其做“伪删除”,否则会在查找的时候出现开放定址法查找链的断裂。这里,使用一个dummy对象来标记那些被删除的键值对。所以,PyDictObject中的所有键值对就分成了三种状态:actived, dummy, unused。
  • ma_table和ma_smalltable。这里注意,ma_smalltable是以栈上的数组定义的,也就是只要定义了一个PyDictObject,那么就一定会有PyDict_MINSIZE个PyDictEntry对象被分配到栈上。这是因为经过实验,大部分dict对象内的键值对个数都不会超过PyDict_MINSIZE(8,可以自己修改),这样减少了大量的malloc请求,提高了运行时效率。ma_table也与此相关。当字典中的键值对数目不超过PyDict_MINSIZE时,ma_table实际是指向ma_smalltable的;只有当其中的键值对更多时,ma_table才指向另外一块malloc出来的内存。这种做法使得ma_table始终有效,避免了不断地去判断ma_table != NULL。
  • 创建函数PyDict_New

    • 在PyDict_New函数中出现的EMPTY_TO_MINSIZE宏中有一个奇怪的do{…}while(0)语句。do{…}while(0)经常用于宏定义,以使使用这个宏的语句看上去符合c的语法。
    • 例如,如下定义的宏:

      1
      #define EMPTY_TO_MINSIZE(x, y) do{x++; y++;}while(0)
    • 可以这么使用:

      1
      2
      3
      4
      if(i==0)
      EMPTY_TO_MINSIZE(i, i);
      else
      return -1;
    • 而如果把宏定义为

      1
      #define EMPTY_TO_MINSIZE(x, y) {x++; y++;}
    • 或者

      1
      #define EMPTY_TO_MINSIZE(x, y) x++; y++;
    • 都会出现编译错误或者歧义。

    • PyDictObject的缓冲池策略和之前PyListObject的策略基本一样,都是维护了一个缓冲池数组,而只有在释放PyDictObject时(即,调用dict_dealloc函数时),才会将不用的PyDictObject加入缓冲池。
  • 元素搜索lookdict或者lookdict_string

    • freeslot
      if (ep->me_key == dummy)
      freeslot = ep;
      
    • 这里的freeslot用于记录搜索过程中发现的第一个dummy entry,之后如果本次搜索不成功,则应该返回此dummy entry;没有dummy entry的情况下,才返回unused entry。这样能够提高内存使用效率。
    • 查找的过程中使用PyObject_RichCompareBool来判断两个PyObject*指针的相等。内部其实综合考虑了引用相等和值相等两种情况。
    • 搜索策略上,与开放定址法处理插入哈希冲突的方式相对应。首先查看哈希值直接对应的位置是否为所查找的键,不是则按照开放定址法的规则依次查找接下来可能的位置,直到找到或者遇到一个unused entry。
    • 在查找的过程中有这么一句判断语句,if (ep0 == mp->ma_table && ep->me_key == startkey) 按照上下文,其中的两个判断条件恒为true,不理解这里为什么要加这么一句,难道是为了处理什么奇怪的bug么?我在StackOverflow上提了这个问题,链接在这里
    • lookdict_string是lookdict的特殊情况,在判断时可以直接使用_PyString_Eq,效率更高。
  • 插入、删除都基于上述的查找功能。

评论