今回は「明解 Javaによるアルゴリズムとデータ構造」を参照します。 この本に掲載されているサンプルプログラムは著者の後援会のサイトからダウンロードできますが、 文字コードが Shift JIS なため、UTF-8 に変換したものを以下に置いておきます。
線形探索や2分探索とは考え方の違うデータのアクセス方法としてハッシュ法があります。 上手に利用すれば、データに高速にアクセスすることが可能です。
ハッシュ法では、データを格納する場所がかち合う「衝突」という現象がおきます。 それを扱う方法に、チェイン法とオープンアドレス法があります。 Java の HashMap などの実装はチェイン法です。