こんにちは!今日の講義は
ArrayList
、これまでの講義よりも簡単になる一方で、より難しくなります。 今日は「内部」を覗いてArrayList
、運用中に何が起こっているかを研究するので、これはさらに困難です。一方、この講義にはコードはほとんどなく、ほとんどが画像と説明です。それでは、行きましょう:) すでにご存知のとおり、ArrayList
'a の内部には、データ ストアとして機能する通常の配列があります。ほとんどの場合、リストの正確なサイズは指定されません。ただし、内部配列にはある程度のサイズが必要です。これは本当です。デフォルトのサイズは [10] です。
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
}
まず、新しい要素の追加がどのようなものかを見てみましょう。まず、内部配列に十分なスペースがあるかどうか、およびもう 1 つの要素が収まるかどうかがチェックされます。スペースがある場合は、新しい要素がリストの最後に追加されます。「最後まで」と言うとき、配列の最後のセルを意味するわけではありません (これは奇妙です)。これは、現在の最後の要素の次のセルを指します。そのインデックスは に等しくなりますcars.size()
。現在リストは空です ( cars.size() = 0
)。したがって、新しい要素が Index のセルに追加されます0
。
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);
ここではすべてが明らかです。挿入が途中、つまり複数の要素の間に行われた場合はどうなりますか?
public static void main(String[] args) {
ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
Car ford = new Car("Ford Modneo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
cars.add(1, ford);//добавляем ford в ячейку 1, которая уже занята
}
繰り返しますが、最初に配列内に十分なスペースがあるかどうかがチェックされます。十分なスペースがある場合、要素は新しい要素を挿入するセルから右にシフトされます。インデックス 1 のセルに貼り付けます。つまり、セル 3 の要素がセル 4 に、要素 2 がセル 3 に、要素 1 がセル 2 にコピーされます。 その後、新しい要素が所定の位置に貼り付けられます。前の要素 ( bugatti
) はすでにそこから新しい場所にコピーされています。 ここで、配列に挿入するスペースがない場合にこのプロセスがどのように行われるかを考えてみましょう。 もちろん、最初に、十分なスペースがあるかどうかがチェックされます。十分なスペースがないことが判明した場合は、ArrayList
(OldArray のサイズ * 1.5) + 1 のサイズの新しい配列が 'a 内に作成されます。この場合、新しい配列のサイズは 16 セルになります。現在のすべての要素がすぐにそこにコピーされます。 古い配列はガベージ コレクターによって削除され、新しい拡張された配列のみが残ります。これで、新しい要素用の空きスペースができました。これを、占有されているセル 3 に貼り付けます。さて、おなじみの手順が始まります。インデックス 3 で始まるすべての要素が 1 セル右にシフトされ、新しい要素が静かに追加されます。 これで挿入が成功しました!インサートを整理しました。次に、要素の削除について話しましょう。覚えているとおり、配列を操作するときに問題が発生しました。配列を削除すると、配列に「穴」が残ってしまいます。唯一の解決策は、要素が削除されるたびに 要素を左にシフトすることであり、シフトのコードを自分で記述する必要がありました。ArrayList
同じ原理で動作しますが、このメカニズムではすでに自動的に実装されています。 これは次のようになります: そして最終的には、 要素がlambo
正常に削除されたという望ましい結果が得られます。ここでは真ん中から削除しました。他のすべての要素を移動せずに目的の要素が削除されるため、リストの末尾から削除する方が高速であることは明らかです。内部配列のサイズとメモリ内のそのストレージをもう一度見てみましょう。 配列の拡張は、一定量のリソースを必要とするプロセスです。ArrayList
したがって、少なくとも 100 個の要素が含まれることが確実にわかっている場合は、デフォルト サイズで 作成しないでください。100 番目の要素を挿入するまでに、内部配列は6 回拡張され、毎回すべての要素が転送されます。
- 10要素から16要素へ
- 16要素から25要素へ
- 25から38まで
- 38から58まで
- 58から88まで
- 88 から 133 (式 (古い配列のサイズ * 1.5) + 1 による)
ArrayList<Car> cars = new ArrayList<>(100);
100 個の要素の配列がメモリに即座に割り当てられるようになり、拡張時にリソースが無駄にならないため、より効率的になります。コインの裏側もあります。 オブジェクトが内部配列から削除されても、サイズは自動的には縮小されません。ArrayList
たとえば、ArrayList
88 個の要素からなる内部配列があり、完全に埋められています。 プログラムの操作中に、そこから 77 個の要素が削除され、11 個だけが残ります。 何が問題なのか、もうわかりましたか? もちろん、メモリの使用は非効率的です。使用するセルは 11 個だけですが、メモリは 88 個の要素に割り当てられています。これは必要量の 8 倍です。この場合に最適化を実行するには、特別なクラス メソッドArrayList
-を使用できますtrimToSize()
。内部配列の長さを、現在そこに格納されている要素の数に「カット」します。 これで、必要な量のメモリが割り当てられるようになりました。:)
GO TO FULL VERSION