Python の辞書とハッシュ テーブル、およびハッシュ競合の解決に関する簡単な説明

この記事の内容は、Python の辞書とハッシュ テーブルに関する簡単な説明と、ハッシュ競合の解決に関するものです。一定の参考価値があります。必要な友人は参照できます。お役に立てれば幸いです。

Python はハッシュ テーブルを使用して dict を実装します。

ハッシュ テーブルは実際にはスパース配列です (常に空白の要素を持つ配列をスパース配列と呼びます)。一般書籍では、ハッシュテーブルの単位をバケットと呼ぶことが多いです。存在する 辞書 ハッシュ テーブルでは、各キーと値のペアがテーブル要素を占め、各テーブル要素には 2 つの部分があり、1 つはキーへの参照、もう 1 つは値への参照です。表の各セルは同じサイズであるため、オフセットによって表のセルを読み取ることができます。

Python は、テーブル要素の約 3 分の 1 が空であることを確認しようとします。このしきい値にほぼ達すると、元のハッシュ テーブルを拡張して、より大きなハッシュ テーブルにコピーします。

オブジェクトをハッシュ テーブルに追加する場合は、まず要素キーのハッシュ値を計算する必要があります。これには、キーがハッシュ可能である必要があります。

ハッシュ可能オブジェクトは次の条件を満たす必要があります:

hash() 関数をサポートし、__hash__() メソッドを通じて取得されたハッシュ値は変更されません。

__eq__() メソッドによる等価検出をサポートします。

a == b が true の場合、hash(a) == hash(b) も true になります。

以下では主にハッシュテーブルのアルゴリズムについて説明します。

キーを取得するには search_key に対応する値 search_value 。Python は最初に hash(search_key) を呼び出して計算します。 検索キー 値のハッシュ値、この値の最下位数桁がオフセットとして使用され、ハッシュ テーブル内でテーブル要素が検索されます (特定の数値は現在のハッシュ テーブルのサイズによって異なります)。見つかったテーブル要素が空の場合、KeyError がスローされます 例外; 空でない場合は、テーブル要素に found_key:found_value のペアが存在します。search_key と found_key を確認してください。 それらが等しいかどうか、等しい場合は、found_value を返します。それらが等しくない場合、この状況はハッシュ衝突と呼ばれます。

ハッシュの競合を解決するために、アルゴリズムはハッシュ値のさらに数ビットを取得し、それを特別な方法で処理し、取得した新しい値をオフセットとして使用して検索します。ハッシュ テーブルのテーブル要素。見つかったテーブル要素が空の場合は、KeyError 例外もスローされます。空でない場合は、キーを比較して一貫性があるかどうかを確認し、一貫性がある場合は対応する値を返します。ハッシュの競合が見つかった場合は、上記の手順を繰り返します。

新しい要素の追加は上記のプロセスとほぼ同じですが、空のテーブル要素が見つかった場合に新しい要素が追加される点が異なります。空でない場合は、ハッシュが繰り返され、検索は続行されます。

いつ行くか 新しい要素が辞書に追加され、ハッシュの競合が発生した場合、新しい要素は別の場所に格納されるように調整される可能性があります。したがって、次の状況が発生します: dict([key1, value1], [key2, value2]) および dict([key2, value2], [key1, value1]) 2 つの辞書を比較すると等しいですが、key1 と key2 のハッシュが競合する場合、辞書内の 2 つのキーの順序は異なります。

いつでも行ってください dict、pythonに新しいキーを追加します パーサーは辞書を拡張することを決定する場合があります。拡張の結果、より大きなハッシュ テーブルが作成され、ディクショナリ内の既存の要素が新しいハッシュ テーブルに追加されます。このプロセス中に新しいハッシュの競合が発生し、新しいハッシュ テーブル内のキーの順序が変更される可能性があります。新しいキーを追加しながら辞書を反復処理するとどうなるでしょうか?残念ながら容量が拡張されましたが、残念ながらキーの順番が変わってしまいました。 orz。

ハッシュ テーブルはスパースである必要があるため、その消費スペースはさらに大きくなる必要があり、これは一般的なスペースと時間のトレードオフです。

以上がPython の辞書とハッシュ テーブル、およびハッシュ競合の解決に関する簡単な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。