ハッシュテーブルの大きなOとバイナリ検索ツリー

Question

どちらが長くかかりますか？

バイナリ検索ツリーに格納されているすべてのアイテムをソート順に印刷するか、ソート順にハッシュテーブルに格納されたすべてのアイテムを印刷します。

ハッシュテーブルのアイテムがソートされていないため、ハッシュテーブルのアイテムをソート順に出力するのに時間がかかりますか？ BSTは？

Answer 1

あなたは正しいですか？ハッシュテーブルは自然な並べ替え順序ではなく、いくつかのハッシュ関数でソートされるため、O（N）のすべてのエントリを抽出してO（NlogN）をソートする必要があります。 N）。

しかし、たとえばJavaでは、LinkedHashSetとLinkedHashMapがあります。これは、Hashの利点のいくつかを追加した順序でトラバースすることができるため、並べ替えることができますソートされた順序でそれをトラバースし、ハッシュで項目を抽出します。

Answer 2

正解ですが、ハッシュテーブルは、必要に応じて「ソート」されません。ハッシュテーブル内の要素は、ソートされていない場合がほとんどありますが、通常、並べ替えの種類はほとんどありません。しかし、それらはハッシュ関数に従って配列されていますが、これは通常、類似のフレーズでは大きく異なります。人間が使用するメトリックの種類ではありません。

あなたがあなたのコレクションでやっていることは、ソートされた順序で印刷しているのであれば、ある種のBSTを使うのが一番良いです。

Answer 3

バイナリ検索ツリーは、深度を最初に探索すると、並べ替えられた順序で項目が見つかる（一貫性のある比較関数があると仮定して）。既にツリーに入っているアイテムを返すだけの大きな仕事は、ツリーを横断する大きな仕事です。

ハッシュテーブルについては正しいですが、ソートされていません。実際には、平易なハッシュテーブルのすべてを列挙するためには、すべてのバケットをチェックしてそこにあるものを確認し、取り出し、取得したものを並べ替える必要があります。ソートされたリストを取得する作業がたくさんあります。

Answer 4

ハッシュテーブルがソートされたデータではないため、ハッシュテーブルに格納されているソートされたデータを正しく印刷するのが遅くなります。特定のアイテムを簡単に見つけることができます。 「Big O Notation」には、項目が一定時間、すなわちO（1）時間で見つけられると言われている。

一方、データが既にソートされているため、バイナリ検索ツリーの項目を「対数時間」（O（log n））で見つけることができます。

ソートされたリストを印刷するのが目的ならば、ソートされた順番（つまりバイナリツリー）でデータを保存するほうがはるかに良いでしょう。

これは興味深い質問のカップルが表示されます

ロバートC. Cartaino

Answer 5

、お楽しみください。次の点を考慮すると、検索ツリーはまだ高速ですか？

1. ハッシュテーブルとBSTのセットアップ時間を組み入れていますか？
2. ハッシュアルゴリズムがソートされた単語のリストを生成する場合。技術的には、そうするアルゴリズムを使用するハッシュテーブルを作成することができます。この場合、BSTとハッシュテーブルの速度は、ソートされた順序でハッシュテーブルを満たすのに要する時間になるはずです。

Answer 6

また、バイナリツリー対スキップリストの関連考慮事項をチェックアウト：Skip List vs. Binary Tree