python - 用于字典方法的 BigO 'get(key)'

Question

有人知道 python 的字典“get(key)”方法的 O(?) 是多少吗？

我已经使用 cProfile 模块对其进行了测试，并在字典中获得了 100、1000、10000、100000、1000000、100000000 条记录的相同时间结果。

这是否意味着python的字典为任何键提供了O(1)的访问时间？

Answer 1

答案是肯定的，因为 Python 字典使用哈希来存储键。哈希表访问其键的平均时间复杂度为 O(1) - 在此处阅读更多信息 http://en.wikipedia.org/wiki/Hash_table .

键检索的最坏情况是O(n)，其中n 是字典 中键的数量。 (@Michael Butscher)。