読み方 : ハッシュほう

ハッシュ法【hashing method】ハッシュ探索/ハッシュ表探索

概要

ハッシュ法とは、データ探索アルゴリズムの一つで、対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式。対象とするデータが長い場合に処理を高速化することができる。
ハッシュ法のイメージ画像

ハッシュ値はハッシュ関数(hash function)によって算出される固定長のデータで、任意の長さのデータから算出することができ、同じデータからは必ず同じハッシュ値が得られる。ハッシュ法ではまず各データのハッシュ値を算出し、探索対象のデータもハッシュ値に変換して、ハッシュ値同士で比較を行い探索する。

長い文字列データなど、毎回データ全体を比較すると比較処理自体に長い時間がかかるような場合に、短いハッシュ値で代用することにより比較処理を高速化することができる。また、広い値域を持つデータを短い配列などに格納して、高速に書き込みや読み出しを行うことができる。

ハッシュ値の算出は他のデータの存在を考慮せず行われるため、複数の異なるデータから同じハッシュ値が算出される衝突(collision)が起きることがある。同じハッシュ値を持つデータ群をシノニム(synonym)という。

シノニムを処理する方法としては、空いているハッシュ値にデータを振り分けて衝突を解消する「オープンアドレス法」や、同じハッシュ値を持つデータを線形リストとして保存する「直接連鎖法」などがある。

資格試験などの「ハッシュ法」出題履歴

【令5修7/平28修6/平26修12/平25修6/平22修6】 ハッシュ法の説明として,適切なものはどれか。
【令4修6/令1秋/平30修7/平29修1/平26修7/平25春/平22秋】 10進法で5桁の数 a 1 a 2 a 3 a 4 a 5 を,ハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a 1 +a 2 +a 3 +a 4 +a 5 ,13) とし,求めたハッシュ値に対応する位置の配列要素に格納する場合,54321 は配列のどの位置に入るか。
【令3修12/平29修7/平28修1/平24秋】 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。
【令3修7】 探索表の構成法を例とともに a〜c に示す。最も適した探索手法の組合せはどれか。ここで,探索表のコードの空欄は表の空きを示す。
【令3修1/令1修6/平30修1/平27修12/平25秋/平23秋】 次の規則に従って配列の要素 A[0],A[1],…,A[9] に正の整数kを格納する。kとして 16,43,73,24,85 を順に格納したとき,85が格納される場所はどこか。
【令2修6/平31春】 データ検索時に使用される,理想的なハッシュ法の説明として,適切なものはどれか。
【平30春/平27修7/平25修1】 表探索におけるハッシュ法の特徴はどれか。
【平26秋/平24修6/平21春】 0000~4999 のアドレスをもつハッシュ表があり,レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。
【平22春】 ハッシュ表探索において,同一のハッシュ値となる確率が最も低くなるのは,ハッシュ値がどの分布で近似されるときか。
この記事の著者 : (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。