Java ArrayListsが自動的に縮小されないのはなぜですか

Question

私はプリンストンCoursera MOOCのビデオ講義を見ました：アルゴリズムの紹介はhereです。 ArrayListのような構造のサイズを変更して要素を追加または削除する際のコストについて説明しています。私たちのデータ構造にサイズ変更を提供したい場合は、addとremove操作では、O(n)からamortized O(n)になります。

私はJavaのArrayListを数年間使用しています。私はいつも彼らが自動的に成長し縮小することを確信してきました。最近、私の大きな驚きに、私はthis postで間違っていることが判明しました。 Java ArrayListは、自動的に縮小しません。ここで

は私の質問です：私の意見では

1. は、パフォーマンスがすでにamortized O(n)あるようArrayList Sに縮小することは害がありません提供します。なぜJavaクリエイターはこの機能をデザインに含まなかったのですか？

2. 私はHashMapのような他のデータ構造も自動的に縮小しないことを知っています。自動縮小をサポートする配列の上にビルドされているJavaの他のデータ構造はありますか？

3. 他の言語ではどのような傾向がありますか？リスト、辞書、地図、Python/C＃などのセットの場合のように、自動縮小はどのように見えますか？Javaが行うのとは逆の方向に進むと、私の質問は：なぜですか？

Answer 1

コメントは既にあなたが求めているもののほとんどをカバーしています。ご質問にここではいくつかの考え：

1. JavaでArrayListような構造を作成し、開発者は実行時/パフォーマンスに関する特定の決定を行います。彼らは明らかに、必要とされる追加のランタイムを避けるために、「通常の」操作からの縮小を除外することに決めました。

2. なぜあなたが自動的に縮小したいのですか？ ArrayListはあまり増殖しません（ファクタは約1.5;正確にはnewCapacity = oldCapacity + (oldCapacity >> 1)）。たぶん、あなたはまた中央に挿入し、最後に追加するだけではありません。次に、LinkedList（配列に基づいていない - 収縮が必要ない）が良いかもしれません。それは実際にあなたのユースケースに依存します。 ArrayListが本当に必要だと思うのですが、要素を取り除くときに縮む必要があります（実際にはこれが必要なのか疑問です）。ArrayListを拡張してメソッドをオーバーライドしてください。しかし、注意してください！削除するたびに縮小すると、O(n)に戻ります。

3. C＃ListとC++ vectorは、要素の削除時にリストを縮小することに関しても同様に動作します。しかし、自動成長の要因はさまざまです。いくつかのJava実装でさえ、異なる要素を使用します。