文章目录
- List扩容
- ArrayList 扩容机制
- 结论:无参构造创建的ArrayList的初始空间为0,在添加第一个元素的时候空间会默认为10,之后扩容会为当前容量的1.5倍。
- 0->10->15->22->33->49
- 源码分析
- 1.ArrayList list = new ArrayList();
- 2. list.add(1);
- Vector 扩容机制
- 结论:无参构造默认空间为10,每次扩大一倍。
- 源码分析
- LinkedList 扩容机制
- 结论:LinkedList是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
- 其他问题
- 扩容后的size是多少?还是实际元素大小
- 给了初始值,它会给我自动扩充为10、15、22......吗?不会
List扩容
ArrayList 扩容机制
结论:无参构造创建的ArrayList的初始空间为0,在添加第一个元素的时候空间会默认为10,之后扩容会为当前容量的1.5倍。
0->10->15->22->33->49
演示代码
public static void main(String[] args) {ArrayList list = new ArrayList();for (int i = 0; i <= 9; i++) {list.add(i);}list.add(10);list.add(11);list.add(12);
}
第一次调试截图:此时ArrayList内未添加任何元素,默认为0;
第二次调试截图:当向ArrayList中添加第一个元素的时候,空间变为10。
10条插入完后,再插入就会变成15
这是第二次扩容为,扩容为15
再继续插入16个,扩容为22
第三次扩容22
源码分析
1.ArrayList list = new ArrayList();
会调用无参构造器,新建一个ArrayList。将elementData设置为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
通过源码,我们知道DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的数组。
/*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
2. list.add(1);
将1进行Integer包装
public static Integer valueOf(int i) {if (i >= IntegerCache.low && i <= IntegerCache.high)return IntegerCache.cache[i + (-IntegerCache.low)];return new Integer(i);}
通过add类进行元素添加
/*** 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) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}
通过ensureCapacityInternal方法来确保容量足够,此处的Math.max(DEFAULT_CAPACITY, minCapacity);就是确保第一次扩容空间为10
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}
ensureCapacityInternal方法会调用ensureExplicitCapacity方法来确保空间,modCount用来多线程的判断,此处不赘述
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}
ensureExplicitCapacity方法会调用grow方法,扩容1.5倍,就是在此发生的。 int newCapacity = oldCapacity + (oldCapacity >> 1);
/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint 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);}
Vector 扩容机制
结论:无参构造默认空间为10,每次扩大一倍。
如下代码
public class ArrayExercise {public static void main(String[] args) {Vector vector = new Vector();for (int i = 0; i < 10; i++) {vector.add(i);}vector.add(10);vector.add(11);vector.add(12);}
}
调试过程略。
源码分析
初始化会默认调用无参,再调用有参数构造器,空间默认10。
/*** Constructs an empty vector so that its internal data array* has size {@code 10} and its standard capacity increment is* zero.*/public Vector() {this(10);}
扩容的主要操作在grow中的int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
方法,capacityIncrement默认是0,所以等价newCapacity=oldCapacity+oldCapacity
;
/*** Appends the specified element to the end of this Vector.** @param e element to be appended to this Vector* @return {@code true} (as specified by {@link Collection#add})* @since 1.2*/public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}
LinkedList 扩容机制
结论:LinkedList是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
其他问题
扩容后的size是多少?还是实际元素大小
调试下我们可以发现,虽然elementData进行了扩容,但是实际大小还是元素的个数,别被唬住了
给了初始值,它会给我自动扩充为10、15、22…吗?不会
别激动,给多少就是多少