連想配列やKVSのキーはhashだから検索が早い、項目が多くなっても早い、の理由を教えて下さい。

hashということは固定長になるからアドレスが単純な掛け算で求められるから早いのでしょうか? 項目が増えても早い理由は何でしょうか?

MySQLのmemoryエンジンでも検索が早いというのは、ディスクでなくmemoryであるという以外におそらく似たような理由かと思います。そのあたりもわかれば教えてください。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/06/25 01:08:36
  • 終了:2012/07/02 01:10:02

回答(2件)

id:Mook No.1

Mook回答回数1312ベストアンサー獲得回数3912012/06/25 02:18:36

ポイント50pt

この手の話は一から説明を書くよりも、解説されたページを探した方が体系だった説明があると思いますが、
ハッシュ関数
ハッシュ法

概要を書けば、
単純に配列を考えた場合、そこに任意に登録した単語を検索するには平均 単語数/2 の検索処理が発生します(数に比例)。

ハッシュではハッシュ関数(データからインデックスを計算する関数)によって格納位置を配列内になるべく均等になるようにして、そこにたどり着くまでの回数をなるべく少なくなるように設計します(されているはず)。
ハッシュ関数の結果が同じになれば、そこからは逐次検索ですが、それでも全体に対する検索に比べれば、はるかに少ない検索コストで済みます。
極端な例として、完全ハッシュ関数が実装できるケースでは一回の検索で済むわけです。

連想配列では、ハッシュ以外にも平衡2分探索木などによる実装もあるようです。
いずれも、目的の値までにいかに少ない検索回数で到達するかという工夫です。

データベースも基本的には同じ話ですが、興味があればこのあたりを読んでみてはどうでしょうか。
基礎から理解するデータベースのしくみ(7) データの格納方法を知ろう(2)

id:mash76

wikipediaわかりやすいですね。ありがとうございます。

2012/06/25 03:11:21
id:windofjuly No.2

うぃんど回答回数2625ベストアンサー獲得回数11492012/06/25 02:44:32

ポイント50pt

(1)ハッシュは言うなれば背番号制。
データを保存する時に、
ハッシュ関数で背番号を生成して保存しておく。
(当然ながら保存処理は平文よりも長くなる)

(2)早い理由はフルネームではなく背番号による検索だから。
データを検索する時には、
まず検索対象をハッシュ関数で背番号にして、
その背番号でデータの存在を探す。
(元が大きなデータでも、背番号の比較で済むため、
 検索時間は短くて済む)

(3)氏名、年齢、身長、体重・・・項目が増えても背番号は1つ。
1件ごとに番号を生成して付けるため、
文字数や項目の数が増えても検索速度は変わらない。
(もちろん、ハッシュを計算する時間は長くなるけれど、
 それは登録時の1回と、検索開始時点の1回だけで、
 検索作業は背番号で済むので早い)

(4)複雑な条件付き検索は苦手です。
背番号51を探せと命じてイチローと答えさせるのは非常に早い。
だがしかし、背番号51から61までを出力しろと命じると非常に遅い。
(背番号をつけただけで、並び順までは管理していないため、
 データの末尾に達するまで比較検討することになったりするのです)

(5)すなわち、
単一の値を探し出すことを優先する連想配列などであれば、
ハッシュは非常に有効な手段となるけれど、
複雑な条件設定になるデータベースのテーブルでは、
B-treeが多様されるというようなことになります。
(データベースのテーブルでも単一の値を探すことに特化できる場合は、
 ハッシュを選ぶ場合もあります)

(その他)MySQL5.xのmemoryストレージエンジンはメモリ上にあるから早いのです。
4.x時代はヒープでしたが、
現在はディスクに保管するテーブルに近い機能を持っていて、
ハッシュとB-treeを必要に応じて使い分けてくれます。

id:mash76

ズバリ、な感じでありがとうございます!!

2012/06/25 03:11:17

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません