java - Python辞書はJavaハッシュマップ/ハッシュテーブルと比較して複雑さを検索します

Question

重複の可能性：
Pythonの組み込み辞書はどのように実装されていますか

私はPythonにかなり慣れておらず、Javaのバックグラウンドを持っています。Pythonの辞書がJavaのハッシュマップと同じ検索の複雑さを持っているかどうか疑問に思いました。例：Javaのハッシュテーブル/マップでキーを検索することは定数時間の操作ですが、Pythonで辞書のキーを検索することも定数時間の操作であるかどうか疑問に思いました。マッピングに関するPythonのドキュメントを数ページ読んだのですが、Pythonで辞書のキーがハッシュされていることを示していないようです。そのため、次のことを考えていました。

1. Pythonで辞書のキーを検索することは、定数時間の操作でした。
2. もしそうなら、彼らはどのようにしてハッシュなしでこの一定時間の検索を達成するのでしょうか？

Answer 1

Python辞書には、O（1）検索の複雑さがあります。

時間計算量のwikiページを参照してください。

Python辞書はハッシュテーブルとして実装され、キーはハッシュされます。__hash__メソッドを実装することでハッシュに影響を与えることができます。