ハッシュテーブル
ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである。
目次 |
[編集] 概要
ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。 通常、配列の添え字には非負整数しか扱えない。そこで、キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。しかしハッシュ関数の選び方（例えば、異なるキーから頻繁に同じハッシュ値が生成される場合）によっては、性能が劣化して最悪の場合O(n)となってしまう。
[編集] 実装方法
一つの実装例を示す。まず、ルート配列と呼ばれる要素数 N の配列を一つ用意する。ルート配列の各要素は、リスト（便宜上エントリリストと呼ぶ）とする。エントリリストには、少数のエントリを格納する。
エントリを格納する場合、エントリのキーをもとにハッシュ関数を用いてハッシュ値を生成する。ハッシュ関数は 0 から N - 1 までの整数値を生成するものであって、一様な分布と高速な計算が要求される。ハッシュ値を i とするとき、ルート配列上の i 番目のエントリリストにこのエントリを格納する。異なるキーが同じハッシュ値になることを衝突 (collision) と呼び、それらのエントリは同一のエントリリストに格納される。
あるキーをもつエントリを検索する場合、そのキーからハッシュ値を生成する。ハッシュ値を j とするとき、ルート配列上の j 番目のエントリリストに入っているエントリを一つずつ検索し、キーが一致しているものを取り出す。ルート配列上のエントリリストが高速でアクセスできる必要がある。
[編集] プログラミング言語におけるハッシュテーブルの実装
- Javaにおける
HashMapLinkedHashMapHashtable - AWKにおける連想配列
- PerlにおけるHash
- JavaScriptにおけるオブジェクト
- Pythonにおける辞書
- C++のSTLの
unordered_map - RubyのHashクラス
- Common Lispにおける(make-hash-table &key test size rehash-size rehash-threshold) [1]
- CLI (Common Language Infrastructure) の
System.Collections.Hashtable,System.Collections.Specialized.ListDictionary,System.Collections.Specialized.HybridDictionary,System.Collections.Generic.Dictionary<TKey, TValue>
[編集] 脚注
[編集] 関連項目
|
||||||||||||||||||||||||||||||||||||||||||||||
