Pythonの辞書を実装する方法

(*-*)浩
(*-*)浩オリジナル
2019-07-02 14:34:293579ブラウズ

Python の dict オブジェクトは、それがキーと値のペアの形式で保存されたプリミティブ Python データ型であることを示し、その中国語名が辞書に翻訳されます。名前が示すように、キー名で対応する値。時間計算量は定数レベルで O(1) です。

Pythonの辞書を実装する方法

dict 基礎となる実装 (学習を推奨) : Python ビデオ チュートリアル

Python2 では、辞書の最下層はハッシュ テーブルによって実装され、競合を解決するためにオープン アドレス メソッドが使用されます。その検索の時間計算量は O(1) になります。

Dict 操作の実装原理 (挿入、削除、バッファ プールなどを含む)

最初に以下を紹介します。 PyDictObject オブジェクト要素の検索戦略:

2 つの検索戦略、つまり lookdict と lookdict_string があります。Lookdict_string は、PyStringObject を検索するときの lookdict の特別な形式です。一般的な検索戦略 lookdict の主なロジックは次のとおりです:

(1) 最初のエントリの検索:

a) ハッシュ値に基づいてエントリのインデックスを取得します。

b) エントリが未使用状態の場合、検索は終了します。エントリが指すキーが検索されたキーと同じ場合 キーが同じ場合、検索は成功です。

c) 現在のエントリがダミー状態の場合、フリースロットを設定します(ここでのフリースロットは(エントリを保存するためにすぐに利用可能な次のアドレスとして返されます)

d) アクティブなエントリを確認します。キーが指す値が検索された値と同じであれば、検索は成功です

(2) 残りの検出チェーン内の要素を走査して検索します:

a )使用する検出関数に従って、検出チェーン上でチェックされる次のエントリを取得します

b)未使用のエントリが検出され、検索が失敗したことを示します:

フリースロットが空でない場合はフリースロットを返し、それ以外の場合は未使用のエントリを返します

c) エントリのキーが同じかどうかを確認します検索対象のキーの参照として入力し、同じであれば検索は成功し、エントリを返します。

d) エントリを確認します。キーの値が検索されたキーの値と同じかどうかを確認します。 e) トラバーサル プロセス中に、ダミー状態のエントリが見つかり、フリースロットが設定されていない場合は、フリースロット

## を設定します。 : PyDictObject オブジェクトの要素を挿入および削除するための戦略:

最初に検索戦略を使用する必要があります。検索が成功した場合、値は直接置換されます。検索が失敗した場合、エントリは未使用になります。状態またはダミー状態が返されます。キー、値、ハッシュ値を設定し、現在挿入されている要素に従って ma_table のサイズを調整します (調整は読み込み率に基づいており、2/3 より大きいかどうかに従って調整されます)。 ); 削除も同様で、まずハッシュ値を計算して、該当するエントリを検索すると、検索が成功し、エントリ内に保持されている要素を削除し、エントリをActive状態からダミー状態に変更します

PyDictObject の実装プロセスでは、バッファ プールが使用されます。PyDictObject オブジェクトが破棄されると、バッファされた PyDictObject オブジェクトの受け入れが開始されます。定義されたバッファ プールが受け入れることができるオブジェクトの数は 80 です。新しい PyDictObject オブジェクトを作成するとき、バッファー プールにオブジェクトがある場合は、バッファー プールから直接取り出すことができます。使用

Python 関連の技術記事の詳細については、

Python チュートリアルをご覧ください。

学べるコラム!

以上がPythonの辞書を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。