Javaコレクションサイズに達したときの自動リアルロケーション

StackOverflow https://stackoverflow.com/questions/3771040

質問

正しい用語を使用しているかどうかはわかりませんが、Javaがいっぱいになったときにコレクションのサイズをどれだけ増やすかを決めたことに興味がありますか？私は検索を試みましたが、私は本当に役に立つことは何も考えていません。

だから、私がどんなものを持っているなら


List l = new ArrayList(1);
l.add("1");
l.add("2");
リストのサイズを増やす量をどのように決定しますか？それは常に設定値ですか、もしそうなら、その値は何ですか？また、Bitsetが異なる場合、この情報に興味があります。

ありがとう、そして私が何かを明確にするべきかどうか教えてください。

役に立ちましたか？

解決

それは呼び出します ensureCapacity:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3) / 2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

あなたが見ることができるように newCapacity それは (oldCapacity * 3) / 2 + 1

他のヒント

ArrayListのソースには、いくつかの手がかりがあります。

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}


/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

この行： int newCapacity = (oldCapacity * 3)/2 + 1; ArrayListが変更される量を示します。

ArrayListには、サイズがアレイ内で成長できるようにサイズがある場合に成長するオブジェクトの配列が含まれています。

中身 ArrayList.ensureCapacity() .

必要に応じて、このArrayListインスタンスの容量を増やして、最小容量引数で指定された要素の数を保持できるようにします。

add(E e) 電話 ensureCapacity()

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

による Javadoc,

成長ポリシーの詳細は、要素を追加すると一定の償却時間コストがかかるという事実を超えて指定されていません。

したがって、人々がJDKソースコードを投稿しているのは素晴らしいことですが、バージョンによって異なる可能性があります。保証された成長因子はありません。

通常、容量は2倍になります（または定数を掛けます）。これにより、新しい要素を挿入するのにかかった時間がおおよそします の上） （のサイズに依存しない n).

使用しているJDK実装に依存します。私はそれを見つけました 次のアルゴリズム （Apache Harmonyで使用）：

int increment = size / 2;
if (required > increment) {
    increment = required;
}
if (increment < 12) {
    increment = 12;
}

サイズが古いサイズの半分、最小12だけ増加することを意味します。

しかし、私が言ったように、これは実装固有のものであるため、すべてのJVMはこれを独自の方法で処理できます。

アレイリスト容量は必要に応じて増加します。容量を設定するとき、あなたは初期容量を設定しています - あなたはコレクションに良いものを持つことができるようにコンストラクターに推測を提供しています イニシャル サイズ。 arrayList！= array。

JavaのArrayListは完全になることはなく、そのサイズがいっぱいになると成長し、さらにデータを追加する必要があります。

低レベルの実装について尋ねたい場合は、ArrayListが配列を使用してデータを封じ込めることができると思います。次に、アレイリストが保持する配列がいっぱいになった場合、アレイリストはダブルサイズの新しい配列を作成し、古い配列から新しい配列にすべての要素をコピーすると思います。しかし、これは私の仮定であり、Javaドキュメントを読む必要があります

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top