データ構造のハッシュテーブル: Python 例
サラ・チェン
ハッシングとは？
ハッシュは固定長の値であり、数式を使用して生成されます。 ハッシュ値は、データ圧縮や暗号化などで使用されます。データのインデックス作成では、生成に使用された値に関係なく、ハッシュ値のサイズが固定長であるため、ハッシュ値が使用されます。 これにより、ハッシュ値は、さまざまな長さの他の値と比較して最小限のスペースを占めるようになります。
ハッシュ関数は、数学的アルゴリズムを使用してキーをハッシュに変換します。 ハッシュ関数が複数のキーに対して同じハッシュ値を生成すると、衝突が発生します。
ハッシュテーブルとは何ですか?
A ハッシュ表 キーと値のペアを使用して値を格納するデータ構造です。 各値には、ハッシュ関数を使用して生成される一意のキーが割り当てられます。
キーの名前は、関連付けられた値にアクセスするために使用されます。これにより、ハッシュ テーブル内の項目の数に関係なく、ハッシュ テーブル内の値の検索が非常に高速になります。
ハッシュ関数
たとえば、従業員レコードを保存する場合、各従業員は従業員番号を使用して一意に識別されます。
従業員番号をキーとして使用し、従業員データを値として割り当てることができます。
上記の方法では、次の追加の空き領域が必要になります。 (m * n2) ここで、変数 m は、 配列、変数 n は従業員番号の桁数です。 このアプローチでは、ストレージスペースの問題が発生します。
ハッシュ関数は、従業員番号を取得し、それを使用してハッシュ整数値、固定桁を生成し、記憶領域を最適化することで、上記の問題を解決します。 ハッシュ関数の目的は、保存する値を参照するために使用されるキーを作成することです。 この関数は保存する値を受け取り、アルゴリズムを使用してキーの値を計算します。
以下は単純なハッシュ関数の例です。
h(k) = k1 % m
ここに、
- h(k) はパラメータ k を受け取るハッシュ関数です。 パラメータ k は、キーを計算する値です。
- k1 % m はハッシュ関数のアルゴリズムです。k1 は保存する値、m はリストのサイズです。モジュラス演算子を使用してキーを計算します。
例
固定サイズ3のリストがあり、次の値があると仮定します。
【1,2,3]
上記の式を使用して、各値が占めるべき位置を計算できます。
次の画像は、ハッシュ テーブルで使用可能なインデックスを示しています。
ステップ1） 次のように最初の値が占める位置を計算します
h(1) = 1 % 3
= 1
値 1が占有します 上のスペース インデックス1
ステップ2） XNUMX 番目の値が占める位置を計算します
h(2) = 2 % 3
= 2
値 2が占有します 上のスペース インデックス2
ステップ3） XNUMX 番目の値が占める位置を計算します。
h(3) = 3 % 3
= 0
値 3が占有します 上のスペース インデックス0
最終結果
埋め込まれたハッシュ テーブルは次のようになります。
優れたハッシュ関数の性質
優れたハッシュ関数には、次のような特性が必要です。
- ハッシュを生成する式では、アルゴリズムに保存されるデータの値を使用する必要があります。
- ハッシュ関数は、同じ量の入力データであっても、一意のハッシュ値を生成する必要があります。
- この関数は衝突の数を最小限に抑える必要があります。 複数の値に対して同じ値が生成されると、衝突が発生します。
- 値は、可能なハッシュ全体にわたって一貫して分散される必要があります。
衝突
アルゴリズムが複数の値に対して同じハッシュを生成すると、衝突が発生します。
例を見てみましょう。
次のような値のリストがあるとします
【3,2,9,11,7]
ハッシュ テーブルのサイズが 7 であると仮定し、次の式を使用します (k1 % m) ここで、m はハッシュ テーブルのサイズです。
次の表は生成されるハッシュ値を示しています。
| キー | ハッシュ アルゴリズム (k1 % m) | ハッシュ値 |
|---|---|---|
| 3 | 3％7 | 3 |
| 2 | 3％7 | 2 |
| 9 | 3％7 | 2 |
| 11 | 3％7 | 4 |
| 7 | 3％7 | 0 |
上記の結果からわかるように、値 2 と値 9 は同じハッシュ値を持ち、各位置に複数の値を格納することはできません。
与えられた問題は、チェーニングまたはプローブのいずれかを使用して解決できます。次のセクションでは、チェーニングとプローブについて詳しく説明します。
連鎖
チェーン化は、それぞれが一意のインデックスを持つリンク リストを使用して衝突の問題を解決するために使用される手法です。
次の画像は連鎖リストがどのように見えるかを視覚化したものです。
2 と 9 は両方とも同じインデックスを占めますが、リンクされたリストとして保存されます。 各リストには一意の識別子があります。
連鎖リストの利点
連鎖リストの利点は次のとおりです。
- 連鎖リストは、挿入順序が O(1) であるため、データ挿入時のパフォーマンスが向上します。
- 連鎖リストを使用するハッシュ テーブルのサイズを変更する必要はありません。
- 空き領域があれば、多数の値を簡単に収容できます。
プロービング
衝突を解決するために使用されるもう XNUMX つの手法はプローブです。 プローブ方法を使用する場合、衝突が発生した場合は、単に先に進み、値を保存する空のスロットを見つけることができます。
調査の方法は次のとおりです。
| 方法 | 説明 |
|---|---|
| リニアプロービング | 名前が示すように、このメソッドは衝突が発生した位置から開始して前方に向かって直線的に空きスロットを検索します。 リストの最後に達しても空のスロットが見つからない場合。 プローブはリストの先頭から始まります。 |
| 二次プロービング | この方法では、XNUMX次多項式を使用して、次に利用可能な空きスロットを見つけます。 |
| Double ハッシング | この手法では、XNUMX 次ハッシュ関数アルゴリズムを使用して、次の空きスロットを見つけます。 |
上記の例を使用すると、プローブを使用した後のハッシュ テーブルは次のようになります。
ハッシュテーブル操作
ここに、 Operaハッシュ テーブルでサポートされるオプション:
- 挿入 - この Opera要素をハッシュ テーブルに追加するために使用されます。
- 検索 - この Operaキーを使用してハッシュ テーブル内の要素を検索するために使用されます。
- 削除 - この Operaハッシュ テーブルから要素を削除するために使用されます
データ挿入操作
挿入操作は、ハッシュ テーブルに値を格納するために使用されます。ハッシュ テーブルに新しい値が格納されると、その値にインデックス番号が割り当てられます。インデックス番号はハッシュ関数を使用して計算されます。ハッシュ関数は、インデックス番号の計算時に発生する衝突を解決します。
データ操作の検索
検索操作は、インデックス番号を使用してハッシュ テーブル内の値を検索するために使用されます。検索操作は、検索インデックス番号にリンクされた値を返します。たとえば、インデックス 6 に値 2 を格納すると、インデックス番号 2 の検索操作は値 6 を返します。
データ削除操作
削除操作はハッシュテーブルから値を削除するために使用されます。 Opera削除はインデックス番号を使用して行われます。値が削除されると、インデックス番号は解放されます。挿入操作を使用して他の値を保存するために使用できます。
ハッシュテーブル実装 Python 例
キーのハッシュ値を計算する簡単な例を見てみましょう。
def hash_key( key, m):
return key % m
m = 7
print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')
ハッシュテーブルコードの説明
ここに、
- パラメータ key と m を受け入れる関数 hash_key を定義します。
- 単純な剰余演算を使用してハッシュ値を決定します
- 値 7 に初期化される変数 m を定義します。これはハッシュ テーブルのサイズです。
- 3のハッシュ値を計算して出力します。
- 2のハッシュ値を計算して出力します。
- 9のハッシュ値を計算して出力します。
- 11のハッシュ値を計算して出力します。
- 7のハッシュ値を計算して出力します。
上記のコードを実行すると、次の結果が生成されます。
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python 辞書の例
Python Dictionary と呼ばれる組み込みデータ型が付属しています。 辞書はハッシュ テーブルの一例です。 キーと値のペアを使用して値を保存します。 ハッシュ値は自動的に生成され、衝突はバックグラウンドで解決されます。
次の例は、辞書データ型を python 3
employee = {
'name': 'John Doe',
'age': 36,
'position': 'Business Manager.'
}
print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()
print (employee)
ここに、
- ディクショナリ変数employeeを定義します。 キー名は値 John Doe を格納するために使用され、age は 36 を格納し、position は値 Business Manager を格納します。
- キー名の値を取得し、ターミナルに出力します。
- キーの位置の値をソフトウェア エンジニアの値に更新します。
- キーの名前と位置の値を出力します。
- ディクショナリ変数employeeに格納されているすべての値を削除します。
- 従業員の値を出力します
上記のコードを実行すると、次の結果が生成されます。
The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}
複雑さの分析
ハッシュ テーブルの平均時間計算量は、最良の場合で O (1) です。最悪の場合の時間計算量は O(n) です。最悪のシナリオは、多くの値が同じハッシュ キーを生成する場合に発生し、プローブによって衝突を解決する必要があります。
実際のアプリケーション
現実世界では、ハッシュ テーブルはデータを保存するために使用されます。
- データベース
- 連想配列
- セット
- メモリキャッシュ
ハッシュテーブルの利点
ハッシュ テーブルを使用する利点と利点は次のとおりです。
- ハッシュ テーブルは、データの検索、既存の値の挿入、削除において高いパフォーマンスを発揮します。
- ハッシュ テーブルの時間の計算量は、テーブル内の項目の数に関係なく一定です。
- 大規模なデータセットを操作する場合でも、非常に優れたパフォーマンスを発揮します。
ハッシュテーブルのデメリット
ハッシュ テーブルを使用する場合の短所は次のとおりです。
- Null 値をキーとして使用することはできません。
- を使用してキーを生成する場合、衝突を避けることはできません。 ハッシュ関数。 すでに使用されているキーが生成されると、衝突が発生します。
- ハッシュ関数で多くの衝突が発生すると、パフォーマンスの低下につながる可能性があります。
まとめ
- ハッシュ テーブルは、キーと値のペアを使用してデータを保存するために使用されます。
- ハッシュ関数は、数学的アルゴリズムを使用してハッシュ値を計算します。
- 複数の値に対して同じハッシュ値が生成されると、衝突が発生します。
- チェーンでは、リンクされたリストを作成することで衝突を解決します。
- プローブでは、ハッシュ テーブル内の空のスロットを見つけて衝突を解決します。
- リニア プローブは、衝突が発生したスロットから開始して値を保存する次の空きスロットを検索します。
- 二次プローブでは、衝突が発生したときに多項式を使用して次の空きスロットを見つけます。
- Double ハッシュでは、衝突が発生したときに二次ハッシュ関数アルゴリズムを使用して、次の空きスロットを見つけます。
- ハッシュ テーブルは、他のデータ構造と比較してパフォーマンスが優れています。
- ハッシュテーブルの平均時間計算量はO（1）である。
- Python の辞書データ型は、ハッシュ テーブルの例です。
- ハッシュ テーブルは、挿入、検索、削除の操作をサポートします。
- NULL 値をインデックス値として使用することはできません。
- ハッシュ関数では衝突を避けることはできません。 適切なハッシュ関数を使用すると、発生する衝突の数が最小限に抑えられ、パフォーマンスが向上します。
