ハッシュマップとツリーマップのメリットとデメリットは？

Question

C++はデフォルトでツリーベースのマップを提供します。ブーストではhashmapを得ることができます。

1. C++のツリーベースの地図と

2. ブーストのHashMapの の長所と短所は何ですか？

Answer 1

C++ 0x/TR1は、通常、ハッシュマップとして実装されるunordered_mapも提供します。

違いは2つあります：

1. キータイプ。順序付けられたマップでは、キータイプは厳密な弱い順序に従わなければならず、エントリはその順序で維持されます。順序付けされていないマップでは、キーの型は等価でなければならず、hというハッシュ関数を提供する必要があります。h(Key)はsize_t [説明のためにSteve Jessopに感謝]を返します。

2. アクセスの複雑さ：順序付けられたマップの挿入/削除/検索は、マップサイズnのO（ログn）です。順序付けられていないマップでは、通常はO（1）ですが、最悪の場合の動作はO（n）です（たとえば、すべてのキーが同じハッシュ値にマップされている場合）。

順不同マップはあなたのハッシュ関数の品質に応じて、良い例に（良い）複雑を提供しながら、だから、注文したマップは、総複雑保証を提供します。

順序付けられていないマップの内部実装の複雑さは、順序付けされたマップのものよりも大きいですが、少ない機能しか得られないため、アクセスの複雑さが増すと考えられます。これは古典的なトレードオフです。

もう1つのポイント：実際には、文字列の場合と同様に、計算コストが高い場合、ハッシュタイプの比較が非常に高速であるため、実際には、無秩序マップはかなり高速になります。一方、あなたのキータイプが（組み込みの整数型のような）簡単なハッシュ関数を持っていて、注文が必要ない場合は、順序のないコンテナを使うことを検討してください。

Answer 2

ハッシュテーブルは、非常に高速の検索アクセスとオブジェクトの挿入/削除を提供します。このような操作の複雑さは、一定時間を意味する平均O（1）です。これらの2つの操作の主な制限は、ハッシュアルゴリズムの速度です（PODではないオブジェクトの種類によっては、これらが少し複雑になり、2つの異なるオブジェクトがハッシュする "衝突"を避けるために、同じ値）。ハッシュテーブルの主な欠点は、余分なスペースが必要だということです。

もう一方のバイナリツリーは、挿入と検索の時間が比較的短く、削除とオブジェクトの複雑さは挿入と同じです。各ノードに2つ以上の子ノードがあるバイナリツリーが動作する方法のため、検索とアクセス時間（挿入と削除だけでなく）にはO（ログN）時間がかかります。したがって、バイナリーツリーはハッシュテーブルよりも「遅い」が、実装するのが複雑ではありません（バランスのとれたバイナリ検索ツリーはアンバランスなツリーより複雑です）。

バイナリ検索ツリーの別の利点は、コンテナを「最初の」要素から「最後の」要素まで反復することで、オブジェクトのソートされたリストを取得できることです。そのリストはソートされません。したがって、挿入の余分な時間は、バイナリ検索ツリーがソートされた挿入であるという面も考慮に入れます。例えば、N個のアイテムのグループに対するクイックソートの複雑さは、N個のアイテムの同じグループに対する平衡バイナリ検索ツリー（すなわち、赤/黒のツリー）を構築するのと同じ複雑さである。両方の操作はO（N log N）です。