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

概要

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

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

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

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

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

(2018.10.29更新)