ハッシュ探索

著者:杉浦

ハッシュ探索

 人間が本棚から特定本を探す時、どのような行動をとるでしょうか。
 慣れ親しんだ自宅の本棚ならここに入れてある、と一瞬で目当ての本の場所がわかると思います。図書館の様な場所なら辞書内を探す様にタイトルを追って大体の場所を行ったり来たりして探していくと思います。前者と後者の違いは題名と保管場所に密接な関係があるかないかの違いです。前者ならば題名を思い出した時に保管場所も共に思い出しているでしょう。後者ならば題名からこのあたりにあるだろうと推測を付けているでしょう。データ名がコンピュータがデータを保存している場所を示した場合、コンピュータも自宅の本棚から本を見つける様に一瞬で目当てのデータを探せるでしょう。ハッシュ探索は大体そのような方法です。
 コンピュータのデータ格納場所は番地、値で表せます。データ名もまた、値で表せます。データの格納番地をデータ名とした場合、データ名の場所にアクセスしにいけばそれで一発でデータを読み出せます。大体このような考えがハッシュ探索です。実際には、格納場所はもっと狭く、格納番地を読み出すためのコストもバカにならないので、データそのままでなく何らかの別のものをキー(格納番地)として扱います。それでも多くの場合で他のデータ構造より高速に特定のデータを読み出せます。
 多くの言語にはマップというデータ構造が備えられておりハッシュ探索に対応しています。先ほどのデータ名や格納番地足るキーと共にデータ値を登録していくデータ構造です。
追記:人間の頭が一瞬で目当てのデータを見つけられる主な仕組みはハッシュ探索の仕組みというより、頻繁に使われるデータや最近使用されたデータを上位(記憶の上層)に保管している仕組みです。

  • この記事いいね! (0)

著者について

杉浦 author