python辞書実装原理
3006 ワード
引用する
Pythonにおけるdictオブジェクトは、元のPythonデータ型であることを示すものであり、キー値ペアで記憶する、文名が辞書に翻訳され、その名の通りキー名で対応する値を探すことが効率的であり、時間的複雑度が定数レベルO(1)である.本稿では,Pythonのソースコードプロファイリングにかかわらず,実現したデータ構造について原理的に説明し,拡張した.
dict最下位実装
Python 2では、dictの下位層はハッシュテーブル(Hash Table)によって実現する、オープンアドレス法を用いて衝突を解決する.したがって,その検索の時間的複雑さはO(1)であり,ハッシュテーブルの動作原理と衝突を解決するための具体的な方法を以下で具体的に説明する.
ハッシュ表
ハッシュテーブルはkey-valueタイプのデータ構造であり、キー値で直接アクセスします.ハッシュ・テーブルは、ハッシュ関数によってキーと配列のインデックス・マッピングを行い、キー値がどの位置に配置されるべきかを決定します.**ハッシュ・テーブルは、キー値が一定のルールで格納される必要がある配列として理解できますが、ハッシュ関数はこのルールです.**ここではいくつかの専門名詞を提出して、後で一つ一つ紹介します.
1.ハッシュ表が生成された理由
単純なキー値ペア構造、キー-従業員番号、値-勤務中かどうかを仮定します.従業員番号を入力し、従業員が在職しているかどうかを返す機能が必要になります.理想的な方法は、長さMax(従業員番号)の配列を作成することです.配列の下には従業員番号が表示され、配列の値は0と1で見分けることができます.これにより、O(1)の時間的複雑さだけで操作が完了しますが、拡張性が強くなく、以下の問題があります.1.新入社員の従業員番号がMax(従業員番号)よりも大きいと仮定すると、移行操作のために配列を再申請する必要があります.2.極端な場合、2人の従業員が存在し、従業員番号がそれぞれ1と100000001であると仮定すると、従来の設計の考え方では、大きなストレージスペースが浪費されます.
上の2点、第1点は配列の固定申請サイズの属性によって決定されるが、第2点はハッシュテーブルを導入する理由であり、大きな従業員番号を小さくしてマークがなく、ハッシュ関数を生成する方法があるのではないか.ここでのハッシュ規則は3型を除いたものと仮定すると、従業員1が得たハッシュ値は1であり、従業員100000001が得たハッシュ値は2である.このように設計の考え方では,大きさ2の配列1つでカバーできるというハッシュ思想である.アルゴリズムでは時間と空間を兼ねることはできません.ハッシュテーブルは、特定の機能要件に応じて、合理的な時間消費で大量の空間消費を減らす操作です.
2.ハッシュ関数
上記の例ではハッシュ関数の設計は勝手ですが、この例からも情報を得ることができます.
ハッシュ関数はマッピングであるため、ハッシュ関数の設定は柔軟であり、任意のキーワードによって得られるハッシュ関数の数値が表長の許容範囲内に収まるようにすればよい.すべての入力が唯一の出力にしか対応していないわけではありません.つまり、ハッシュ関数は1対1のマッピング関係を作ることはできません.その本質は1対1のマッピングであり、次の概念である衝突を引き出します.
3.衝突
一対一のマッピング関係でなければ、衝突は必然的に発生するのか、それとも上の極端な例なのか、この時に従業員番号が2の従業員を追加しました.まず、私たちの配列の大きさを考慮しないで2にしました.前のハッシュ関数によると、従業員番号が2のハッシュ値も2で、これは100000001の従業員と同じです.これは衝突です.異なる解決構想に対して、3つの異なる解決方法を提出した.
4.競合解決方法
4.1オープンアドレス
オープンアドレスとは、ハッシュ関数に加えて得られたアドレスが利用可能であり、競合が発生した場合に他のアドレスも同様に利用可能であることを意味し、一般的なオープンアドレス思想の方法としては、線形プローブ再ハッシュ、二次プローブ再ハッシュがあり、これらの方法はいずれも第1選択が占有された場合の解決方法である.
4.2再ハッシュ法
この方法は,複数のハッシュ関数を順番に規定し,クエリのたびにハッシュ関数を順番に呼び出し,最初が空のときに返されて存在せず,このキーを呼び出すたびにその値を返す.
4.3チェーンアドレス法
すべてのキーワードハッシュ値が同じレコードを同じ線形チェーンテーブルに存在させることで、他のハッシュアドレスを占有する必要がなくなり、同じハッシュ値がチェーンテーブル上にあり、順番に遍歴すれば見つけることができます.
4.4パブリックオーバーフロー領域
その基本的な考え方は、すべてのキーワードと基本テーブルのキーワードが同じハッシュ値のレコードであり、ハッシュ関数から得られるハッシュアドレスが何であるかにかかわらず、競合が発生するとオーバーフローテーブルに埋め込まれることです.
5.充填因子α
一般的に、競合メソッドは同じハッシュテーブルを処理し、その平均ルックアップ長はハッシュテーブルの充填因子に依存する.ハッシュテーブルの充填因子は、テーブルに埋め込まれた記録数とハッシュテーブル長の壁紙として定義され、すなわちハッシュテーブルの充填度合いを示す.直感的に見ると、α小さいほど衝突の可能性は小さくなり、逆に大きくなります.一般的に0.75が適切であり、数学的導出に関連する.
本文はshouting 3901のCSDNブログから来て、全文の住所はクリックしてください:https://blog.csdn.net/shouting3901/article/details/80468735?utm_source=copy
実装の詳細
CPythonは,辞書の下位データ構造として擬似ランダムプローブ(pseudo−random probing)のハッシュテーブルを用いた.この実装の詳細により,辞書のキーとしてハッシュ可能なオブジェクトのみが使用できる.
Pythonのすべての可変の内蔵タイプはハッシュ可能です.リスト、辞書、コレクションなどの可変タイプはハッシュできないため、辞書のキーとして使用できません.
辞書の3つの基本操作(要素を追加し、要素を取得し、要素を削除する)の平均イベントの複雑度はO(1)であるが、彼らの屋台の最悪の状況の複雑度はO(N)よりずっと高い.
本文は4月晴れのCSDNブログから来て、全文の住所はクリックしてください:https://blog.csdn.net/siyue0211/article/details/80560783?utm_source=copy
Pythonにおけるdictオブジェクトは、元のPythonデータ型であることを示すものであり、キー値ペアで記憶する、文名が辞書に翻訳され、その名の通りキー名で対応する値を探すことが効率的であり、時間的複雑度が定数レベルO(1)である.本稿では,Pythonのソースコードプロファイリングにかかわらず,実現したデータ構造について原理的に説明し,拡張した.
dict最下位実装
Python 2では、dictの下位層はハッシュテーブル(Hash Table)によって実現する、オープンアドレス法を用いて衝突を解決する.したがって,その検索の時間的複雑さはO(1)であり,ハッシュテーブルの動作原理と衝突を解決するための具体的な方法を以下で具体的に説明する.
ハッシュ表
ハッシュテーブルはkey-valueタイプのデータ構造であり、キー値で直接アクセスします.ハッシュ・テーブルは、ハッシュ関数によってキーと配列のインデックス・マッピングを行い、キー値がどの位置に配置されるべきかを決定します.**ハッシュ・テーブルは、キー値が一定のルールで格納される必要がある配列として理解できますが、ハッシュ関数はこのルールです.**ここではいくつかの専門名詞を提出して、後で一つ一つ紹介します.
1.ハッシュ表が生成された理由
単純なキー値ペア構造、キー-従業員番号、値-勤務中かどうかを仮定します.従業員番号を入力し、従業員が在職しているかどうかを返す機能が必要になります.理想的な方法は、長さMax(従業員番号)の配列を作成することです.配列の下には従業員番号が表示され、配列の値は0と1で見分けることができます.これにより、O(1)の時間的複雑さだけで操作が完了しますが、拡張性が強くなく、以下の問題があります.1.新入社員の従業員番号がMax(従業員番号)よりも大きいと仮定すると、移行操作のために配列を再申請する必要があります.2.極端な場合、2人の従業員が存在し、従業員番号がそれぞれ1と100000001であると仮定すると、従来の設計の考え方では、大きなストレージスペースが浪費されます.
上の2点、第1点は配列の固定申請サイズの属性によって決定されるが、第2点はハッシュテーブルを導入する理由であり、大きな従業員番号を小さくしてマークがなく、ハッシュ関数を生成する方法があるのではないか.ここでのハッシュ規則は3型を除いたものと仮定すると、従業員1が得たハッシュ値は1であり、従業員100000001が得たハッシュ値は2である.このように設計の考え方では,大きさ2の配列1つでカバーできるというハッシュ思想である.アルゴリズムでは時間と空間を兼ねることはできません.ハッシュテーブルは、特定の機能要件に応じて、合理的な時間消費で大量の空間消費を減らす操作です.
2.ハッシュ関数
上記の例ではハッシュ関数の設計は勝手ですが、この例からも情報を得ることができます.
ハッシュ関数はマッピングであるため、ハッシュ関数の設定は柔軟であり、任意のキーワードによって得られるハッシュ関数の数値が表長の許容範囲内に収まるようにすればよい.すべての入力が唯一の出力にしか対応していないわけではありません.つまり、ハッシュ関数は1対1のマッピング関係を作ることはできません.その本質は1対1のマッピングであり、次の概念である衝突を引き出します.
3.衝突
一対一のマッピング関係でなければ、衝突は必然的に発生するのか、それとも上の極端な例なのか、この時に従業員番号が2の従業員を追加しました.まず、私たちの配列の大きさを考慮しないで2にしました.前のハッシュ関数によると、従業員番号が2のハッシュ値も2で、これは100000001の従業員と同じです.これは衝突です.異なる解決構想に対して、3つの異なる解決方法を提出した.
4.競合解決方法
4.1オープンアドレス
オープンアドレスとは、ハッシュ関数に加えて得られたアドレスが利用可能であり、競合が発生した場合に他のアドレスも同様に利用可能であることを意味し、一般的なオープンアドレス思想の方法としては、線形プローブ再ハッシュ、二次プローブ再ハッシュがあり、これらの方法はいずれも第1選択が占有された場合の解決方法である.
4.2再ハッシュ法
この方法は,複数のハッシュ関数を順番に規定し,クエリのたびにハッシュ関数を順番に呼び出し,最初が空のときに返されて存在せず,このキーを呼び出すたびにその値を返す.
4.3チェーンアドレス法
すべてのキーワードハッシュ値が同じレコードを同じ線形チェーンテーブルに存在させることで、他のハッシュアドレスを占有する必要がなくなり、同じハッシュ値がチェーンテーブル上にあり、順番に遍歴すれば見つけることができます.
4.4パブリックオーバーフロー領域
その基本的な考え方は、すべてのキーワードと基本テーブルのキーワードが同じハッシュ値のレコードであり、ハッシュ関数から得られるハッシュアドレスが何であるかにかかわらず、競合が発生するとオーバーフローテーブルに埋め込まれることです.
5.充填因子α
一般的に、競合メソッドは同じハッシュテーブルを処理し、その平均ルックアップ長はハッシュテーブルの充填因子に依存する.ハッシュテーブルの充填因子は、テーブルに埋め込まれた記録数とハッシュテーブル長の壁紙として定義され、すなわちハッシュテーブルの充填度合いを示す.直感的に見ると、α小さいほど衝突の可能性は小さくなり、逆に大きくなります.一般的に0.75が適切であり、数学的導出に関連する.
本文はshouting 3901のCSDNブログから来て、全文の住所はクリックしてください:https://blog.csdn.net/shouting3901/article/details/80468735?utm_source=copy
実装の詳細
CPythonは,辞書の下位データ構造として擬似ランダムプローブ(pseudo−random probing)のハッシュテーブルを用いた.この実装の詳細により,辞書のキーとしてハッシュ可能なオブジェクトのみが使用できる.
Pythonのすべての可変の内蔵タイプはハッシュ可能です.リスト、辞書、コレクションなどの可変タイプはハッシュできないため、辞書のキーとして使用できません.
辞書の3つの基本操作(要素を追加し、要素を取得し、要素を削除する)の平均イベントの複雑度はO(1)であるが、彼らの屋台の最悪の状況の複雑度はO(N)よりずっと高い.
本文は4月晴れのCSDNブログから来て、全文の住所はクリックしてください:https://blog.csdn.net/siyue0211/article/details/80560783?utm_source=copy