ハッシュ検索はなぜ速い

Question

ハッシュ検索はなぜ速いのか、素人にも分かりやすく教えてください。

何度も照合しなくてよいから、直接探すことが出来るから、とかいうコメントは見かけるのですが、これが具体的にどういうことか教えてください。

よろしくお願いいたします。

queuerev2 · Accepted Answer

ハッシュを用いた連想配列の最も基本的な部分の動作ですが、

データ書き込みは・・・
１．ハッシュ関数を用いてデータ（またはデータとペアになっているキー）からハッシュ値（Ｎとする）を算出する
２．ハッシュ表のＮ番目にデータを書き込む

データ読み出しは・・・
１．ハッシュ関数を用いてデータ（またはキー）からハッシュ値（Ｎとする）を算出する
２．ハッシュ表のＮ番目からデータを読み出す

というものです。
基本的にハッシュ値は整数でハッシュ表は配列です。
つまり、１度のデータの書き込みや読み出しで、値の算出と配列の書き込みまたは読み出しを１回だけ行えばいいので、探索を行うようなデータ構造より高速だということです。
ただし、異なるデータ（キー）でも同じハッシュ値になることがあるので、これに対応する必要があり、速度低下の原因となります。
（なお、データあるいはデータとペアになっているキーが狭い範囲の０以上の整数で重複がなければ、通常の配列を使えば済むので連想配列は不要）

解説が比較的わかりやすそうで、何らかのプログラミング言語での実装のあるものを探してみました。
プログラム言語がわかれば言うことはないのですが、たとえわからなくても解説を読むだけでもけっこう理解できるのではないでしょうか。
１．　http://prograpark.ninja-web.net/HSP/lab/AsArray1.html
（HSPでの実装。読みやすくわかりやすい。未完成だが原理を知るには十分）
２，　http://www.geocities.jp/m_hiroi/xyzzy_lisp/abclisp09.html#yori14
（Common Lispでの実装。線形探索との速度比較あり。このサイトには他にC, Ruby, Python, Scheme, OCamlでの実装例あり）
（VB系での実装も探したのですが見つかりませんでした）

foomufoomu · Answer

No.1 回答の補足になりますが、
ハッシュ法の手順は、
データを覚えるとき、検索キーをある規則（たとえば、文字列なら、全文字のアスキーコードを掛け算し、下３けたをとりだす(記憶場所が1000個ある場合)、など）によって数値化し、その数値の場所にデータを記録します。
データを取り出すときは、検索キーをもとに、前と同じ方法で数値計算し、その場所のデータを読みます。
ですから、1つずつ探すのでなく、いっぱつで目的データを取り出すことができるのです。

ただし、この方法では、偶然、異なる検索キーが同じ場所に割り付けられることがあります。その場合は、2番目の規則（たとえば、最初の場所から３だけ後ろ）によって、2番目の場所を計算します。
とうぜん衝突が多いと検索が遅くなるのですが、この衝突は、ハッシュ記憶域の70%が埋まった時点で、1/2程度の確率で発生する（と言われている）ので、意外と衝突による検索速度の低下はありません。

jjon-com · Answer

付箋の色を持ち出さなくても，数値の方が説明しやすいように思います。

例えば，ある学校が学生番号として7桁の10進数を採用しているとする。
その取り得る範囲は0000000～9999999の全1000万パターンです。
検索キーとして学生番号を指定してその学生のデータを検索するもっとも高速な方法は，
「学生番号を添字とする，要素数1000万個の一次元配列を用いること」です。
この場合の探索回数は「１回」です。
学生番号を添字として，該当要素に直接アクセスする，で終わり。超高速です。

この発想は，学生番号の場合だけしか使えないものではありません。
例えば，氏名を検索キーとしてその学生のデータを検索したいというニーズがあるとする。
この場合は，氏名「ああああああああ」なら添字0，氏名「あああああああい」なら添字1，氏名「あああああああう」なら添字2，…のように対応づけを適当に定めればよいわけです。
要素数が万になるか億になるかわかりませんが，氏名に対応する添字を求めて，該当要素に直接アクセスする，で終わり。やはり探索回数は「１回」です。

----------------
しかし上記には問題があります。
配列がやたらと長いくせに，使われていない要素がとても多いことです。
その学校は開校以来，通算しても学生数は1万人を下回る程度かもしれない。
氏名に対応する一次元配列だって，実際に氏名として登場する文字列は全パターン中のほんのわずかでしょう。

このように「元の検索キーとしてあり得る値の全パターンは広いが，実際のデータ数はずっと少ない」場合に，ハッシュは有効に働きます。

具体例としては，学生データを格納する一次元配列の大きさを例えば10,000件とする。
添字の範囲は0～9999です。
そして，7桁の10進数を入力として与えたとき，それを10,000で割った余りを求める「ハッシュ関数」を用意するわけです。出力されるハッシュ値の範囲は0～9999ですから，これを添字として用います。

