ハッシュ検索はなぜ速い

質問

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

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

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

回答No.6

queuerev2 · ベストアンサー

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

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

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

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

解説が比較的わかりやすそうで、何らかのプログラミング言語での実装のあるものを探してみました。
プログラム言語がわかれば言うことはないのですが、たとえわからなくても解説を読むだけでもけっこう理解できるのではないでしょうか。
１．　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系での実装も探したのですが見つかりませんでした）

お礼

回答ありがとうございました。

一つ前のお礼欄に書いてある内容を読んで、ようやく、なぜ速いか理解できました。

回答No.5

foomufoomu

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

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

お礼

回答ありがとうございます

分かってしまえば、おっしゃる通りですね。

ネット上から探して、私が一番分かりやすいものを見つけました。これ以外は、全く見つけることが出来ませんでした。

検索対象のデータを一定の規則にしたがってハッシュ値と呼ばれる整数に変換し、ハッシュ値を比較して検索を行なう方式。
文字列検索のように個々のデータが大きい場合、データ全体を比較しながら検索するよりも比較にかかるコストが節約でき、高速に検索できる。ただし、検索するデータの大きさが小さければ、ハッシュ値に変換する手間が増えるためにかえって効率が悪くなることもある。

計算機でデータ処理を行う際には，データのキーを表の形式に格納し，そこからあるキーを探してデータを取り出す，という作業が必要となる場面はよくあります．こういう作業では，「あるキーが表の中にあるかどうか調べる（探索といいます）のをすばやくやりたい」，というような要望があるかもしれません． ハッシュ法（hash method, hashing）は，こういう場合によく使われる手法です．キーをその大小によらず表上に散らばるように格納することから，このような名前がついています．
例えば，学籍番号の数字をキーとして一次元配列に格納することを考えましょう．ばらばらのキーを何も考えずに配列の先頭から順に格納してある場合，ある番号を探索するには，配列を先頭から順に調べていく（順探索あるいは逐次探索）しかないでしょう．
i table[i]
------------
0 901051 <-- 901334 ? (^o^ ここか？
1 901002 <-- 901334 ? (^_^ それともここか？
2 901359 <-- 901334 ? (-_- ないのんか？
3 901000 <-- 901334 ? (~_~ うー
4 900555 <-- 901334 ? (~o~ ほげー
5 901334 <-- 901334 ? (^_^)/ あった
順探索の場合，あらかじめキーの数を知ってれば表のサイズをそれに合わせておけばいいですから，後述のハッシュ法と違って記憶領域に無駄はありません．しかし一方で，探索にはかなり時間を要するかもしれません．
ハッシュ法では，探索をもっとうまいことできるようにデータの格納の仕方を工夫します．例えば，表のサイズを 10 にして，キーを格納する場所を「キーの値を 10 で割った余り」で計算してみます．つまり，901051 mod 10 は 1 なので table[1] に格納，901002 は table[2] へ…という調子です．
i table[i]
-----------
0 901000
1 901051
2 901002
3
4 901334 <-- 901334 ? (^_^)/ あった
5 900555
6
7 <-- 901777 ? (;_;) ないの
8
9 901359
このように表を作っておけば，901334を探索しろといわれたら， 901334 mod 10 は 4 やから table[4]にあるはずということで，一箇所だけ調べれば済みます．また，901777を探索しろといわれたら，table[7]を見て，そんなんない，ちうことが一発でわかります．というわけで，必要な表のサイズは多少大きくなりますが，探索に要する時間はずっと短くすることができます．

回答No.4

jjon-com

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

例えば，ある学校が学生番号として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

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

お礼

回答ありがとうございます。

>この場合は，氏名「ああああああああ」なら添字0，氏名「あああああああい」なら添字1，氏名「あああああああう」なら添字2，…のように対応づけを適当に定めればよいわけです。

これって普通のことですよね。
一般に言われている時間が掛かる配列の場合とこの場合は何が違うのでしょうか？

回答No.3

chie65536（@chie65535）

追記。

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

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

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

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

こういう決め方にして

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

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

・赤付箋グループ

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

・青付箋グループ

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

・白付箋グループ

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

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

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

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

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

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

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

が除外できます。

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

残った

「うあああああ」

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

お礼

回答ありがとうございます。
大変詳しく砕いて書いていただきありがとうございます。

こういう賢い仕組みも考えられているのですね。すごいです。

ところで、先ほどの回答のお礼欄にも書いておいたのですが、赤や青の付箋がどのページに貼られているのか、結局、1枚ずつ付箋の色を確認していたら、ページを1枚づつめくることと変わらないと思ってしますのですが。

回答No.2

chie65536（@chie65535）

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

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

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

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

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

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

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

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

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

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

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

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

お礼

回答ありがとうございます。

ここでいつも分からないのが、付箋を貼っても、その付箋が何色か１枚づつ調べていくと、１枚づつページをめくることと同じで、何も変わらないのではと思ってしまうのですが。

回答No.1

ok-kaneto

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

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

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

お礼

回答ありがとうございます。

ハッシュ検索だと、データ量が増えても検索回数が増えないのはなぜですか？