データ構造 ハッシュテーブル(ハッシュテーブル)とは何ですか?具体的にはどのような操作があるのでしょうか？

1. ハッシュ テーブルとは

ハッシュ テーブルとは何かを知りたい場合は、まずハッシュ関数を理解する必要があります

ハッシュ関数:

前回のブログで説明したバイナリ ソート ツリー、バイナリ バランス ツリー、赤黒ツリー B B ツリーと比較すると、最初にルート ノードから検索が実行され、データまたはノードからインデックスを取り出して値を検索し、比較します。では、関数 H はありますか? この関数と検索キーワードのキーに基づいて、検索値の位置を 1 つずつ比較することなく直接決定できます。このようにして、キーの場所を事前に「把握」し、データを直接見つけて効率を向上させることができます。

つまり、アドレスインデックス=H(キー)

平たく言えば、ハッシュ関数はキーに基づいてアドレスを格納する場所を計算するものであり、ハッシュテーブルはハッシュ関数に基づいて検索します。テーブル

#2#、ハッシュ関数の構築方法 #これまでの経験によれば、一般的に使用されるハッシュ関数の構築方法は次のとおりです。

直接カスタマイズ方法

ハッシュ関数は、次のようなキーワードの線形関数です。 as H (key) = a* key b

この構築方法は比較的単純で統一されていますが、大きな制限があり、アドレス サイズ = キーワード セットの状況に限定されます。例:

中国の人口の年齢分布に関する統計 (10 を最小単位とする) が必要であると仮定します。今年は 2018 年なので、10 歳未満は 2008 年から 2018 年に分布し、20 歳未満は 1998 年から 2008 年に分布します。2018 年が 2018 年から 2008 年の直接データを表すと仮定すると、キーワードは次のようになります。 2018, 2008, 1998...

この場合、ハッシュ関数 H(key)=(2018-key)/10=201-key/10 を構築できます

この場合、ハッシュ テーブルは次のようになります。

インデックスキー 年齢 人数（想定データ）

0 2018 0-10 200W

1 2008 10-20 250W

2 1998 20-30 253W

3 1988 30- 40 300W

……

数値分析方法

各キーワードは、キーワード セットは s 桁 (k1,k2 ,...,knk1,k2,...,kn) で構成され、キー内のデータ全体を分析し、均等に分散された多数のビットまたはその組み合わせを抽出して全体を形成します。

使用例
us ID 番号が規則的であることがわかったので、クラス内の生徒の ID 番号を保存したいとします。このクラスの生徒は全員同じ地域で生まれたと仮定します。同じ年に、ID カードの最初の桁が同じである場合、次の異なるビットをインターセプトして保存できます。5 つの異なるビットがあると仮定し、これらの 5 ビットを使用して住所を表します。

H(key)=key 0000

この方法は通常、桁数が長い場合に使用されますが、数値には一定の法則があり、数値の分布がわかっている必要があります。 , 上記のような たとえば、このクラスの生徒は同じ年、同じ地域で生まれたことが事前にわかっています。

二乗法

キーワードの各桁に頻繁に出現する特定の数字がある場合、まずキーワードの二乗値を求め、二乗して差を拡大します。そして中央の数字を最終的なストレージアドレスとして取得します。 使用例

例: key=1234 1234^2=1522756、ハッシュアドレスとして 227 を取得します

例: key=4321 4321^2=18671041、ハッシュ アドレスとして 671 を取得します

この方法は、データが事前にわかっておらず、データ長が短い場合に適しています

フォールディング方法

If数値の桁数が多い場合、数値をいくつかの部分に分割することができ、それらを重ね合わせた合計をハッシュ アドレスとして取得します。

使用例 たとえば key=123 456 789 それを 61524 に保存できます。下3桁で524の位置があります
この方法は数字に適しています 桁数が多くデータの分布が事前に分からない場合に適しています

余りを残す方法がよく使われます
H (key)=key MOD p (p非常に明らかですが、p をどのように選択するかが重要な問題です。

使用例

たとえば、3 6 9 を格納する場合、p を 3 にすることはできません

because 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p は、m 以下の素数、または 20 未満の素因数を含まない合成数である必要があります。これにより、アドレスの重複 (競合) を減らすことができます。

たとえば、key = 7、39、18、 24、33、21 のとき、テーブル長 m を 9、p を 7 として、次のように格納します。

乱数法

H（key）=Random（ key)

キーワードのランダム関数値をハッシュアドレスとして取得します

ハッシュ関数の設計における考慮事項

1. ハッシュ アドレスの計算に必要な時間 (つまり、ハッシュ関数自体が複雑すぎないこと)
2 . キーワードの長さ
3. テーブルの長さ
4. キーワードの分布が均等かどうか、および従うべきルールがあるかどうか
5. ハッシュ関数は、上記の条件を満たしながら競合を最小限に抑えるように設計されています

3. ハッシュの競合

つまり、異なるキー値が同じアドレスを生成します。H (key1) = H (key2)
Forたとえば、上記の 3 6 9 を格納すると、p は 3 を
3 MOD 3 == 6 MOD 3 == 9 MOD 3
このとき、3、6、9 でハッシュ競合が発生しました

ハッシュ競合の解決策

ハッシュ関数がどれほど巧妙に設計されていても、特に動的ルックアップ テーブルの場合、ハッシュ競合を引き起こす特別なキーが常に存在します。

ハッシュ関数には、競合を解決するための次の一般的なメソッドがあります

1. オープン カスタマイズ メソッド

2. チェーン アドレス メソッド

3. パブリック オーバーフロー領域メソッド

競合するデータを保存するための特別なストレージ スペースを作成します。この方法は、データが少なく競合がある状況に適しています。

4. リハッシュ法

ハッシュ関数をいくつか用意し、最初のハッシュ関数で競合が発生した場合は、2 番目のハッシュ関数を使用します。 3 つ目...

オープン カスタマイズ方法とチェーン アドレス方法に注目

オープン カスタマイズ方法

最初に H (キー) ハッシュ関数があります

If H(key1)=H(keyi)

Then keyi storage location Hi=(H(key) di)MODmHi=(H(key) di)MODmm はテーブル Long

注

インクリメント di には次の特性 (完全性) が必要です。生成された Hi (アドレス) はすべて異なり、生成された s (m-1) Hi は次のとおりです。ハッシュ テーブル内のすべてのアドレスをカバーします

* 正方形検出中、テーブルの長さ m は 4j 3 の素数でなければなりません (正方形検出テーブルの長さは制限されています)

* ランダム 共通のものはありません検出時の m と di の間の係数 (di のランダムな検出には制限があります)

3 つのオープン アドレス指定方法の競合解決ソリューションの例

次のセットがあります。データ

19 01 23 14 55 68 11 86 37 は、テーブル長 11 の配列に格納されます。ここで、H (キー) = キー MOD 11

次に、上記に従います。 3 つの競合解決方法の場合、格納プロセスは次のとおりです。

(表の説明: データを前から後ろに挿入します。挿入位置がすでに占有されており、競合が発生した場合は、競合のために新しい行を開始します。アドレスが利用可能になるまでアドレスを計算します。後続の競合に備えて新しい行を開始し続けます。最終結果 先頭のデータを取得します (最も「占有している」データであるため))

線形検出と次にハッシュします

di=1、つまり競合後のストレージを取得します。競合後の位置で、まだ競合がある場合は後方に続行します。

二乗検出してからハッシュする

ハッシュにおけるランダム検出 (二重検出してからハッシュする)
競合後
H(key)'=(H(key) di)MOD m
この例では
H(key)=key MOD 11
di=key を採用しますMOD 10 1
結果は次のようになります:

チェーン アドレス メソッド

ハッシュの競合が発生した後、競合するデータを指すポインタを保存されたデータの後に追加します。
上の例では、チェーン アドレス メソッドは次のようになります。

4. ハッシュ テーブルの検索

検索プロセスはテーブルの作成プロセスと同じです。競合を処理するためにオープン アドレス指定方法が使用されます。検索プロセスは次のとおりです。

指定されたキーに対して、ハッシュ アドレス インデックス = H (キー) を計算します。

配列 arr の値が[index] が空の場合、検索は失敗します

配列 arr[index] == キーの場合、検索は成功します

それ以外の場合は、競合解決メソッドを使用して次のアドレスを見つけますarr[index] == key または arr[index] == null

どの関数であっても、負荷係数が大きいほど、平均検索長の場合、負荷率 α は小さいほど良いのでしょうか?いいえ、テーブル長 100 に 1 つのデータしか格納されないのと同様に、α は小さいですが、スペースの使用率は高くありません。これは時間とスペースのトレードオフです。通常、α=0.75が時間と空間の総合利用効率が最も高い状況と考えられます。

上の表は特に便利です。現在 10 個のデータがあり、チェーン アドレス方式を使用して競合を解決したいと考え、平均検索長

が必要な場合、1 α/2

が存在します。 α

つまり、 n/m

m>10/2

m>5 つまり、チェーンアドレス方式は平均検索長を にするために使用されます。

私のブログでは、以前にさまざまなツリーの平均検索長について説明しました。それらはすべてデータ n を格納する機能に基づいていますが、ハッシュ テーブルは異なります。つまり、データ n が増加すると、テーブルの長さ m を増加して、負荷係数を変更せずに ASL を変更しないようにすることができます。

そうすると、ハッシュ テーブルの構造は次のようになります:

5. ハッシュ テーブルの削除

はじめに チェーン アドレス方式では要素を直接削除できますが、オープン アドレス方式では要素を削除できません。前述の二重検出とハッシュを例に挙げます。要素 1 を削除してその位置を空白のままにすると、23 は見つかりません。正しいアプローチは、-1 など、存在しないデータを削除する前に挿入することです。

関連するその他の質問については、PHP 中国語 Web サイトをご覧ください: PHP 実践ビデオ チュートリアル

以上がデータ構造 ハッシュテーブル(ハッシュテーブル)とは何ですか?具体的にはどのような操作があるのでしょうか？の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。