対象読者
- アルゴリズムを勉強したい人
- Javaで実装してみたい人(次回)
Java/アルゴリズム勉強シリーズです。今回はhash tableを勉強したので実装してみます。
Javaのクラスとしては、単一スレッドなど、synchronizationを気にしないケースではHashtableよりもHashMapの方がよく使われるようです(こちらの記事で言及しました)。今回はJavaによらず、データ構造の一般論としての hash tableを指して、記事を書いていきます。次回Javaで実装します。
hash table
ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。
概要
キーを元に生成されたハッシュ値を添え字とした配列のこと。検索や追加時間を要素数によらず一定時間O(1)で実現することができる。
しかし、ハッシュ関数の選び方によっては(値がうまく散らばってくれると嬉しい)、性能が劣化して、最悪の場合O(n)となってしまう。つまり、keyの特性を見極め、衝突の少ない良いhash関数を選ぶことが重要である。かぶりが一つも存在しないhash関数をperfect hash functionという。
異なるキーから同じハッシュ値が生成された場合、衝突が起きる。その衝突を扱う方法として、以下の二つの方法が存在する。
- Separate chaining
- Open addressing
Separate chainingは衝突を起こしたキー同士を連結リストでつないでいき格納する方法である。
Open addressingは衝突が起きると、テーブルの中で空いている別の番地を探す方法である。ハッシュ関数とは別の関数を用いて次の候補隣る番地を求める。
すごく簡略化すると、検索時間的には、Open addressingの方がよく、メモリ使用量的にはSeperate chainingの方がよく節約できるという感じでしょうか。
hash table wikipedia(英語)がとてもよくまとまっていました。
二分探索木を使用してhash tableを実装することもできる
ハッシュ値を使用した二分探索木を作り、平衡を保つことで、O(log(n))の検索時間を保証することができます。また、配列において存在する空白の配列の要素などがななるため、メモリ的に節約できます。配列リサイズの必要もありません。
hash tableの実装は次回します。