开篇之前, 想想下面几个问题的答案是什么? 有的时候我们看源码也是, 并不是说一味盲目的直接跑到源码中去看, 我们带着这几个问题去阅读源码, 反而会轻松许多
- ArrayList 的大小是如何自动增加的？
- 什么情况下你会使用ArrayList？什么时候你会选择LinkedList？
- ArrayList 的扩容机制
- 几个重要的参数, 以及构造方法
ArrayList 是我们在开发中高频率使用到的一个基于数组实现的一个有序的集合类, 那下面就简单的从平常是如何使用的, 做源码分析如下, 也了解一下上面几个经常被问到的问题, 做一个解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
List<String> arrayList = new ArrayList<>();
arrayList.add("1");
arrayList.add("3");
arrayList.add("2");
arrayList.add("4");
arrayList.add("5");
arrayList.get(1);
arrayList.remove(2);
ArrayList<String> arrayList2 = new ArrayList<>();
arrayList2.add("2");
arrayList2.add("3");
arrayList.containsAll(arrayList2);
arrayList.removeAll(arrayList2); |
几个重要的构造
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
/**
* Default initial capacity. 默认大小容量为 10 的大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 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 = {};
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial 当前 ArrayList 的容量实时的容量大小
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
// 给定初始容量大小的构造
if (initialCapacity > 0) {
// 创建一个 initialCapacity 大小的 Object 对象数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
// 无参数的构造方法
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
} |
首先从 ArrayList 的继承的结构体系中, 可以大小了解到一些信息, 继承了一个抽象类 AbstractList, 这里就不展示他的源码了, 其实这个类里面并没有做什么操作, 只是简单的定义了一些方法, 他是一个模板设计模式, 然后实现了 RandomAccess, Cloneable, java.io.Serializable , 随机访问接口, 可克隆, 序列化接口
然后可以发现初始值容量大小为 10, ArrayList 底层是用 Object 对象数组来实现的, 然后是无参和有参的构造方法, 这个仅仅是对 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值操作, 和创建一个 new Object[initialCapacity] 大小的数组
往集合中添加元素
1 2 3 4 5 6 7 |
public boolean add(E e) {
// 确保容量大小, (其中扩容机制也在这个方法中实现的)
ensureCapacityInternal(size + 1); // Increments modCount!!
// 元素放入 Object 对象数组中
elementData[size++] = e;
return true;
} |
1 2 3 4 5 6 7 8 9 10 |
private void ensureCapacityInternal(int minCapacity) {
// 当我们使用无参数构造的时候, 第一次被 add 添加元素的时候, 这个调节是肯定成立的, 因为在上面的无参构造中就是对这个赋值操作
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 初始化了容量为大小为 10 的大小
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 确保容量大小
ensureExplicitCapacity(minCapacity);
} |
1 2 3 4 5 6 7 8 9 |
private void ensureExplicitCapacity(int minCapacity) {
// 被修改的次数增加, 这个主要是一个并非修改异常, 这个后面会讲到
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 扩容
grow(minCapacity);
} |
假设上面, 我们是第一次 add 添加元素, 那么 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个条件成立, 然后初始化容量大小为 10 的数组, 那么到了这个条件 if (minCapacity - elementData.length > 0) 只要是小于 10 的就不会触发扩容, 那么如果是再添加一个, 那么传递下来的参数就是 11-10=1 那么这个条件成立, 那么就会触发扩容了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
private void grow(int minCapacity) {
// overflow-conscious code
// 假设这里的 minCapacity 为 11 触发扩容机制
// 原数组大小是 10
int oldCapacity = elementData.length;
// 赋值新的容量大小, 15 = 10 + (10/2)
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);
} |
上面就是扩容机制的代码了, 可以发现很简单, 就是等于 原数组的长度 + 原数组长度 1⁄2, 然后就是数组的拷贝了 Arrays.copyOf(elementData, newCapacity)
Arrays.copyOf()
1 2 3 |
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
} |
1 2 3 4 5 6 7 8 9 10 11 12 |
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
// 创建一个新的对象
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 系统底层使用 c 实现的数组拷贝
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
// 将对象返回
return copy;
} |
好了, 添加元素操作的源码到这里基本没有了, 到了这里我们知道了扩容机制其实就是扩容原数组的 1.5 倍的大小, 其实也就是说 ArrayList 是一个动态扩容数据, 然后对创建新的数据, 对老的数组进行copy, 这个是会消耗一部分的性能的, 这里给出一个假设, 假设你当前的数组容量为 100, 那么可想而知, 数组会发生好几次的拷贝, 所以当我们知道了数组的容量大小的时候, 最好是直接给定, 防止多次拷贝
获取数据
1 2 3 4 5 6 7 |
public E get(int index) {
// index 索引值大于当前数组, 抛出越界异常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
} |
删除元素
根据下标删除数据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
public E remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); // 修改次数加1, 这个主要是一个并非修改异常, 这个后面会讲到 modCount++; // 需要删除的元素 E oldValue = (E) elementData[index]; // 数组要移动的次数 int numMoved = size - index - 1; if (numMoved > 0) // 发生数组移动, 也就是拷贝 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 堆中数据置为 null, 让 GC 可以回收 elementData[--size] = null; // clear to let GC do its work return oldValue; }根据元素内容删除数据
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
public boolean remove(Object o) { if (o == null) { // 删除为 null 的元素 for (int index = 0; index < size; index++) if (elementData[index] == null) { // 删除元素, 本质上是数组拷贝, 位置发生偏移 fastRemove(index); return true; } } else { // for 循环遍历查找元素的内容, 将其删除, 位置发生偏移 for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { // 删除元素, 本质上是数组拷贝 fastRemove(index); return true; } } return false; }
修改元素
1 2 3 4 5 6 7 8 9 10 11 12 |
public E set(int index, E element) {
// 越界异常检查
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 旧的元素
E oldValue = (E) elementData[index];
// 新的元素, 赋值给旧的元素
elementData[index] = element;
// 然后将旧的元素返回
return oldValue;
} |
这里, 由于是数组实现的 ArrayList, 内存地址是连续的, 可基于下标直接访问元素, 这里回到文章开头提到的问题, 在什么情况下使用 ArrayList 什么情况下使用 LinkedList, 这就要看我们的需求是元素是访问多, 还是元素删除多, 访问多的用 ArrayList, 由于 LinkedList 是用链表实现的, 内存地址不连续, 当前节点保存上一个节点和下一个节点, 当要删除元素时候, 直接指针改变指向就可以了, 所以删除多用 LinkedList
最后看几个比较有意思的, 算法写的很好, 平时在我用开发中也会经常用的到, 可以作为参考
提出问题: 假设目前有一个数组 [1,2,3,4,5] 和 [2,3], 要求是移除相同的元素, 或者是保留相同的元素, 不使用下面的方法, 自己手写的话, 你会怎么写?
删除相同的元素, 不相同元素的返回
1 2 3 4
public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); }返回相同的元素, 不相同的元素删除掉
1 2 3 4
public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); }稍微留意一下, 这两个方法都是相同的, 仅仅是一个参数的不同
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; // 类似读(read)指针, 和一个写(write)指针 int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) // for 循环遍历 /** * 1.r 一直自增加, 当 complement 为 true 的时候, * 条件成立, w++, 当前相同的元素赋值给 w++ 下标元素 * 最后完后所有的操作, 最终就是 [2,3] */ /** * 2.r 一直自增加, 当 complement 为 false 的时候, * 条件成立, w++, 当前相同的元素赋值给 w++ 下标元素 * 最后完后所有的操作, 最终就是 [1,4,5] */ if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // 最终一定会被执行 // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. // 上面如果执行了操作, 这个值是相等的 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // 条件成立 /** * 假设是条件 1, w 是 2, 那么就将 2 下标后面的元素都删除 * 假设是条件 2, w 是 3, 那么就将 3 下标后面的元素都删除 */ if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; // 将元素置为null, 让 GC 可以回收 // 被修改的次数 modCount += size - w; // 赋值最新的 size 容量大小 size = w; modified = true; } } return modified; }
好了, 源码中写了注释, 用了一个类似, 读指针和写指针的东西, 很巧妙的完成了查找相同元素, 或者是移除相同元素, nice