目录
前言
源码解析
基本成员变量
添加元素
查询元素
修改元素
删除元素
为什么用 "transient" 修饰数组变量
总结
前言
今天学习一个 Java 集合类使用最多的类 ArrayList , ArrayList 继承了 AbstractList, 并实现了 List 和 RandomAccess 等接口,
- public class ArrayList<E> extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable
是一个以数组形式存储数据的集合, 它具有以下的特点:
集合中的数组是有序排列的;
允许元素为 null;
允许重复的数据;
非线程安全;
针对它的这些特点, 我们一步步跟进源码进行解析.
源码解析
基本成员变量
先看下 ArrayList 的基本成员变量
- transient Object[] elementData;
- private static final int DEFAULT_CAPACITY = 10;
- private int size;
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
elementData : 一个 object 数组, 组成了 ArrayList 的底层数据结构, 由于数组类型为 Object, 所以允许添加 null . 值得注意的是, 变量的修饰符是 transient , 这说明这个数组无法被序列化, 但是之前 ArrayList 却实现了序列化接口, 是可以被初始化, 这不是互相矛盾了吗, 关于这个原因, 下面会说到, 别急.
DEFAULT_CAPACITY : 数组的初识容量
size : 数组元素个数
MAX_ARRAY_SIZE: 数组最大容量
说完变量后, 开始学习 ArrayList 的基本方法, 我们都知道, 一个集合最重要的方法就是对元素的 增删改查操作, 了解了这些操作的方法, 也就基本了解了容器的运作机制.
添加元素
ArrayList 中最基础的添加元素方法是 add(E e)
- public boolean add(E e) {
- // 调整容量
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
源码逻辑比较简单, 主要是先做了调整容量处理, 并把元素存入数组的最后一个位置.
来看一下调整容量的方法 ensureCapacityInternal(), 源码如下:
- private void ensureCapacityInternal(int minCapacity) {
- // 如果是空数组, 初始化容量, 取默认容量和 当前元素个数 最大值
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- // 容量不够, 做扩容
- grow(minCapacity);
- }
- private void grow(int minCapacity) {
- // overflow-conscious code
- 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);
- // minCapacity is usually close to size, so this is a win:
- // 将元素组里面的内容复制到新的数组里面去
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
可以看到, 调整容量的过程其实是扩容了数组的容量, 并在最后调用了 Arrays 的 copyOf 方法 , 等于把元素组里面的内容复制到新的数组里面去,
- 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);
- System.arraycopy(original, 0, copy, 0,
- Math.min(original.length, newLength));
- return copy;
- }
用一张图来表示是这样的
除了上面的 add 方法外, ArrayList 还提供了几个添加操作的方法, 分别是
- // 在指定位置添加元素
- public void add(int index, E element) {
- // 判断 index 是否在 size 范围内
- rangeCheckForAdd(index);
- ensureCapacityInternal(size + 1); // Increments modCount!!
- // 整体复制, 并后移一位
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- elementData[index] = element;
- size++;
- }
- // 添加整个集合
- public boolean addAll(Collection<? extends E> c) {
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacityInternal(size + numNew); // Increments modCount
- System.arraycopy(a, 0, elementData, size, numNew);
- size += numNew;
- return numNew != 0;
- }
- // 在指定位置, 添加一个集合
- public boolean addAll(int index, Collection<? extends E> c) {
- rangeCheckForAdd(index);
- // 把该集合转为对象数组
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacityInternal(size + numNew); // Increments modCount
- int numMoved = size - index;
- if (numMoved> 0)
- System.arraycopy(elementData, index, elementData, index + numNew,
- numMoved);
- System.arraycopy(a, 0, elementData, index, numNew);
- size += numNew;
- return numNew != 0;
- }
这三个方法虽然也是插入的操作, 但其实最后都是调用 System 的 arraycopy 方法做一个整体的复制, 这是一个 native 的方法, 功能就是把数组做一个整体的复制, 并向后移了一位. 如果要复制的元素很多, 那么就比较耗费性能, 这是比较不好的一点.
所以, 一般情况下, ArrayList 适合顺序添加的情景.
查询元素
- E elementData(int index) {
- return (E) elementData[index];
- }
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
查询的代码比较简单, 都是直接返回数组对应位置的元素, 充分利用了数组根据索引查询元素的优势吗, 因此效率较高.
扩展: 说到查询, 来提一个知识点, 那就是遍历元素的效率问题, 前面说了, ArrayList 实现了 RandomAccess 接口, 所以 遍历 ArrayList 的元素 get() 获取元素在效率上是优于迭代器的, 至于原因, 在 《Java 集合类:"随机访问" 的 RandomAccess 接口》有介绍, 这里不进行叙述了.
修改元素
- public E set(int index, E element) {
- rangeCheck(index);
- E oldValue = elementData(index);
- elementData[index] = element;
- return oldValue;
- }
也是根据索引操作数组 , 不多说.
删除元素
ArrayList 删除元素的方法比较多, 但说起来无非是三类,
1, 按照下标删除元素
2, 按照元素删除, 这会删除 ArrayList 中与指定要删除的元素匹配的第一个元素
3, 清除数组元素
前面两种虽然功能不同, 但代码的最终调用是差不多的, 都是引用类似这段代码来解决问题:
- 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
这段代码的逻辑大概就是把指定元素后面的所有元素整体复制并向前移动一个位置, 然后最后一个元素置为 null, 跟插入中的部分方法逻辑很像, 都是调用 System.arraycopy 来做数组操作, 所以说, 删除元素的效率其实也是不高的.
而第三类删除的方法其实是调用 clear ,
- public void clear() {
- modCount++;
- // clear to let GC do its work
- for (int i = 0; i < size; i++)
- elementData[i] = null;
- size = 0;
- }
把数组的每个元素都置为 null, 并把 size 置为 0, 就这么简单.
为什么用 "transient" 修饰数组变量
最后一个问题, 之前说了 ArrayList 可以被序列化, 但其数组变量却是用 transient 修饰, 这是为什么呢? 按照 五月的仓颉 大神这篇文章的解释就是:
序列化 ArrayList 的时候, ArrayList 里面的 elementData 未必是满的, 比方说 elementData 有 10 的大小, 但是我只用了其中的 3 个, 那么是否有必要序列化整个 elementData 呢? 显然没有这个必要, 因此 ArrayList 中重写了 writeObject 方法:
- private void writeObject(java.io.ObjectOutputStream s)
- throws java.io.IOException{
- // Write out element count, and any hidden stuff
- int expectedModCount = modCount;
- s.defaultWriteObject();
- // Write out size as capacity for behavioural compatibility with clone()
- s.writeInt(size);
- // Write out all elements in the proper order.
- for (int i=0; i<size; i++) {
- s.writeObject(elementData[i]);
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
每次序列化的时候调用这个方法, 先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素, elementData 不去序列化它, 然后遍历 elementData, 只序列化那些有的元素, 这样:
1, 加快了序列化的速度
2, 减小了序列化之后的文件大小
不得不说, 设计者还是很用心良苦的.
总结
ArrayList 的源码分析就到这里了, 因为其底层只有数组, 所以源码的逻辑还是比较简单, 比起 HashMap 这样的学习起来要轻松多了 (HashMap 源码学习过程回想起来真是痛苦啊) , 下面总结一下它的一些知识点:
1,ArrayList 的插入删除操作比较慢, 因为涉及到整个数组的复制和移动操作.
2, 因为是数组, 支持随机访问, 所以查询和修改的速度较快
3,ArrayList 的方法里没有做同步操作, 所以 ArrayList 是非线程安全的, 一般使用的时候可以调用 Collections.synchronizedList 来包装.
来源: https://www.cnblogs.com/yeya/p/9955555.html