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

Question

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

您似乎可以使用 next(iter(my_dict))?

获取字典中的第一项

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

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

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

Answer 1

这可能是最好的方法（实际上您现在获得了第一个密钥，next(iter(d.values())) 获得了您的价值）。

此操作（至少对组合表通过 keys、values 或 items 的任何迭代）iterates through an array holding the 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 的其他实现是如何实现的。