概要
キーワードkがあるとすると、その値はf(k)の格納場所に格納されます。このように、比較することなく、レコードをチェックするために直接取得することができます。f（k）はハッシュ関数であり、テーブルを構築するために、このアイデアによると、ハッシュテーブルです。
しかし、f（k）の計算中に、異なるkが同じ値を計算され、これはまた、ハッシュの競合として知られている、この問題を解決するために、また、競合に対処するための方法が必要です。
要約すると、ハッシュ関数f（k）とキーワードのセットを連続したアドレスの有限セットにマッピングする競合を処理する方法によると、アドレスセットのキーワードは、テーブル内の格納場所のレコードとして "のような"、このようなテーブルは、ハッシュテーブルとして知られている、このマッピングプロセスは、ハッシュテーブルまたはハッシュとして知られている、結果の格納場所は、ハッシュアドレスとして知られています。
テキストが読めない？ハッシュ計算の流れは以下の図をご覧ください。
一般的なメソッド
- 直接アドレス指定」：キーワードまたはキーワードの一次関数をハッシュアドレスとして指定します。
H(key)=keyまたはH = a·key + bすなわちa と b は定数です。H（キー）にすでに値がある場合は、H（キー）にこれ以上の値が存在しないまで、次に移動し、それを入れてください。 例：人口の統計テーブルの年齢の1〜100年、キーワードの年齢は、ハッシュ関数は、キーワード自体を取ることです。次の表に示すように。
| 年齢 | 1 | 2 | 3 | ... | 20 | 21 | ... | 002 |
| 人数 | 002 | 991 | 891 | ... | 081 | 971 | ... | 1 |
したがって、25歳の人が何人いるかを知りたければ、表の項目25を見ればよいのです。 アドレスの集合と同じサイズのキーワードの集合を直接アドレス指定するためです。したがって、異なるキーワード間で衝突することはありませんが、実際にはこのハッシュ関数が使えるケースはほとんどありません。
- 数値解析」：「キーワードがrを底とする数値」であり、「ハッシュテーブルの中でキーワードが出現する可能性があらかじめわかっている」と仮定すると、「キーワードの桁数をとってハッシュアドレスを形成することができる」。
たとえば、生年月日の従業員のグループは、それが最初の数桁の生年月日がほとんど同じであることが判明した、この場合、競合の可能性が非常に大きくなりますが、最後の数ヶ月は、月と大きな違いの数の特定の日付の生年月日の後、後者の数は、ハッシュアドレスを形成する場合、競合の可能性が大幅に低くなります。したがって、デジタル分析法は、可能な限り、これらのデータの使用は、競合のハッシュアドレスの低い確率を構築するために、番号のパターンを見つけることです。
- 真ん中のメソッドを平方：あなたはキーワードのどのビットがより均等に分布している決定することはできませんときは、まず`キーワードの平方値`を見つけることができますし、ハッシュアドレス`としていくつかのビットの平方値の真ん中`を取る必要性によると。これは次のためです：相関のすべてのビットの中央のビットとキーワードの2乗の後、異なるキーワードは、異なるハッシュアドレスを生成する確率が高くなります。
アルファベットの内部コードは、そのアルファベットの位置を表す数字です。例えば、Kの内部コードは11、Eの内部コードは05、Yの内部コードは25、Aの内部コードは01、Bの内部コードは02です。 これにより、キーワード "KEYA "の内部コードは11052501となり、同様にキーワード "KYAB"、"AKEY"、"BKEY "の内部コードを得ることができます。キーワードを2乗した後、7ビット目から9ビット目をキーワードハッシュアドレスとして取り出します。
- 折りたたみ」：キーワードを同じビット数の部分に分割し、最後の部分は異なっていてもよく、これらの部分の合計をハッシュアドレスとして使用します。重ね合わせの数は、シフト重ね合わせと境界間重ね合わせの2つの方法があります。シフト重ね合わせは、アライメントの各部分の最下位ビットの分割であり、その後、追加されます。重ね合わせの境界の間に折り返しの境界に沿って分割の一方の端から他方の端までであり、その後、追加するために整列。
例えば：各中国と西洋の書籍は、国際標準図書番号を持って、それは10ビットの10進数で、ハッシュテーブルを構築するためのキーワードとして使用する場合は、書籍の10,000種類未満のコレクションは、4桁のハッシュ関数を構築するために折り畳み方式を使用することができます。フォールディング法では、重ね合わせの数をシフト重ね合わせと境界間重ね合わせの2つの方法で行うことができます。シフト重ね合わせは、最下位ビットの並びの各部分を分割して加算する方法、境界間重ね合わせは、パーティション境界に沿って端から端まで折り返して整列して加算する方法です。図に示すISBN 0-442-20586-4ハッシュアドレスのようなもの。
乱数法：ランダム関数を選択し、ハッシュアドレスとしてキーのランダムな値を取る、すなわち、H（キー）=ランダム（キー）ここでランダムは、通常、機会のキーの長さが等しくないために使用されるランダム関数です。
余りで割る：キーワードをハッシュテーブルの長さm以下の数pで割った余りをハッシュアドレスとします。
H(key) = key MOD p,p<=mつまり。pの選択は重要です。pの選択は非常に重要で、通常は素数またはmを取る、pがうまく選択されていない場合は、同義語を生成するのは簡単です。
コンフリクトの処理
- オープンアドレス法`：Hi= + di) MOD m,i=1,2,......,k(k<=m-1),ここでH(key)はハッシュ関数、mはハッシュテーブルの長さ、diはインクリメンタルシーケンスで、以下の3つの方法があります。
- di=1,2,3,...,m-1を線形検出ハッシュと呼びます。+ di=1^2,-1^2,2^2,-2^2,(3)^2,...,±は2次検出ハッシュと呼ばれます。+ di = 擬似乱数列、擬似乱数検出再ハッシュと呼ばれます。
再ハッシュ法：Hi=RHi（キー）,i=1,2,...,k RHiは異なるハッシュ関数である、すなわち、同義語では、競合が発生しなくなるまで、別のハッシュ関数のアドレスを計算するときにアドレスの競合を生成し、このメソッドは、"集約 "を生成することは容易ではありませんが、計算時間が長くなります。
チェインアドレス法 HashMapの使用法 キーワードが同義語であるレコードをすべて同じ線形チェインテーブルに格納。ハッシュ関数が生成するハッシュアドレスが区間[0,m -1 ]にあると仮定して、ポインタ型ベクトルChainHash[m]を設定し、その各構成要素の初期状態をヌルポインタとします。ハッシュ・アドレスiを持つレコードは、ヘッド・ポインタChainHash[i]を持つチェーン・テーブルに挿入されます。挿入は、テーブルの先頭または末尾に行うことができます。また、同じ線形チェーン内の同義語をキーワード順に保つために、途中に行うこともできます。
共通のオーバーフロー領域を確立することも、競合に対処するための方法は、[ 0、m - 1 ]のドメインの値のハッシュ関数と仮定し、基本テーブルのベクトルHashTable [ 0...m - 1 ]を設定し、各コンポーネントは、レコードを格納し、オーバーフローテーブルのベクトルOverTable [0...v]を設定します。基本テーブルのすべてのキーワードとキーワードは、ハッシュアドレスによってそれらのハッシュ関数に関係なく、同義レコードは、競合が発生すると、オーバーフローテーブルに記入されるものです。
