达到尺寸时，Java集合自动重新分配

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

题

我不确定我是否正在使用正确的术语，但是我很好奇它是如何确定在java中增加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.ensureCapacity() .

如有必要，增加此数组实例的能力，以确保它至少可以容纳最低容量参数指定的元素数量。

这 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源代码，但在不同版本中可能会有所不同。没有保证的生长因素。

通常，容量加倍（或乘以常数）。这确保了插入新元素所花费的时间大致 在） （独立于大小 n).

这取决于您正在使用的JDK实现。我找到了 遵循算法 （用于Apache Harmony）：

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

意味着尺寸增加了旧尺寸的一半，最小12。

但是正如我所说，这是特定于实施的，因此所有JVM都可以自己处理这一方法。

阵列列表的容量根据需要增加。当您设置容量时，您将设置初始容量 - 您正在向构造函数提供一个猜测，以便该集合可以拥有良好 最初的 尺寸。 arrayList！= array。

Java中的ArrayList永远不会满足，其大小将在满足时会增长，并且需要在其中添加更多数据。

如果您想询问低级实现，我认为该数组列表可以使用数组来包含数据。然后，我认为，当数组列表所保存的数组已满时，阵列列表创建一个具有双重大小的新数组，并将所有元素从旧数组复制到新数组。但这是我的假设，您需要阅读Java Doc

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top