連想配列やKVSのキーはhashだから検索が早い、項目が多くなっても早い、の理由を教えて下さい。
hashということは固定長になるからアドレスが単純な掛け算で求められるから早いのでしょうか？ 項目が増えても早い理由は何でしょうか？
MySQLのmemoryエンジンでも検索が早いというのは、ディスクでなくmemoryであるという以外におそらく似たような理由かと思います。そのあたりもわかれば教えてください。
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。
ログインして回答する
みんなの回答
-
Mook
満足50pt
この手の話は一から説明を書くよりも、解説されたページを探した方が体系だった説明があると思いますが、
ハッシュ関数
ハッシュ法
概要を書けば、
単純に配列を考えた場合、そこに任意に登録した単語を検索するには平均 単語数/2 の検索処理が発生します（数に比例）。
ハッシュではハッシュ関数（データからインデックスを計算する関数）によって格納位置を配列内になるべく均等になるようにして、そこにたどり着くまでの回数をなるべく少なくなるように設計します（されているはず）。
ハッシュ関数の結果が同じになれば、そこからは逐次検索ですが、それでも全体に対する検索に比べれば、はるかに少ない検索コストで済みます。
極端な例として、完全ハッシュ関数が実装できるケースでは一回の検索で済むわけです。
連想配列では、ハッシュ以外にも平衡2分探索木などによる実装もあるようです。
いずれも、目的の値までにいかに少ない検索回数で到達するかという工夫です。
データベースも基本的には同じ話ですが、興味があればこのあたりを読んでみてはどうでしょうか。
基礎から理解するデータベースのしくみ(7) データの格納方法を知ろう(2) -
- その他の回答を読む
この質問へのコメント
質問の情報
- 登録日時
- 2012-06-25 01:08:36
- 終了日時
- 2012-07-02 01:10:02
- 回答条件
- 1人5回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
この英文どうなってますか？ The boy seemed to be waiting for his mother to come.（その少年は母親が来…
匿名質問者
3
1
-
不定詞の形容詞的用法らしいんですけど、副詞的用法と書いたら✖️ですか？ I want to buy a book to read …匿名質問者11
-
日向陽葵という○V女優が好きなのですが似ている○V女優はいますか匿名質問者
-
共通テストで使われるプログラミング言語は共通テスト特有の言語と聞いたのですが、受験勉強で身につけたプ…匿名質問者21
-
内定してほしいポケモンはいますか？匿名質問者