在Python 3.6及更高版本中按位置访问字典项

在Python 3.6及更高版本中按位置访问字典项

对于，

OrderedDict

这本质上

O(n)

是因为排序记录在链接列表中。

对于内置的dict，有一个向量（一个连续的数组）而不是一个链表，但是最后几乎是一样的：向量包含几种“假人”，特殊的内部值表示“没有密钥。或“曾经存储在这里但不再存储的密钥”。例如，这使得删除密钥变得非常便宜（只需用虚拟值覆盖密钥）。

但是，如果不在此之上添加辅助数据结构，就无法跳过虚拟变量而不一次移动它们。因为Python使用一种开放式寻址的形式来解决冲突，并将负载因子保持在2/3以下，所以向量的至少三分之一
是 假人。

the_vector[i]

可以及时访问

O(1)

，但实际上与第i个非虚拟条目没有可预测的关系。