マップとハッシュまとめ

マップとハッシュ

マップ

二分木によるツリーマップとハッシュ表によるハッシュマップがある。

ツリーマップ
・データの追加と削除がまぁまぁ高速
・データの検索もまぁまぁ高速

パフォーマンス
ラッキーなとき　O(logN)
アンラッキーなとき　O(N)

C++やJavaのmapクラスがコレ。

ハッシュマップ
・データの追加、削除、検索すごい高速
・メモリ消費量やや多め
・メモリ確保にゆとりを持たないとハッシュ衝突でパフォーマンス低下
・キーに対応するハッシュ値を求め、配列にデータ格納
・データを格納する構造体を指すポインタの配列を確保する必要あり

パフォーマンス
いつもほぼO(1)！

JavaにはHashMap/HashtableクラスあるけどC++のSTLにはない。
ちなみにハッシュ関数 (ハッシュかんすう、hash function) とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという。
Wikipediaに代表的なハッシュ関数が紹介されている。