【ハッシュ法】意味・特徴・ハッシュ関数の計算

ハッシュ法の意味・特徴・関数について解説します。

[latexpage]

スポンサーリンク

【ハッシュ法とは】データ探索方法

ハッシュ法とは、データ探索方法の1つです。
データの探索キーの値からデータの格納位置をハッシュ関数を用いて直接計算します。
表では、レコードのキー値とハッシュ関数を用いて格納アドレスを求めることでデータにアクセスします。

主な特徴
1 探索回数の少ないデータ探索の場合、線形探索・2分探索より探索時間が短い(メリット)
2 連続したデータ探索の場合、探索時間が長くなる(デメリット)
3 線形探索法や2分探索法とは異なり、常に一定の時間で目的のデータを探索することが可能
4 異なるキー値から同じ格納場所が計算されることがある(本来格納されるべき所に格納できない事態が発生)
スポンサーリンク

【ハッシュ関数とは】衝突発見困難性、原像計算困難性、第二原像計算困難性

ハッシュ関数は、入力されたデータをもとに固定長の文字列(ハッシュ値)に変換する関数です。

SHA-256(Secure Hash Algorithm 256)が出力するハッシュ値は256ビットなので、入力データの長さにかかわらず得られるハッシュ値は常に256ビットになります。
衝突が発生する確率は$\frac{1}{2^{256}}$なので、平均で$2^{128}$回の試行で同じハッシュ値を出力する異なる入力を発見できます。

特性 概要
衝突発見困難性(強衝突耐性) ハッシュ値が一致する2つのメッセージを探索することが困難であること。
原像計算困難性 ハッシュ値hash(M)から元のメッセーMを探すことが困難であること、
第二原像計算困難性(弱衝突耐性 既知のメッセージM1に対するハッシュ値が与えられた時、ハッシュ値が一致する、hash(M1)=hash(M2)となるようなメッセージM2を探索することが困難であること。
【情報処理入門】用語解説・資格試験対策まとめ
情報処理分野の用語・原理・資格試験対策について解説します。

コメント