inserdict() 应用搜寻函数 lookdict_string() 来查找余暇槽。这跟查找键所用的是同一函数。lookdict_string() 应用哈希值和掩码计算槽的索引。如不雅用“索引 = 哈希值&掩码”的办法未找到键，则会用调用先前介绍的轮回办法探测，直至找到一个余暇槽。第一轮探测，如不雅未找到匹配的键的且探测过程中碰到过哑槽，则返回一个哑槽。这可使优先选择先前删除的槽。

如今我们想添加如下的键/值对：{‘a’: 1, ‘b’: 2′, ‘z’: 26, ‘y’: 25, ‘c’: 5, ‘x’: 24}，那么将会产生如下过程：

分派一个字典构造，内部表的尺寸为8。

 

以下就是我们今朝所获得的：

8个槽中的6个已被应用，应用量已经跨越了总容量的2/3，因而，dictresize()函数将会被调用，用以分派一个长度更大年夜的数组，同时将旧表中的条目复制到新的表中。

j = (5*j) + 1 + perturb; 
 
perturb >>= PERTURB_SHIFT; 
 
use j % 2**i as the next table index;  

在我们这个例子中，dictresize()函数被调用后，数组长度调剂后的长度不小于晃荡槽数量的 4 倍，即minused = 24 = 4*ma_used。而当晃荡槽的数量异常大年夜(大年夜于50000)时，调剂后长度应不小于晃荡槽数量的2倍，即2*ma_used。为什么是 4 倍?这主如果为了削减调用调剂长度函数的次数，同时能明显进步稀少度。

arguments: string object 
 
returns: hash 
 
function string_hash: 
 
    if hash cached: 
 
        return it 
 
    set len to string's length 
 
    initialize var p pointing to 1st char of string object 
 
    set x to value pointed by p left shifted by 7 bits 
 
    while len >= 0: 
 
        set var x to (1000003 * x) xor value pointed by p 
 
        increment pointer p 
 
    set x to x xor length of string object 
 
    cache x as the hash so we don't need to calculate it again 
 
    return x as the hash  

　　推荐阅读

　　如何算出精确的PUE？连续监测才是王道

PUE申报精度电力应用效力(PUE)是一个评价数据中间能源效力的通用指标，是数据中间消费的所有能源竽暌闺IT负载应用的能源之比。PUE能赞助数据中间经理有效地治理能耗设备。计算某数据中间举措措施的PUE值有很多原因，>>>详细阅读

本文标题：深入Python字典的内部实现

地址：http://www.17bianji.com/lsqh/35357.html

 1/2    1