在ArrayList中的ensureCapacity方法中使用的逻辑 [英] Logic used in ensureCapacity method in ArrayList

问题描述

我正在浏览ArrayList的源代码。我遇到了方法ensureCapacity（），它增加了内部使用的数据数组的容量。其中，数据阵列的新容量基于逻辑 int newCapacity =（oldCapacity * 3）/ 2 + 1; 增加，其中旧容量是当前数据数组的大小。是否有任何特殊原因选择（oldCapacity * 3）/ 2 + 1 这是新的数组大小，如果是这样的话是什么？

I was going through the source code of ArrayList. I came across the method ensureCapacity() which increases the capacity of the data array used internally. In that, the new capacity of the data array was increased based on logic int newCapacity = (oldCapacity * 3)/2 + 1; where old capacity is the current data array size. Is there any particular reason for choosing (oldCapacity * 3)/2 + 1 this as new array size, if so what is it?

/**
 * 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);
}
}

提前致谢...

推荐答案

在JavaDoc中做出的唯一保证是添加新元素具有恒定的摊销时间。这意味着向数组添加新元素的平均时间是不变的。有时它可能需要更长的时间（比如在尝试调整阵列大小时），但总体而言这些情况非常罕见，因为它不会对平均值造成太大影响。

The only guarantee made in the JavaDoc is that adding a new element has constant amortized time. That means that the average time of adding a new element to the array is constant. Sometimes it might take a bit longer (like when trying to resize the array), but overall these cases are rare enough for it not to affect the average too much.

所以为了让他们能够尊重这种保证，他们需要确保调整大小很少发生，以免影响平均增加时间。出于这个原因，他们使用新容量的当前容量的百分比。如果调整大小类似于 oldCapacity + 50 ，则数组对于小数组列表来说太大了，但如果要添加几千个元素，则每50个元素的大小调整会带来表现方式下降。这样容量会成倍增加（如果你已经添加了很多元素，你可能会增加更多元素，所以它们会增加更多容量）所以它不会使性能降低太多。

So for them to be able to respect that guarantee they need to make sure the resizing happens rarely enough as to not affect the average adding time. They use a percent of the current capacity for the new capacity for this reason. If the resize would be something like oldCapacity + 50 the array would be too big for small arrayLists, but if you want to add a few thousand elements, resizing every 50 elements would bring the performance way down. This way the capacity increases exponentially (if you already added a lot of elements, chances are you will add more, so they increase the capacity by more) so it doesn't degrade the performance too much.

至于为什么他们选择了50％，也许他们认为容量增加一倍（或更多）可能是过度杀戮（对于非常大的ArrayLists会消耗太多的额外内存），而且太低了（比如10） -25％）会使性能降低太多（通过执行太多的重新分配），因此可能+ 50％提供足够好的性能，而不会占用太多的额外内存。我猜他们在决定价值之前做了一些性能测试。

As to why they chose 50%, perhaps they felt that doubling (or more) the capacity might be overkill (would consume too much extra memory for very large ArrayLists), and going too low (like perhaps 10-25%) would degrade the performance too much (by doing too many reallocations), so probably +50% offered good enough performance, without taking too much extra memory. I'm guessing they did some performance tests before deciding on the value.

这篇关于在ArrayList中的ensureCapacity方法中使用的逻辑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！