Java性能調優之容器擴容問題
在Java和Android編程中，我們經常使用類似ArrayList,HashMap等這些容器。這些容器少則存儲幾條，多則上千甚至更多。作為性能調優的一部分，容器調優往往被我們忽略，本文將嘗試探索闡述一些關于容器調優中的擴容問題。雖然以Java為例，但是也同樣適用于其他編程語言。
首先以我們最常用的ArrayList為例，它是一個基于數組的List實現。
public static void main(String[] args) {
ArrayList<Object> collection = new ArrayList();
for (int i = 0; i< 1000; i++) {
collection.add(new Object());
}
}
以上代碼很簡單，不用贅述。那我們使用NetBeans的profile插件 來看一下關于Object對象分配的stacktrace
從stacktrace中，我們可以發現
- Object對象trace始于ArrayList.add方法
- 經過了一個叫做ArrayList.grow方法
以上我們可以推斷，ArrayList對象發生了擴容操作。因為使用無參的構造方法，會初始化一個存儲容量為0的數組。
如下代碼為ArrayList的構造方法
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
然而想要容量1000個Object實例，這個過程中則需要不斷的擴容,在這個過程中發生了以下幾點
- 確定新的容量，并以新容量為大小創建新的數組
- 將舊數組的數據拷貝到新數組中
- 舊的數組將會后續被GC回收掉
除此之外，擴容還會增加CPU高速緩存的 未 命中率。因為
在JVM中，一般來說，由于對象和其字段常常都需要同時引用，將對象和其字段盡可能放在內存中相鄰位置能夠減少CPU高速緩存的未命中率。
而ArrayList擴容后的新數組可能不在于該對象相鄰，所以擴容理論上會增加CPU高速緩存的未命中率。
注意：上面提到的都是CPU高速緩存的未命中率，不是命中率。
更容易擴容的HashMap
HashMap作為一個高效的key-value的容器，內部也維護了一個Entry數組，也存在擴容的問題。
然而，HashMap為了更加有效的避免數組沖突，引入了兩個概念。
- threshold 閾(yu，四聲)值，當內部數據占用量超過這個值，進行擴容。
- loadFactor 通常為0.75,用來計算threshold值，即threshold = 容量 * loadFactor
舉個例子
- 創建一個HashMap設置初始化容量為16，使用默認的loadFactor 0.75，即threshold為12
- 然后不斷的填充key,value數據
- 當內部數據占用量超過12時，就會觸發擴容操作，而不是等到16的時候。
- 通常的擴容為雙倍擴容，即變成原來的兩倍，這里為32.
因此說HashMap更容易觸發擴容，但是這其實是一種在hash與容量占用的一種平衡。
如何解決或者改善擴容問題
使用預設較為合理的初始容量
SQLiteDatabase提供了方便的ContentValues簡化了我們處理列名與值的映射，ContentValues內部采用了HashMap來存儲Key-Value數據，ContentValues的初始容量是8，如果當添加的數據超過8之前，則會進行雙倍擴容操作，
因此建議對ContentValues填入的內容進行估量，根據實際需要的字段數量，設置合理的初始化數量。
嘗試使用其他非基于數組的數據結構
數組的一大優點就是隨機訪問很高效，這是鏈表所無法匹敵的。
但是并不是所有的時候都數組都有明顯優勢
- 不需要隨機訪問或者數據量很小
- 在頻繁的增加和刪除數據的時候，鏈表有明顯的優勢。
一些替代方案
- 對于List，可以考慮使用LinkedList
- 對于Map，可以考慮使用TreeMap
- 關于替代HashMap，Android引入了一個叫做ArrayMap的類，用來解決HashMap內存占用的問題。
關于擴容的問題就是以上內容，當我們無論是使用任何數據結構時都需要考慮到具體的環境和需要，確保能夠做到最優。
來自：http://droidyue.com/blog/2017/03/05/java-performance-tuning-collection-size-growth/