ハッシュテーブルは常にツリーよりも高速ですか？ハッシュテーブルにはO（1）の検索の複雑さがありますが、ハッシュ関数の設計が不適切なために多くの衝突が発生し、連鎖構造（たとえばバランスの取れたツリー）を使用して衝突を処理する場合、検索の最悪の実行時間はO（log n ）。それで、最悪のシナリオの場合でも、ハッシュテーブルは常にツリーよりも高速であると結論付けることができますか？また、十分なメモリがあり、範囲検索が必要ない場合は、常にハッシュテーブルを検索できますか？
質問する
4208 次
4 に答える
10
ハッシュテーブルは常にツリーよりも高速ですか？
いいえ、常にではありません。これは、コレクションのサイズ、ハッシュ関数、一部のハッシュテーブルの実装（削除操作の数など）など、多くの要因に依存します。
ハッシュテーブルは平均しO(1)て操作ごとにありますが、常にそうであるとは限りません。最悪の場合です。O(n)
私が現時点で木を好むと考えることができるいくつかの理由：
- 注文は重要です。[ハッシュテーブルは順序を維持していません。BSTは定義によってソートされています]
- レイテンシーは問題です-そしてあなたはそれが起こるかもしれないことに苦しむことはできません
O(n)。[これはリアルタイムシステムにとって重要かもしれません] - それらのデータはハッシュ関数に「類似」している可能性があり、同じ場所[衝突]にハッシュされた多くの要素はありそうもないことではありません。[これは、別のハッシュ関数を使用することで解決できる場合があります]
- 比較的小さなコレクションの場合（多くの場合、ハッシュテーブル間の隠し定数
O(1)はツリーよりもはるかに高くなります）、ツリーを使用すると、小さなコレクションの方が高速になる可能性があります。
ただし、データが巨大な場合、遅延は問題ではなく、衝突の可能性は低くなります。ハッシュテーブルは、ツリーを使用するよりも漸近的に優れています。
于 2012-04-05T17:56:30.093 に答える
1
不適切に設計されたハッシュ関数が原因で多くの衝突が発生し、連鎖構造（バランスツリーなど）を使用して衝突を処理する場合、検索の最悪の場合の実行時間はO（n）（O（log n）ではない）になります。したがって、最悪のシナリオの場合でも、ハッシュテーブルは常にツリーよりも高速であるため、大きなデータセットまたは小さなデータセットについて結論を出すことはできません。
于 2012-04-05T17:56:38.267 に答える
0
ハッシュテーブルを使用し、適切なディメンションで初期化します。たとえば、半分のスペースのみを使用する場合、衝突は非常に少なくなります。
于 2012-04-05T17:55:28.610 に答える
0
最悪のシナリオでは、速攻テーブルでO（n）時間があります。しかし、これは現在、太陽が爆発する書き込みよりも数十億少ない可能性が高いため、優れたハッシュ関数を使用すると、太陽が爆発しない限り、O（1）で機能すると安全に想定できます。
一方、ハッシュテーブルとツリーの両方のパフォーマンスは、実装、言語、月の満ち欠けによって異なる可能性があるため、この質問に対する唯一の良い答えは、「両方を試して、考えて、よく選ぶ」です。
于 2012-04-05T17:55:39.910 に答える