ハッシュ法 【hashing method】 ハッシュ探索 / ハッシュ表探索
概要
ハッシュ法(hashing method)とは、データ探索アルゴリズムの一つで、対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式。対象とするデータが長い場合に処理を高速化することができる。ハッシュ値はハッシュ関数(hash function)によって算出される固定長のデータで、任意の長さのデータから算出することができ、同じデータからは必ず同じハッシュ値が得られる。ハッシュ法ではまず各データのハッシュ値を算出し、探索対象のデータもハッシュ値に変換して、ハッシュ値同士で比較を行い探索する。
長い文字列データなど、毎回データ全体を比較すると比較処理自体に長い時間がかかるような場合に、短いハッシュ値で代用することにより比較処理を高速化することができる。また、広い値域を持つデータを短い配列などに格納して、高速に書き込みや読み出しを行うことができる。
ハッシュ値の算出は他のデータの存在を考慮せず行われるため、複数の異なるデータから同じハッシュ値が算出される衝突(collision)が起きることがある。同じハッシュ値を持つデータ群をシノニム(synonym)という。
シノニムを処理する方法としては、空いているハッシュ値にデータを振り分けて衝突を解消する「オープンアドレス法」や、同じハッシュ値を持つデータを線形リストとして保存する「直接連鎖法」などがある。
(2018.10.29更新)
アルゴリズムの用語一覧
その他の関連用語
試験出題履歴
基本情報技術者試験 : 【令5修7 問15】 【令4修6 問8】 【令3修12 問5】 【令3修7 問9】 【令3修1 問9】 【令2修6 問18】 【令1秋 問10】 【令1修6 問6】 【平31春 問18】 【平30修7 問6】 【平30春 問7】 【平30修1 問6】 【平29修7 問4】 【平29修1 問7】 【平28修6 問19】 【平28修1 問4】 【平27修12 問7】 【平27修7 問6】 【平26修12 問20】 【平26秋 問2】 【平26修7 問7】 【平25秋 問7】 【平25修6 問26】 【平25春 問7】 【平25修1 問6】 【平24秋 問3】 【平24修6 問2】 【平23秋 問6】 【平22秋 問7】 【平22修6 問24】 【平22春 問6】 【平21春 問2】