检查foo={'foo'：1，'zip'：2，'zam'：3，'bar'：4}的负载因子

Question

假设这样一个关联数组

foo = {'foo':1,'zip':2,'zam':3,'bar':4}

如何检查哈希表的负载因子？你知道吗

Answer 1

加载因子=项目总数/哈希表大小。据我所知，cpython3.6 dictis 8中最小的表大小不超过5个活动条目

Answer 2

而公式取决于（C）Python版本和指针大小（有时甚至键的类型！），您可以用sys.getsizeof()来测量它。后面的确切数字适用于64位版本。你知道吗

在Python2中，它非常简单：280b表示PyDictObject（其容量始终为8）及其PyGC_Head，因此容量是

def cap2(d): return (sys.getsizeof(d)-280)/24 or 8

这个版本的词典增长了四倍，如果很大的话，增长了一倍。你知道吗

在3.6之前的Python3中，有96b的固定开销（除了用于在类实例之间共享属性名的所谓“拆分表”），因此

def cap3(d): return (sys.getsizeof(d)-96)//24

字典（版本3.5）增长了一倍（在没有删除的情况下）。你知道吗

由于3.6，开销是112b。进一步的存储更复杂，因为实际的哈希表只存储索引，并且索引的大小是可变的。然后我们必须使用dictobject.c中USABLE_FRACTION的公式，并计算出用于表容量2^n（n=3）的空间是

112+(1<<n)*(n//8+1)+(1<<n+1)//3*24

这很难精确地反转，但是（考虑到这些严格的假设），你可以近似为2的最大幂，不大于十七分之一（！）尺寸：

def cap36(d):
  s=sys.getsizeof(d)//17
  n=3
  while 1<<n+1<=s: n+=1
  return n

别忘了用容量除以len(d)！你知道吗