0

重複の可能性:
LinkedList または ArrayList に対して HashMap を使用する場合、およびその逆を使用する場合

MapsJavaに出くわして以来、私はそれらを広範囲に使用してきました。特にHashMap、多くのシナリオで優れたオプションです。それはArrayListすべてのカテゴリで に勝っているようです - 反復は予測できないと言う人もいますが、そのために . がありLinkedHashMapます。

ですから、私の質問は次のとおりHashMapです。しっかりした不変のキーがあるのであれば、常に a を使用しないのはなぜですか?

さらに、アイテムの数が非常に少ない (<10) 場合に a のようなものを使用するのは適切HashMapですか、それとも考慮していない追加のオーバーヘッドがありますか?

4

3 に答える 3

1

HashMap には、配列 (または ArrayList) と比較してかなりの量のオーバーヘッドがあります。

  • キーをハッシュしてバッキング配列へのインデックスを取得し、値とキーを保存する必要があります。これは遅く、配列より多くのメモリを使用します。これは、ハッシュに時間がかかるか、より多くのスペースを必要とするため、キーが大きいまたは複雑なものである場合により重要です。
  • また、値を検索するたびにキーをハッシュする必要があります。
  • ArrayList のサイズを変更するときは、新しい配列を作成してすべてをコピーするだけです。HashMap のサイズを変更するときは、新しい配列を作成してから、ハッシュをもう一度計算します (したがって、ハッシュは新しい配列全体に分散されます)。
  • HashMap は、いっぱいになるとパフォーマンスが低下するため、通常、スペースの 25% 程度を空のままにします。

これらはすべて非常に小さなものなので、常に HashMap を使用するだけで済みます (実際、これは PHP が行っているようです) が、本当に必要のないときに HashMap を使用するのは無駄です。

比較が役立つかもしれません: 整数でできることはすべて文字列でもできるのに、なぜ整数があるのでしょうか? それらはより小さく、より高速に動作するためです (また、常に数値が含まれているなど、いくつかの優れた保証を提供します)。

于 2012-11-05T02:19:47.933 に答える
1

私は常にマップを使用しています。これは、最も強力で用途の広いデータ構造の 1 つです。私は主に LinkedHashMap を使用しますが、文字列をキーとして使用する場合は、キーを並べ替えるという追加の利点があるため、TreeMap を使用します。

でも：

  • キーが int で、すべてのキー 0..n を使用する予定の場合は、配列を使用します (覚えておいてください - int は Integer よりも効率的です)。ただし、「疎な値」がある場合はマップの方が適しています
  • 索引付けされていないアイテムのリストが必要な場合は、リンクリストを使用してください
  • 一意の要素を保存する必要がある場合は、セットを使用してください (キーだけが必要な場合、値を保持するためにスペースを無駄にする必要はありません)。

覚えておいてください - Java は非常に強力なコレクション (Set、Map、List) を提供し、それぞれに異なる機能を持つ複数の実装を提供します - それらには理由があります。

すべてのデータ構造には用途があります。多くがバックエンドとしてマップを使用して実装できる場合でも、最も適切なデータ構造が...より適切です (通常、より効率的で、オーバーヘッドが少なく、より多くの機能を提供します)。

サイズは問題ではありません - 5 つまたは 500 の要素で、マップのように見える場合は、マップを使用します (最大の効率が必要で、ハード コーディングされた値の方が優れている例外やコーナー ケースはほとんどありません)。しかし、セットのように見える場合は、セットを使用してください。

于 2012-11-05T02:21:34.960 に答える
1

ArrayListキーが連続する整数の場合は、を使用します。(それらが 0 に基づいていない場合は、オフセットを使用してください。) アクセス (特にランダム アクセス) と更新がはるかに効率的です。そうでなければ、確かにHashMap(または、あなたが言うようにLinkedHashMap) は非常に有用なデータ構造です。

a のデフォルトの初期サイズHashMapは 16 バケットなので、リストが非常に小さい場合は多少のオーバーヘッドが生じると思います。ただし、大量のマップを作成する場合を除き、コーディングの要因にはなりません。

于 2012-11-05T02:17:39.527 に答える