动态扩容
1,add(E e) 方法中
1 ensureCapacityInternal(size+1), 确保内部容量, size 是添加前数组内元素的数量
2 elementData[size++] = e 添加元素到相应位置, 元素数量加 1
2, ensureCapacityInternal(size+1) 确保内部容量
1 计算最小需要空间 (如果传入的是个空数组则最小容量取默认容量与 minCapacity 之间的最大值)
2 判断是否需要扩容 (如果最小需要空间比 elementData 的内存空间要大, 则扩容)
3, 扩容 grow(int minCapacity)
newCapacity=oldCapacity + (oldCapacity>> 1), 原来元素数量的 1.5 倍
再与最小需要空间比较, 与最大数组长度比较
一 初始化
先看一下 ArrayList 的两个构造方法
- public ArrayList() {
- this.elementData = 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);
- }
- }
在无参构造中, 我们看到了在用无参构造来创建对象的时候其实就是创建了一个空数组, 长度为 0
在有参构造中, 传入的参数是正整数就按照传入的参数来确定创建数组的大小, 否则异常
二 确保内部容量
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
1 ensureCapacityInternal 方法名的英文大致是 "确保内部容量",size 表示的是执行添加之前的元素个数,
并非 ArrayList 的容量, 容量应该是数组 elementData 的长度. ensureCapacityInternal 该方法通过将现有的元素个数与数组的容量比较. 看如果需要扩容, 则扩容.
2是将要添加的元素放置到相应的数组中.
可以看出 ensureCapacityInternal() 是用来扩容的, 形参为最小扩容量, 进入此方法后:
- private void ensureCapacityInternal(int minCapacity) {
- ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
- }
通过方法 calculateCapacity(elementData, minCapacity) 获取最小需要空间
- private static int calculateCapacity(Object[] elementData, int minCapacity) {
- // 如果传入的是个空数组则最小容量取默认容量与 minCapacity 之间的最大值
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- return minCapacity;
- }
ensureExplicitCapacity 方法可以判断是否需要扩容:
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // 如果最小需要空间比 elementData 的内存空间要大, 则需要扩容
- if (minCapacity - elementData.length> 0)
- // 扩容
- grow(minCapacity);
- }
三 扩容
ArrayList 扩容的关键方法 grow():
- private void grow(int minCapacity) {
- // 获取到 ArrayList 中 elementData 数组的内存空间长度
- int oldCapacity = elementData.length;
- // 扩容至原来的 1.5 倍
- int newCapacity = oldCapacity + (oldCapacity>> 1);
- // 再判断一下新数组的容量够不够, 够了就直接使用这个长度创建新数组,
- // 不够就将数组长度设置为需要的长度
- if (newCapacity - minCapacity <0)
- newCapacity = minCapacity;
- // 若预设值大于默认的最大值检查是否溢出
- if (newCapacity - MAX_ARRAY_SIZE> 0)
- newCapacity = hugeCapacity(minCapacity);
- // 调用 Arrays.copyOf 方法将 elementData 数组指向新的内存空间 newCapacity 的连续空间
- // 并将 elementData 的数据复制到新的内存空间
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity <0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity> MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
- int newCapacity = oldCapacity + (oldCapacity>> 1);
oldCapacity>> 1 右移运算符 原来长度的一半 再加上原长度也就是每次扩容是原来的 1.5 倍
之前的所有都是确定新数组的长度, 确定之后就是把老数组 copy 到新数组中, 这样数组的扩容就结束了
### 每次扩容都是通过 Arrays.copyOf(elementData, newCapacity) 这样的方式实现的. ArrayList 的自动扩容机制底层借助于 System 实现 System.arraycopy(0,oldsrc,0,newsrc,length);
扩展: System 源码中的 arraycopy() 标识为 native 意味 JDK 的本地库, 不可避免的会进行 IO 操作, 如果频繁的对 ArrayList 进行扩容, 毫不疑问会降低 ArrayList 的使用性能, 因此当我们确定添加元素的个数的时候, 我们可以事先知道并指定 ArrayList 的可存储元素的个数, 这样当我们向 ArrayList 中加入元素的时候, 就可以避免 ArrayList 的自动扩容, 从而提高 ArrayList 的性能.
来源: https://www.cnblogs.com/moershiwei/p/12637968.html