ハッシュテーブル
7. ハッシュテーブル(Hash Table)
メモリー効率を犠牲にしてでも(たいていのケースで)O(1)でデータにアクセスすることを可能にするこの方法は、連想配列の実装に最適で、Perlで多用されたことから今では連想配列の代名詞にすらなってしまった。
現在のLLでは、いずれも組み込みでこれをサポートしているし、CやC++のライブラリーも充実していることもあって、自ら実装する機会はあまりないと思われるが、その特性は知っておいた方がよい。
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
ハッシュテーブルは以下のような利点を持っています。
- ハッシュ関数に偏りがなく、十分なサイズの配列を取れるなら、ほぼ一定時間で要素の挿入・削除・検索ができます。
ただし、以下のような欠点もあります。
このような特徴から、 偏りのないハッシュ関数が用意できて、かつ、 メモリがふんだんにある環境ではハッシュテーブルがよく用いられます。
ハッシュテーブル - アルゴリズムとデータ構造 | ++C++; // 未確認飛行 C
二分木
8. 二分木(Binary Tree)
これはアルゴリズムというよりデータ構造であるが、両者には密接な関係があるのでここで紹介してもいいだろう。配列ソートにしろハッシュテーブルにしろ、データ構造は配列にデータを転がしているという点において「乱暴」であるが、こちらはデータの並べ方を工夫することによって、データへのアクセスを常にO(ln N)に抑えるという点が特徴だ。
ただし、メモリー確保(具体的にはmalloc)のコストが結構あるということで、メモリー(再)確保の回数が少ない、配列を使ったデータ処理よりも実際は低速なことが多いので、メモリーだけで用が足りる場合には意外と出番が少なかったりもする。
ところが、これがハードディスクが相手となると、とたんにこの方法の利点が生きてくる。これの変種であるB+木などは、データベースの実装などで実によく使われている。まともな計算機科学のクラスであれば、このアルゴリズムを必ず教えるのには理由があるのだ。
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2分探索木は以下のような利点を持っています。
- 理想的には、要素の挿入・削除・検索が O(log n) で行える。
- ハッシュテーブルのように、メモリを多めに確保しておく必要がない。
- また、ハッシュ関数の作り方に悩む必要もない。
- 要素を整列された順序で取り出せる。
ただし、以下のような欠点もあります。
- 木の高さがバランスを保っていないと検索などが O(n) になる。平衡化機構が必要。
ちなみに、2分探索木への、平衡化機構の組込み方にはいくつか種類があります。 実装が簡単なのでよく用いられる物としては、 赤黒木あるいは2色木（red-black tree）と呼ばれるものがあります。
2分探索木 - アルゴリズムとデータ構造 | ++C++; // 未確認飛行 C
平衡2分探索木では、検索・挿入・削除には O(log n) の時間がかかるが、基数木では O(k) である。一般に k e" log n であるから、これは利点とは見なされないが、平衡2分探索木での比較は常に文字列の比較であり、最悪で O(k) の時間がかかる。特に長い接頭部が共通な文字列を多数格納していると遅くなる。
基数木 - Wikipedia
二分木の弱点を抱え込む
404 Blog Not Found:algorithm - 基数木 + 平衡二分探索木 = 三分探索木
二分木というのは放っといても平衡しません。例えばソート済みのデータを食わせると、そのままでは常に片側の枝が空のゴージャスな線形リストが出来上がります。それが起こらないように要素の追加と削除の都度平衡させる技術はすでに確立されて利用されていますが、自分で実装するとなるとかなり煩雑です。
しかし三分探索木に関しては、「本物の」平衡二分探索木よりこの部分を簡素化する余地が大きそうです。例えば要素削除の際の平衡をやめてもいいですし、元の論文のようにあらかじめデータがある場合には、最初の文字をカウントして中央値を得るという方法で平衡処理をなくしています。
比較
その連想配列の実装手段はいくらでもあります。B木も、二分木も、あるんだよ。キーと値のペアを並べただけの配列やリストだって立派な連想配列ですが、それでは値にアクセスする都度線形探索しなければなりません。二分探索木ですらO(log(n))なところに登場したのが、配列と同じくO(1)アクセスをものにしたハッシュテーブルでした。awkで先鞭をつけperlで人気が爆発したそれが連想配列の別名となったのは「お手柄だよ、Wall」なのですが、おかげで他の実装方法が「特殊化」してしまったことも否めません。
404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?
ハッシュ法はデータを高速に検索できる優れたアルゴリズムです。データを検索するだけならば、二分探索木よりもハッシュ法が優れています。ですが、二分探索木にはハッシュ法にはない長所があります。二分探索木はデータの大小関係で構成されているので、左の木をたどることで最小値を、右の木をたどることで最大値を簡単に求めることができます。ハッシュ法で最大値や最小値を求めるには、すべてのデータを調べなければいけません。また、二分探索木では通りがけ順でデータを出力すれば、ソートされた結果を得ることができます。データの大小関係を処理する場合は、ハッシュ法よりも二分探索木を選ぶといいでしょう。
お気楽 OCaml プログラミング入門
