0

正しい用語を使用しているかどうかはわかりませんが、Javaでコレクションがいっぱいになったときに、コレクションのサイズをどれだけ増やすかがどのように決定されるのか知りたいのですが。検索してみましたが、なかなか役に立たないです。

だから、もし私が 


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

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

4

8 に答える 8

7

それは呼び出す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

于 2010-09-22T15:49:02.877 に答える
2

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が変更される量を示します。

于 2010-09-22T15:49:19.277 に答える
2

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);
    }
    }
于 2010-09-22T15:51:05.790 に答える
2

javadocによると、

成長方針の詳細は、要素の追加には一定の償却時間コストがあるという事実を超えて指定されていません。

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

于 2010-09-22T15:55:51.167 に答える
1

通常、容量は2倍になります（または定数が乗算されます）。これにより、新しい要素の挿入にかかる時間はおおよそO（n）になります（ nのサイズとは関係ありません）。

于 2010-09-22T15:48:42.517 に答える
1

使用しているJDKの実装によって異なります。次のアルゴリズム（Apache Harmonyで使用）を見つけました：

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

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

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

于 2010-09-22T15:51:04.043 に答える
0

ArrayListの容量は必要に応じて増加します。容量を設定するときは、初期容量を設定します。コレクションが適切な初期サイズを持つことができるように、コンストラクターに推測を提供します。ArrayList！=配列。

于 2010-09-22T15:50:15.610 に答える
0

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

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

于 2010-09-22T15:51:05.700 に答える