氏名の場合も同様で，「ああああああああ」という文字列を入力として与えたら，それをビット列と見なそうがどう組み替えようが内部処理はどうでもかまわないので，0～9999のハッシュ値が出力されるようなハッシュ関数を用意すればよいわけです。

----------------
探索キーと１対１に対応する添字を用いて，要素数が数千万・数億の一次元配列を用意すれば，探索は１回で済むけれど，ムダがきわめて多い。
ハッシュはそこに「探索キーに計算を施すことによって格納範囲を狭める」という技法を適用しました。それによって新たに生じる問題が，異なる探索キーから同一のハッシュ値が生成されてしまう「シノニム」の存在です。
http://eow.alc.co.jp/search?q=synonym

シノニムは，ハッシュ探索においては避けられません。入力されたキー値をバラバラごた混ぜにして如何にシノニムが生じにくいハッシュ関数を見つけ出すか，シノニムが生じたときの格納方法をどうするかを考えておくことになります。
http://eow.alc.co.jp/search?q=hash

いずれにしろ，シノニムが発生する確率が十分に小さいのであれば，ハッシュ探索による探索回数は「１回」ですから，超高速な探索方法と言えるでしょう。

chie65535 · Answer

追記。

高速化には「付箋の色の決め方」も重要です。

決め方は、以下のようにします。

・元の語句の先頭が同じで、末尾だけが違う場合、なるべく違う色の付箋にする。

・元の語句の先頭が異なる物同士を、なるべく同じ色の付箋にする。

こういう決め方にして

「ああああああああ」
「あああああああい」
「ああああああ」
「いああああああああ」
「いあああああああお」
「いあああああああ」
「うああああ」
「うあああああ」
「うああああお」
「えあああああああ」
「えああああああ」
「えああああああえ」

と言う１２個の単語を、赤、青、白の３つのグループに分けると

・赤付箋グループ

「ああああああああ」
「いああああああああ」
「うああああ」
「えあああああああ」

・青付箋グループ

「あああああああい」
「いあああああああお」
「うあああああ」
「えああああああ」

・白付箋グループ

「ああああああ」
「いあああああああ」
「うああああお」
「えああああああえ」

のようにグループ分けされます。

「うあああああ」を探しに行く場合、「付箋の色を決める手順書」に従って「青付箋グループ」と言うのを求めます。

青付箋グループのみを見ると

「あああああああい」
「いあああああああお」
「うあああああ」
「えああああああ」

が居ますから、最初の１文字目だけを比べただけで

「あああああああい」
「いあああああああお」
「えああああああ」

が除外できます。

「先頭が似ている語句は同じグループにならない」と言う規則のおかげで、文字列を全部調べる必要が無くなって検索が早くなります。

残った

「うあああああ」

は、文字列が完全一致するので「ここにあった」と言うのが判ります。

chie65535 · Answer

ハッシュ検索は「分厚い本に、色々な色が付いた付箋で目印を付けるようなもの」なのです。

単純検索（線形検索）では「１ページ目から順に１ページづつくまなく探していく」ので、本の最後の方にあったら「ほぼ全ページを見る」事になりますし、本に載ってなかった場合は最後のページを探し終わるまで、載ってない事が判明しません。

ハッシュ検索では、まず、探す対象を元に「付箋の色」を決めます。

付箋の色の決め方は「決める方法が書かれた手順書」の通りに決めます。

例えば「この語句なら、赤い付箋」と言うように。

付箋の色が赤だと判ったら、赤色の付箋が付いているページだけを見ます。

最初に開いた赤い付箋のページに無かったら、同じ赤色の付箋が付いた別のページを見に行きます。

もし、赤い付箋が付いたページだけをすべて探しても見付からないなら「本に載ってない」と判ります。

３０００ページの本であっても、赤い付箋が付いているのが３０ページしか無ければ、最大でも３０ページ分だけ調べれば、載ってるか載ってないか、載っているとしたら何ページ目に載っているか、すぐに判ります。

この時「付箋の色」が「ハッシュキー」と呼ばれる物に相当します。

そして「語句から付箋の色を決める方法が書かれた手引き書」が「ハッシュ関数」に相当します。

また「貼られている付箋の集まり」が「ハッシュテーブル」に相当します。

ok-kaneto · Answer

ハッシュ探索以前だと、線形探索という手法がありました。

これは、結局は全部を順番に探す方法です。10個のデータがあれば最大10回の探索ですみますが、1000個あれば最大1000回の探索をする必要があります。

ハッシュ探索だと、ある一定の手順により元データを保存する場所が決まっているため、データ量が増えたとしても探索の回数は増えません。

ハッシュ検索はなぜ速い

ハッシュを用いた連想配列の最も基本的な部分の動作ですが、

No.1 回答の補足になりますが、

付箋の色を持ち出さなくても，数値の方が説明しやすいように思います。

追記。

ハッシュ検索は「分厚い本に、色々な色が付いた付箋で目印を付けるようなもの」なのです。

ハッシュ探索以前だと、線形探索という手法がありました。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング