python源码分析:dict对象的实现-2

你是否对上面那个lookdict提出过疑问?

对啦,没有退出语句,它不会成为死循环吧,不会!下面马上提晓答案。

看下面这段代码,位于PyDict_SetItem中:

if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
return 0;
return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

即dict在插入数据时,都会检查hash空间使用情况,一旦新添加一条且(dummy+used)的数量小于空间总大小的2/3,就会执行dictresize,就会来扩展原有的hash空间,从而始终保证空间中有空闲位置,这样上面那个’死循环‘的疑问就解决了

2/3:还有一个原因,就是根据统计结果,发现装载率超过2/3后冲突率就会急剧升高。下面来详细分析下,dict的插入与删除动作中的关键函数:dictresize。它可以扩展dict的hash空间,也可以收缩dict的hash空间。从中也可以看到ma_table的使用细节。

  • 根据传进的参数minused,计算出大于这个数的最小值:

for (newsize = PyDict_MINSIZE;
newsize <= minused && newsize > 0;
newsize <<= 1) ;//以2倍的速度步进

  •  newtable,oldtable:分析各种情况,oldtable指向现在的数据空间;newtable指向resize之后的数据空间。情况有以下几种:
  1. newsize==PyDict_MINSIZE,使用small_table且无处于dummy态的entry,那么就没必进行任何动作
  2. newsize==PyDict_MINSIZE,使用small_table且有处于dummy态的entry,本来是没有必要进行任何动作,因为空间已经无法再收缩了。源码中有这么一句话:“This is *necessary* if fill==size,  as lookdict needs at least one virgin slot to terminate failing searches.”如 果当整个small_table全部填满时,那lookdict就会一直循环下去,这不就是上面提出的疑问吗?看来python设计者也考虑到这个问题 了,解决方法就是让dict始终有一块处女地没有使用,以便结束查找。如果当small_talbe全部被used了,那么就该是下面了
  3. 当newsize>PyDict_MINSIZE时, 因为(mp->ma_used > 50000 ? 2 : 4) * mp->ma_used,所 以active的数量可能还没有超过small_table的容量时,就需要开辟新空间而扔掉那个小table。即如果 newsize>PyDict_MINSIZE时,就需要扩充原有的hash空间,不管你之前有没有使用small_table。通过代码我们可以 看到使用PyMem_NEW申请了newsize大小的空间交给newtable。
  4. 有一种情况没有做任何处理就直接进行下面的‘搬移’ 操作,哪种情况呢?当newsize==PyDict_MINSIZE,且之前没有使用small_table。也就是说,由于这次插入操作,顺道检查出 该hash空间有太多的dummy状态,因此需要收缩空间,也主是将之前使用的那个‘大‘table中处于active的entry映射到 small_table中,为什么能保证一定可以映射呢?因为(mp->ma_used > 50000 ? 2 : 4) * mp->ma_used,它到dictresize中就变成minused,而newsize是始终大于这个值的,所以newsize绝对大于当前处于active态的entry数量。这样一来,就有理由相信映射一定会成功了。

这样,经过上面这几种情况,newtable与oldtable都各就各位了,下面要做的就是将oldtable的内容映射到newtable中了,不需要考虑两者之间的任何关系。

 

发表评论