ArrayList's
私は、それ自体の中にデータを保存して操作するために広範囲に使用するWebアプリケーションを持っています。しかし、最近、私はそれHashMap's
がより良い選択だったかもしれないことを理解しました。Big O(n)
両方から要素を追加、アクセス、削除するためのアルゴリズムのコスト()と、効率のためにコードにアクセスして変更するのが賢明かどうかを誰かに教えてもらえますか?
3 に答える
ArrayList の場合:
size、isEmpty、get、set、iterator、および listIterator 操作は一定時間で実行されます。追加操作は償却された定数時間で実行されます。つまり、n 個の要素を追加するには O(n) 時間が必要です。他のすべての操作は線形時間で実行されます (大まかに言えば)。定数係数は、LinkedList の実装に比べて低くなります。
ドキュメントから: http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html
HashMap の場合:
この実装は、ハッシュ関数が要素をバケット間で適切に分散すると仮定すると、基本操作 (get および put) に対して一定時間のパフォーマンスを提供します。コレクション ビューの反復には、HashMap インスタンスの「容量」(バケットの数) とそのサイズ (キーと値のマッピングの数) に比例する時間が必要です。したがって、反復のパフォーマンスが重要な場合は、初期容量を高く設定しすぎないようにする (または負荷係数を低く設定しすぎない) ことが非常に重要です。
ドキュメントから: http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
ArrayListのドキュメントには、これらの操作のパフォーマンスに関する説明があります。に関しては、全3種HashMap
となります。ただし、これは、メソッドが適切に実装されているO(1)
ことを前提としています。hashCode
O(1)