ハッシュ関数とハッシュテーブル

ハッシュは、ハッシュ関数と呼ばれる数学関数を使用して、テキストまたは数値のリストから値を生成するプロセスです。数値の数値または英数字のキーを使用するハッシュ関数は多数あります。さまざまなハッシュ関数を以下に示します。

ハッシュ関数

以下はハッシュ関数の一部です-

除算方法

これは、ハッシュ関数を作成する最も簡単な方法です。ハッシュ関数は次のように記述できます-

h(k) = k mod n

ここで、h（k）は、キー値kをハッシュテーブルnのサイズで除算して得られるハッシュ値です。キーがより均一に分散されるようにするため、nは素数であることが最善です。

除算法の例は次のとおりです-

k=1276
n=10
h(1276) = 1276 mod 10
= 6

得られたハッシュ値は6です

分割メソッドIDの欠点は、連続するキーがハッシュテーブル内の連続するハッシュ値にマップされることです。これにより、パフォーマンスが低下します。

掛け算の方法

乗算法に使用されるハッシュ関数は-

h(k) = floor( n( kA mod 1 ) )

ここで、kはキーであり、Aは0から1までの任意の定数値にすることができます。kとAの両方が乗算され、それらの小数部分が分離されます。次に、これにnを掛けて、ハッシュ値を取得します。

掛け算の例は次のとおりです-

k=123
n=100
A=0.618033
h(123) = 100 (123 * 0.618033 mod 1)
= 100 (76.018059 mod 1)
= 100 (0.018059)
= 1

得られたハッシュ値は1です

乗算法の利点は、Aの任意の値で機能できることですが、一部の値は他の値よりも優れていると考えられています。

ミッドスクエア法

ミッドスクエア法は非常に優れたハッシュ関数です。これには、キーの値を2乗してから、ハッシュ値として中央のr桁を抽出することが含まれます。 rの値は、ハッシュテーブルのサイズに応じて決定できます。

ミッドスクエア法の例は次のとおりです-

ハッシュテーブルに100個のメモリ位置があるとします。したがって、 r =2 キーをメモリ位置にマップするには2桁の数字が必要なためです。

k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

ハッシュテーブル

ハッシュテーブルは、キーを値にマップするデータ構造です。ハッシュ関数を使用してデータキーのインデックスを計算し、キーはインデックスに保存されます。

ハッシュテーブルの例は次のとおりです-

ハッシュテーブルに格納する必要のあるキーシーケンスは-

35 50 11 79 76 85

使用されるハッシュ関数h（k）は次のとおりです。

h(k) = k mod 10

線形プロービングを使用して、値はハッシュテーブルに-