[解決済み] set()はどのように実装されていますか？

質問

という声を見かけることがあります。 set オブジェクトのメンバーシップチェックはO(1)です。これを可能にするために、それらは内部でどのように実装されているのでしょうか？どのようなデータ構造を使っているのでしょうか？その実装は他にどのような意味を持つのでしょうか？

どの回答も本当に勉強になりましたが、1つしか受け入れられないので、私の最初の質問に最も近い回答でいきます。情報をありがとうございました。

どのように解決するのですか？

によると このスレッド :

確かに、CPythonのセットは辞書のようなものとして実装されています。 ダミーの値（キーはセットのメンバー）を持つ、いくつかの この値がないことを利用した最適化です。

つまり、基本的には set は、その基礎となるデータ構造としてハッシュテーブルを使用します。このことから O(1) メンバーシップチェックは、ハッシュテーブルの項目を検索するのは O(1) という操作を平均的に行う。

を閲覧することもできます。 のCPythonソースコードです。 set によると アキム・ドマ であった。 もともと からのカットアンドペーストがほとんどです。 dict の実装があります。

注：現在では set と dict の実装は乖離している かなり そのため、様々なユースケースにおける正確な動作（例：任意の順序と挿入順序）やパフォーマンスは異なりますが、ハッシュテーブルの観点から実装されているため、平均的なケースのルックアップと挿入はそのままです。 O(1) しかし set はもはや単なる " ではありません。 dict が、ダミー/省略キー"で表示されます。