ハッシュテーブル
ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。通常、配列の添え字には非負整数しか扱えない。そこで、キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。しかしハッシュ関数の選び方(例えば、異なるキーから頻繁に同じハッシュ値が生成される場合)によっては、性能が劣化して最悪の場合O(n)となってしまう。
JavaにおけるHashMap, LinkedHashMap, Hashtable クラス
AWKにおける連想配列
PerlにおけるHash
JavaScriptにおけるオブジェクト
Pythonにおける辞書
C++のSTLのstd::unordered_map
RubyのHashクラス
Common Lispにおけるhash-tableクラス
CLI (Common Language Infrastructure) の System.Collections.Hashtable, System.Collections.Specialized.ListDictionary, System.Collections.Specialized.HybridDictionary, System.Collections.Generic.Dictionary<TKey, TValue>
RustのHashMap
Nimのstd/tables