Posted at

【アルゴリズム】Hash Tableの概要

More than 3 years have passed since last update.


対象読者


  • アルゴリズムを勉強したい人

  • Javaで実装してみたい人(次回)

Java/アルゴリズム勉強シリーズです。今回はhash tableを勉強したので実装してみます。

Javaのクラスとしては、単一スレッドなど、synchronizationを気にしないケースではHashtableよりもHashMapの方がよく使われるようです(こちらの記事で言及しました)。今回はJavaによらず、データ構造の一般論としての hash tableを指して、記事を書いていきます。次回Javaで実装します。


hash table

ハッシュテーブル wikipediaより


ハッシュテーブル (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の実装は次回します。