java - 与 java hashmap/hashtable 相比，python 字典搜索复杂度

Question

可能重复：
Python 的内置字典是如何实现的

我对python相当陌生，并且有java背景。我想知道 python 中的字典是否具有与 java 中的哈希映射相同的搜索复杂性。示例：在java中搜索哈希表/映射中的键是一个常数时间操作，我想知道在python中搜索字典中的键是否也是一个常数时间操作。我已经阅读了几页关于映射的python文档，但它似乎没有表明python中字典键的任何散列，所以我想知道是否：

1. 在 python 中的字典中搜索键是恒定时间操作。
2. 如果是这样，他们如何在没有散列的情况下实现这种恒定时间搜索？

Answer 1

Python 字典的搜索复杂度为 O(1)。

请参阅时间复杂度 wiki 页面。

Python字典实现为哈希表，键被哈希；您可以通过实现__hash__方法来影响散列。