python - 在 Python 3.6+ 中按位置高效访问字典项目

Question

我知道字典是 insertion ordered in Python 3.6+ ，作为 3.6 中的实现细节和 3.7+ 中的官方版本。

考虑到它们是有序的，没有方法可以通过插入顺序检索字典的i^th项，这似乎很奇怪。 only solutions可用的复杂度似乎为 O(n)，其中之一是:

1. 通过 O(n) 过程转换为列表，然后使用 list.__getitem__。
2. 枚举循环中的字典项，并在达到所需索引时返回值。同样，时间复杂度为 O(n)。

由于从 list 获取项目的复杂度为 O(1)，有没有办法用字典实现相同的复杂度？使用常规 dict 或 collections.OrderedDict 都可以。

如果不可能，是否存在结构性原因阻止这种方法，或者这只是一个尚未考虑/实现的功能？

Answer 1

对于 OrderedDict 来说，它本质上是 O(n)，因为排序记录在 linked list 中。 .

对于内置字典，有一个向量(一个连续数组)而不是一个链表，但最终几乎是一样的:向量包含几种“虚拟”，特殊的内部值，意味着“不” key 已存储在这里”或“ key 曾经存储在这里，但不再存储”。例如，这使得删除 key 极其便宜(只需用虚拟值覆盖 key )。

但是如果不在此基础上添加辅助数据结构，就无法一次跳过一个虚拟对象而跳过它们。由于 Python 使用开放寻址形式来解决冲突，并将负载因子保持在 2/3 以下，因此向量的至少三分之一的条目是虚拟的。 the_vector[i] 可以在 O(1) 时间内访问，但实际上与第 i 个非虚拟条目没有可预测的关系。