0

我不确定我是否使用了正确的术语，但我很好奇它是如何确定在 Java 中的 Collection 变满时增加多少？我试过搜索，但我并没有真正想出任何有用的东西。

所以，如果我有类似的东西 


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

根据javadoc，

除了添加一个元素具有恒定的摊销时间成本这一事实之外，没有指定增长策略的细节。

因此，虽然人们发布 JDK 源代码很好，但在不同版本中可能会有所不同；没有保证的增长因素。

于 2010-09-22T15:55:51.167 回答
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 回答
1

通常容量加倍（或乘以一个常数）。这确保了插入新元素所需的时间大约为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 容量根据需要增加。当您在其上设置容量时，您正在设置初始容量 - 您正在向构造函数提供猜测，以便集合可以具有良好的初始大小。数组列表！= 数组。

于 2010-09-22T15:50:15.610 回答
0

Java 中的 ArrayList 永远不会被填满，当它被填满时它的大小会增长并且需要向其中添加更多数据。

如果您想询问低级实现，我假设 ArrayList 可以使用数组来包含数据。然后，我认为当 ArrayList 保存的数组已满时，ArrayList 会创建一个双倍大小的新数组，并将旧数组中的所有元素复制到新数组中。但这是我的假设，您需要阅读 java 文档

于 2010-09-22T15:51:05.700 回答