RSS
データを、キーと値をペアにした状態で管理し、キーを使って値を効率よく探索できるデータ構造です。
ハッシュテーブルは、データを登録するときに指定されたキーに、一定の計算を行って得られた値を添字として使う配列です。ここで行う計算をハッシュ関数、得られる値をハッシュ値と呼びます。ハッシュ関数が実装できるのであれば、キーはどのような型や値でも構いません。
ハッシュ関数の計算分のコストはあるものの、目的のデータの位置が計算１つで即座に定まるため、データの探索や追加、削除を圧倒的な高効率で実現できます（計算量でいえば O(1)）。しかし仕組み上、異なるキーから同じハッシュ値が生成される、衝突と呼ばれる問題が起こることがあり、その際の対処による追加のコストが発生し、計算量が悪化する場合があります。
キーの分布やデータの総数があらかじめ予測可能であって、うまく配列全体にばらけて格納できるようなハッシュ関数を実装できないかぎりは、基本的に衝突の発生を避けることはできません。
衝突発生時の対処方法はいくつか知られており、連結リストを使って、同じ位置にデータをつないでいくチェイン法や、ほかの空いている場所を探す再計算（再ハッシュ）を行うオープンアドレス法などがあります。
チェイン法については、アルゴリズムとデータ構造編【探索】第６章、オープンアドレス法については第７章で解説しています。
ハッシュテーブルは、連想配列（辞書、マップ）のような、探索の効率の良さに特徴がある抽象データ型を実装する方法としてよく用いられています。
Ｃ言語には、標準のハッシュテーブルはありません。
C++ の標準ライブラリの std::unordered_map は、ハッシュテーブルを使って実装されています。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |