ほんの 5 分前に、私はそのArrayList仕組みを知りました。elementData特定のタイプの配列であるフィールドがあり、要素を追加して配列elementDataがいっぱいになると、コレクションは内部的に次の式で別の配列を作成します。
(oldCapacity * 3) / 2 + 1
そして、古い配列から新しい配列にデータをコピーします。私はちょうど疑問に思っています、それはなぜですか？なぜ最後のサイズを2倍にしないのですか？この数式を記述して、ArrayList コレクションの内部表現に関するより理論的な情報をどこで入手できますか。PS私の母国語ではない英語で申し訳ありません。
実際には、要素の追加に一定の償却コストがかかることを保証することを除いて、成長ポリシーは指定されていません。
提案するスキームとJDKで使用されるスキームの両方が、そのような保証を提供します。実際、乗法的な成長スキームは準拠しています。他の言語/ライブラリではサイズが 2 倍になるため、これも一般的なスキームです。別の Java 実装は、そのスキームに従うことを選択しても、仕様に準拠することができます。
std::vector 挿入の償却分析の議論を参照してください。これは C++ に関するものですが、Java にも同様に当てはまります。
客観的な尺度はない可能性が高い。より多くのメモリを浪費することでコピーを回避することも、より頻繁にコピーすることでメモリを節約することもできます。これら 2 つは、1 つの目標関数で客観的に測定することはできません。