ArrayList中ensureCapacity方法中使用的邏輯

我正在瀏覽ArrayList的源代碼。我遇到了方法ensureCapacity（），它增加了內部使用的數據數組的容量。其中，根據邏輯int newCapacity = (oldCapacity * 3)/2 + 1;增加數據陣列的新容量，其中舊容量是當前數據陣列的大小。是否有任何特別的理由選擇(oldCapacity * 3)/2 + 1作爲新的數組大小，如果是這樣的話？ArrayList中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); 
} 
}

在此先感謝...

來源

2010-07-26 vcosk

我只是看着Java 6的ArrayList實現，我找不到你提到的那一行。這是來自Effective Java嗎？ – helpermethod 2010-07-26 15:35:02

@Helper方法：你的java impl的供應商是什麼？在sun jdk中，我看到了提到的這一行。 – Roman 2010-07-26 15:38:54

我正在使用Sun JDK 1.6.0-b105。 – vcosk 2010-07-26 16:07:54

JavaDoc中唯一的保證是添加一個新元素具有不變的分攤時間。這意味着將新元素添加到數組的平均時間是不變的。有時可能需要更長一點的時間（比如嘗試調整數組大小時），但總體而言，這些情況非常罕見，因爲它不會過多地影響平均值。

因此，爲了讓他們能夠尊重這一保證，他們需要確保調整大小的時間不足以影響平均加入時間。出於這個原因，他們使用新容量的當前容量的百分比。如果調整大小會像oldCapacity + 50那樣，那麼數組對於小數組列表來說可能太大，但如果要添加幾千個元素，則調整每50個元素的大小會降低性能。通過這種方式，容量呈指數級增長（如果您已經添加了很多元素，則可能會添加更多元素，因此它們會增加容量），因此不會降低性能。至於他們爲什麼選擇50％，或許他們認爲容量翻倍（或更多）可能會過度（會爲非常大的ArrayLists消耗太多額外內存），並且變得太低（可能是10-25％）會太多地降低性能（通過執行太多重新分配），因此可能+ 50％提供足夠好的性能，而不會佔用太多的額外內存。我猜他們在決定價值之前做了一些性能測試。

來源

2010-07-26 15:49:09

+1非常好的解釋。我認爲Effective Jave也提到了算法，但我現在找不到它。 – helpermethod 2010-07-26 18:49:09

感謝您的解釋。我正在研究一個有時間限制的問題，而且當STL向量以相同的算法成功時，java ArrayList總是失敗。它引導我進行這樣的討論：Java正在使用STL向量正在使用的不同擴展策略（使容量翻倍）。我承認容量翻倍可能會消耗更多的額外內存，但+ 50％會導致更頻繁的增長率（log_2 - > log_ {3/2}）。整個運行時間仍然會被分攤到每個插入的O（1），但是在java ArrayList之後的常量要比stl向量高得多。 – arosima 2012-12-30 00:55:15

任何想法爲什麼他們做了「（oldCapacity * 3）/ 2 + 1」和Not（oldCapacity * 1.5）+ 1？ – 2014-11-02 17:27:13

它通過每次調用時50％生長的名單，以防止過早地分配世界。 + 1旨在捕獲列表初始化的情況，其大小爲1 :)

來源

2010-07-26 15:33:40 rsp

'+1'部分的好解釋，直到閱讀你的建議纔得到它。 – Roman 2010-07-26 15:35:36

好的，但爲什麼不是（oldCapacity * 12）/ 5 + 1？增加50％背後有邏輯嗎？ – 2010-07-26 15:39:14

@Ronald我會想象這個想法是將這個列表擴大到合理的大小。 50％顯然有些武斷。 – 2010-07-26 15:47:38

ArrayList中ensureCapacity方法中使用的邏輯

回答

相關問題