最近在复习线性数据结构的时候，顺便拿了Java的ArrayList做了分析比较。ArrayList的本质是动态数组，当新加如的数据逼近数组容量时，自动扩容，删除数据后，自动收缩。这么做，虽然效率比较低，但是一定程度上能优化内存分配。
自动扩容
ArrayList内部有个elementData的Object数组，初始容量在Java 8中为10。当第11个数据需要添加时候，扩容1.5倍。这个1.5倍在ArrayList很巧妙，用了整数移位的方式。
1
int newCapacity = oldCapacity + (oldCapacity >> 1);
完整的扩容代码是：
1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
数组收缩
收缩数组的目的是为了节省内存，但是牺牲了时间。比如每一次的删除元素，都会触发一次System.arraycopy重写elementData，移动数组下标，再给无效的下标数据置空，隐式地等待gc清理。
1
2
3
4
5
6
7
8
9
10
11
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
另外，ArrayList还提供了一个显式的收缩方法trimToSize，将elementData的容量大小（elementData.length）收缩为实际大小（ArrayList.size()）。
1
2
3
4
5
6
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = Arrays.copyOf(elementData, size);
}
}
内存分析
我用一段代码来查看ArrayList的实际size和capacity。由于capacity的大小就是elementData的数组大小，而elementData是内部数组，无法访问到，所以我设法采用reflection获取。
1
2
3
4
5
6
7
8
9
10
static int getCapacity(ArrayList<?> list) {
try {
Field dataField = ArrayList.class.getDeclaredField("elementData");
dataField.setAccessible(true);
return ((Object[]) dataField.get(list)).length;
} catch (Exception e) {
e.printStackTrace();
return -1;
}
}
而获取size直接用size()
这段代码的逻辑是：
- 填充1000个数据
- 获取size和capacity
- 导出heap dump
- trimToSize收缩
- 获取capacity
- 再次导出heap dump
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ArrayList<String> list = new ArrayList<String>();
int ii=15;
ii = ii>> 1;
System.out.println(ii);
for(int i=0; i<1000; i++){
list.add("hello-" + i);
}
System.out.println("size: " + list.size());
System.out.println("capacity: " + getCapacity(list));
try {
Thread.sleep(1000*30);
} catch (InterruptedException e) {}
// capture heap dump 1
list.trimToSize();
System.out.println("capacity after trim: " + getCapacity(list));
System.gc();
try {
Thread.sleep(1000*3600);
// capture heap dump 2
} catch (InterruptedException e) {}
输出结果很简单：
1
2
3
size: 1000
capacity: 1234
capacity after trim: 1000
分析收缩前后的两次内存堆，发现elementData数组的大小差异为1234-1000=234，而shallow size和retained size都是936字节。
1
2
shallow size: 4952 - 4016 = 936
retained size: 68152 - 67216 = 936
这936字节的差异就是数组中扩容后产生的234个Object空引用。一个对象引用是4字节，shallow和retained size需要8字节对齐，所以：
1
2
234 * 4 = 936
936 % 8 = 0，所以不需要填充对齐