python - 在 Python 3.7+ 中查找字典中第一项的时间复杂度

Question

自 Python 3.7 起，字典保留基于插入的顺序。

似乎您可以使用 next(iter(my_dict)) 获取字典中的第一项？

我的问题是关于该操作的 Big O 时间复杂度？

我可以把 next(iter(my_dict)) 看做一个常数时间(O(1))的操作吗？或者在恒定时间内检索字典中第一项的最佳方法是什么？

我问的原因是我希望将它用于编码面试，其中非常强调解决方案的时间复杂性，而不是它以毫秒为单位的运行速度。

Answer 1

这可能是最好的方法(实际上你现在得到第一个键，next(iter(d.values())) 得到你的值)。

此操作(至少通过 keys、values 或 items 组合表的任何迭代)iterates通过一个包含 dictionary entries 的数组:

PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
while (i < n && entry_ptr->me_value == NULL) {
    entry_ptr++;
    i++;
}

entry_ptr->me_value 保存每个相应键的值。

如果您的字典是新创建的，这将在第一次迭代期间找到第一个插入的项目(字典条目数组是仅追加的，因此保留顺序)。

如果您的字典已被更改(您删除了许多项目)，在最坏的情况下，这可能会导致 O(N) 找到第一个(在剩余项目中)插入的项目(其中 N 是总数原始项目数)。这是因为在删除项目时字典没有调整大小，因此 entry_ptr->me_value 对于许多条目都是 NULL。

请注意，这是特定于 CPython 的。我不知道 Python 的其他实现是如何实现这一点的。