Javaの観点から見ると、ハッシュマップのルックアップには一定の時間がかかると言えます。しかし、内部実装はどうですか？それでも、特定のバケット（キーのハッシュコードが一致する）を検索して、一致するさまざまなキーを探す必要があります。それでは、なぜハッシュマップのルックアップに一定の時間がかかると言うのでしょうか。説明してください。
43766 次
4 に答える
54
使用されているハッシュ関数に関する適切な仮定の下では、ハッシュ テーブルのルックアップには予想O(1) 時間がかかると言えます(線形プローブや連鎖ハッシュなどの標準的なハッシュ スキームを使用していると仮定します)。これは、平均して、ルックアップを実行するためにハッシュ テーブルが実行する作業量が多くても一定であることを意味します。
直観的には、「優れた」ハッシュ関数を使用している場合、要素がハッシュ テーブル全体に多かれ少なかれ均等に分散されると予想されます。つまり、各バケット内の要素の数は、要素の数をその数で割った値に近くなります。バケツの。ハッシュ テーブルの実装がこの数を低く抑えている場合 (たとえば、バケットに対する要素の比率が定数を超えるたびにバケットを追加することによって)、実行される予想される作業量は、どのバケットを選択するかのベースライン作業量になります。スキャンする必要があり、そこにある要素を見て「あまり多くない」作業を行います。これは、予想どおり、そのバケットには一定数の要素しか存在しないためです。
これは、ハッシュ テーブルがO(1) の動作を保証するという意味ではありません。実際、最悪の場合、ハッシュ スキームが劣化し、すべての要素が 1 つのバケットに格納されてしまい、最悪の場合、ルックアップに Θ(n) の時間がかかります。これが、優れたハッシュ関数を設計することが重要な理由です。
詳細については、アルゴリズムの教科書を読んで、ハッシュ テーブルがルックアップを非常に効率的にサポートする理由の正式な導出を確認することをお勧めします。これは通常、アルゴリズムとデータ構造に関する典型的な大学のコースの一部として含まれており、オンラインには多くの優れたリソースがあります。
興味深い事実: 特定のタイプのハッシュ テーブル (カッコウ ハッシュ テーブル、動的完全ハッシュ テーブル) があり、要素の最悪の場合のルックアップ時間は O(1) です。これらのハッシュ テーブルは、各要素がいくつかの固定された位置の 1 つにのみ配置されることを保証することで機能します。挿入は、すべての要素が適合するように要素の周りをスクランブルすることがあります。
お役に立てれば！
于 2013-03-18T04:37:03.087 に答える
10
キーは、ドキュメントの次のステートメントにあります。
多くのマッピングが HashMap インスタンスに格納される場合、十分な容量で作成すると、必要に応じて自動再ハッシュを実行してテーブルを大きくするよりも効率的にマッピングを格納できます。
と
負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。ハッシュ テーブルのエントリ数が負荷係数と現在の容量の積を超えると、ハッシュ テーブルが再ハッシュされ (つまり、内部データ構造が再構築され)、ハッシュ テーブルのバケット数が約 2 倍になります。
http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
負荷率を超えると内部バケット構造が実際に再構築され、 getとputの償却コストをO(1) にすることができます。
内部構造が再構築されると、O(N) になる可能性が高いパフォーマンス ペナルティが発生するため、償却コストが再び O(1) に近づく前に、かなりの数のgetとputが必要になる可能性があることに注意してください。そのため、初期容量と負荷率を適切に計画して、スペースを無駄にしたり、回避可能な内部構造の再構築を引き起こしたりしないようにしてください。
于 2013-03-18T04:37:14.497 に答える