ハッシュテーブル

概要

ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。これは \(x \mapsto y\) を表しているため写像 (map) の具体的な表現の一つと考えることもできる。

ハッシュテーブルが探索木と異なるのは、検索の典型的な期待実行時間が定数時間 \(O(1)\) となることである。

Table of Contents

1. 概要
2. 導入
3. 参考文献

導入

ハッシュテーブルには 2 種類がある。静的 (static) ハッシュテーブルは内容が変化しないことを前提としており、高速な検索操作のみをサポートする。動的 (dynamic) ハッシュテーブルは検索に加えて挿入と時に削除をサポートし、それぞれの操作はそれなりの性能で動作することが求められる。

参考文献

1. Avrim Blum, Manuel Blum. Universal and Perfect Hashing, CMU 15-451 Algorithms Lecture 10, 2011 Fall.