データ構造内のハッシュ テーブル (ハッシュ テーブル) の従来の競合処理

ハッシュとは、レコードの保存場所とそのキーワードの間に一定の対応関係 f を確立し、各キーワードのキーが保存場所 f (キー) に対応し、キーワードと保存場所の相互関係を確立するものです。 . 対応関係、この関係fをハッシュ関数(ハッシュ関数)といいます。この記事の編集者は主にハッシュ関数の競合処理の問題について話します。

検索プロセス中、キー コードの比較の数は競合の数によって異なります。競合が少ないほど、検索の精度は高くなります。効率が低下すると、競合が多くなり、検索効率が低くなります。したがって、競合の数に影響を与える要因は、検索効率に影響を与える要因となります。競合の数に影響を与える要素は次の 3 つです:

1. ハッシュ関数が一様であるかどうか;

2. 競合の処理方法;

3.ハッシュ テーブルの充填係数。

ハッシュ テーブルの充填率は次のように定義されます: α = テーブルに充填された要素の数 / ハッシュ テーブルの長さ

α は充填度の符号率です。ハッシュテーブルの。テーブルの長さは固定値であるため、αは「テーブルに埋められる要素の数」に比例するため、αが大きいほどテーブルに埋められる要素が多くなり、競合する可能性が高くなります。 α、テーブルに入力される要素が少ないほど、競合が発生する可能性は低くなります。

実際、ハッシュ テーブルの平均検索長は充填係数 α の関数ですが、競合を処理する方法が異なれば機能も異なります。

ハッシュの競合を解決する方法には、一般に次のようなものがあります。

NO.1 オープン アドレス指定方法

いわゆるオープン アドレス指定方法とは、競合が発生すると、ハッシュの競合を解決する方法を意味します。次の空のアドレス: ハッシュ テーブルが十分に大きい限り、空のハッシュ アドレスは常に見つかり、レコードが保存されます。

式: f(key)=(f(key) di)%m(di=1,2,3….m-1)

たとえば、キーワードセットは { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}、テーブルの長さは 12 です。ハッシュ関数 f(key) = key mod 12.

最初の 5 つの数値 {12, 67, 56, 16, 25} を計算すると、それらはすべて競合のないハッシュ アドレスであり、直接保存されます。キー = 37 を計算すると、f(37) であることがわかります。 = 1. この時点では、25 の場所と競合します。したがって、上記の式 f(37) = (f(37) 1) mod 12 =2, を適用します。したがって、37 はインデックス 2 の場所に格納されます。次の 22、29、15、および 47 には競合はなく、正常にデポジットされます。 48 で f(48) = 0 を計算しますが、これは 12 の 0 の位置と競合します。それは問題ではありません。f(48) = (f(48) 1) mod 12 = 1 となりますが、これは位置と競合します。 25の。したがって、 f(48) = (f(48) 2) mod 12 = 2 ですが、まだ競合が存在します... f(48) = (f(48) 6) mod 12 = 6 になるまで空きはありません。以下の表にあります。

#シリアル番号0123 45678910 11 キーワード122556

NO.2 再ハッシュ方法

ハッシュテーブルについては、あらかじめ複数のハッシュ関数を用意しておくことも可能です。

式: fi(key)=RHi(key)(i=1,2,3...,k)

ここで RHi は別のハッシュ関数であり、除算して残すことができます。残りの部分は、折り曲げ、四角形、センタリングがすべて使用されます。ハッシュ アドレスの競合が発生するたびに、別のハッシュ関数が計算に使用されます。

この方法ではキーワードの集計を防ぐことができますが、その分計算時間も長くなります。

NO.3 連鎖アドレス方式（ジッパー方式）

キーワードが同義語であるすべてのレコードを単一リンクリストに格納します。このテーブルを同義語サブリストと呼びます。すべての同義語サブリストの前にハッシュ テーブルに格納されます。キーワードセット {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34} については、前と同じ 12 を剰余として使用し、除算と剰余メソッドを実行して構造を取得します。下に。

NO.4 パブリック オーバーフロー エリアを確立する

この方法は、仕事中に新しいアドレスを見つけて、パブリック オーバーフロー エリアを作成する方法です。競合するすべてのキーワードの場合、ストレージのオーバーフロー領域。

前の例に関する限り、前のキーワードの位置と競合する 3 つのキーワード 37、48、および 34 があるため、これらをオーバーフロー テーブルに保存します。以下に示すように。

検索時は、与えられた値のハッシュアドレスをハッシュ関数で計算した後、まず基本テーブルの対応する位置と比較し、等しい場合は、検索成功。等しくない場合は、オーバーフロー テーブルで順次検索を実行します。基本テーブルと比較して競合するデータが非常に少ない場合でも、共通オーバーフロー領域の構造は検索パフォーマンスが非常に高くなります。

[おすすめコース：C関連コース]

# #16

##67

以上がデータ構造内のハッシュ テーブル (ハッシュ テーブル) の従来の競合処理の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。