本片我们分析基础数组的实现 --ArrayList, 不会分析整个集合的继承体系, 这不是本系列文章重点.
源码分析都是基于 "安卓版" 的源码, 和 java 原生版核心思想都是差不多的. 好了, 废话依然少说, 进入正文.
一, ArrayList 中成员变量
源码:
- /**
- * The minimum amount by which the capacity of an ArrayList will increase.
- * This tuning parameter controls a time-space tradeoff. This value (12)
- * gives empirically good results and is arguably consistent with the
- * RI's specified default initial capacity of 10: instead of 10, we start
- * with 0 (sans allocation) and jump to 12.
- */
- private static final int MIN_CAPACITY_INCREMENT = 12;
- /**
- * The number of elements in this list.
- */
- int size;
- /**
- * The elements in this list, followed by nulls.
- */
- transient Object[] array;
第 8 行 MIN_CAPACITY_INCREMENT 的作用通过注释就大体可以知道了, 主要就是用来控制内部维护的数组每次扩容时的大小, 后面分析具体方法时会多次看到其身影.
第 13 行 size 就是内部维护的数组中元素的个数了, 没什么多余解释的.
第 18 行 array 就是内部盛放数据的数组了, 我们加入的数据就放到这里.
二, ArrayList 构造方法与初始化
初始化方法有三个, 源码如下:
- /**
- * Constructs a new {@code ArrayList} instance with zero initial capacity.
- */
- public ArrayList() {
- array = EmptyArray.OBJECT;
- }
- /**
- * Constructs a new instance of {@code ArrayList} with the specified
- * initial capacity.
- *
- * @param capacity
- * the initial capacity of this {@code ArrayList}.
- */
- public ArrayList(int capacity) {
- if (capacity <0) {
- throw new IllegalArgumentException("capacity < 0:" + capacity);
- }
- array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
- }
- /**
- * Constructs a new instance of {@code ArrayList} containing the elements of
- * the specified collection.
- *
- * @param collection
- * the collection of elements to add.
- */
- public ArrayList(Collection<? extends E> collection) {
- if (collection == null) {
- throw new NullPointerException("collection == null");
- }
- Object[] a = collection.toArray();
- if (a.getClass() != Object[].class) {
- Object[] newArray = new Object[a.length];
- System.arraycopy(a, 0, newArray, 0, a.length);
- a = newArray;
- }
- array = a;
- size = a.length;
- }
4-6 行, 调用空参数的构造方法就是初始化一个空的 array 数组.
15-20 行, 初始化的时候我们可以指定一个大小的数值, 如果小于 0 则会抛出异常, 为 0 就和调用空参数构造方法一样了, 大于 0, 则初始化一个对应大小的 array 数组. 调用此方法我们可以初始化的时候就指定 array 数组的大小, 如果我们事先知道放入元素个数, 那么可以调用此方法初始化的时候就指定好内部 array 数组大小, 省去后续不断放入元素扩容的操作.
29-42 行, 初始化的时候我们同样也可以传入一个集合:
30-32 传入集合为 null, 则报空指针异常.
34 行, 集合 collection 转为 Object 数组.
35 行, 判断 a 的字节码类型是否为 Object[].class 类型, 这里注意 toArray() 方法实际返回的不一定是 Object[] 类型数组, 具体返回由具体的 Collcetion 子类自己去实现 toArray() 方法. 这里只是用 Object[] 类型数组接收 toArray() 返回的数据.
如果返回的字节码类型不是 Object[] 则进入 36-38 行逻辑
36 行, 根据集合大小创建一个同样大小的 Object[] 类型 newArray 数组.
37 行, 就是数组的拷贝了, 调用 System.arraycopy 方法将数组 a 从 0 位置开始, 拷贝到 newArray 数组位置同样从 0 开始, 并且拷贝数据长度为 a.length.System.arraycopy 方法一定要弄明白, 后续主要用这个方法对数组进行操作.
经过 37 行, collection 中数据就都拷贝到数组 newArray 中了.
38 行, newArray 赋值给数组 a.
40-41 行, a 赋值给 array 变量, size 变量记录数据大小.
以上就是三种创建 ArrayList 的方式, 比较简单. 继续往下看
三, ArrayList 中 add 方法源码分析
添加操作主要有四个方法供我们使用, 如下:
- public boolean add(E object)// 添加一个元素
- public void add(int index, E object)// 向指定位置添加一个元素
- public boolean addAll(Collection<? extends E> collection)// 添加一个集合
- public boolean addAll(int index, Collection<? extends E> collection)// 向指定位置添加一个集合
接下来, 逐个分析
add(E object) 源码:
- public boolean add(E object) {
- Object[] a = array;
- int s = size;
- if (s == a.length) {
- Object[] newArray = new Object[s +
- (s <(MIN_CAPACITY_INCREMENT / 2) ?
- MIN_CAPACITY_INCREMENT : s>> 1)];
- System.arraycopy(a, 0, newArray, 0, s);
- array = a = newArray;
- }
- a[s] = object;
- size = s + 1;
- modCount++;
- return true;
- }
这里最核心的就是有个扩容操作, 加入元素的时候如果容器已满则进行 5-7 行扩容逻辑.
扩容方式为: 若容量小于 6 则增加 12, 否则 1.5 倍扩容.
关于扩容这里有两种策略, 时间换空间和空间换时间, 比如我可以一次扩容很大, 这样不断加入元素的时候就省去每次扩容所花费的时间了, 同样, 也可以每次就扩容那么多, 放入一个元素我就扩容 1, 放入 10 个元素我就扩容 10, 这样节省了空间但是每次都要扩容从而牺牲了时间. 而谷歌工程师在这里考虑了时间空间的平衡, 既不扩容很大也照顾扩容次数, 个人感觉这里没有一个完美解决方案, 个设计者个人喜好也有一定关系.
8 行, 又是数组的拷贝了, 原来数组元素全部拷贝到新数组 newArray.
11-12 行, 元素放入数组以及元素个数加一, 没什么要解释的.
13 行, 记录操作次数.
add(int index, E object) 源码:
- public void add(int index, E object) {
- Object[] a = array;
- int s = size;
- if (index> s || index <0) {
- throwIndexOutOfBoundsException(index, s);
- }
- if (s < a.length) {
- System.arraycopy(a, index, a, index + 1, s - index);
- } else {
- // assert s == a.length;
- Object[] newArray = new Object[newCapacity(s)];
- System.arraycopy(a, 0, newArray, 0, index);
- System.arraycopy(a, index, newArray, index + 1, s - index);
- array = a = newArray;
- }
- a[index] = object;
- size = s + 1;
- modCount++;
- }
8 行, 首先判断数组中元素个数是否小于数组长度, 其实就是判断数组是否已经填满, 没填满, 则代表可以直接放入数据, 不容扩容.
9 行, 同样是数组的拷贝, 这里拷贝需要自己小小的计算一下了, 其实就是将 index 开始的元素拷贝到 index+1 开始的位置, 把 index 位置空出来.
如果已经填满数据, 则就需要扩容操作了.
12 行, 创建一个新数组, 数组大小为 newCapacity(s), 自己看一下就可以了, 和上面扩容逻辑一样.
13-14 行同样是数组的拷贝, 将原数组数据拷贝到新数组, 同样新数组的 index 位置会空出来.
17 行在 index 位置上加入新数据.
其余就没什么好解释的了, 如果以上两个方法完全明白操作套路, 那么其余两个 add 方法就很容易理解了, 这里就不一一分析了.
通过上面分析可以看出添加元素到指定位置需要将其后所有元素都要向后移动一位, 所以 ArrayList 向指定位置添加元素还是比较消耗性能的.
四, ArrayList 中 remove 方法源码分析
删除操作主要有以下两个方法:
- remove(int index) // 根据索引删除
- remove(Object object)// 根据元素删除
remove(int index) 源码:
- public E remove(int index) {
- Object[] a = array;
- int s = size;
- if (index>= s) {
- throwIndexOutOfBoundsException(index, s);
- }
- E result = (E) a[index];
- System.arraycopy(a, index + 1, a, index, --s - index);
- a[s] = null; // Prevent memory leak
- size = s;
- modCount++;
- return result;
- }
最核心就是 8-9 行代码了
8 行, 同样也是数组的拷贝操作, 从将要删除元素索引 index 开始将之后元素全部向前移动一位, 也就是将 index 位置元素覆盖掉了.
9 行, 防止内存泄露, 将最后一个元素置 null.
其余就没什么好解释得了, 关键是第 8 行一定要理解.
remove(Object object) 与 remove(int index) 主要区别就是有个判断 object 是否为 null 操作, 其余就基本都差不多了, 就不再分析了.
同样, 根据上面分析我们可以看出对于删除某一个元素其后所有元素都要向前移动一位, 也是比较消耗性能
五, ArrayList 中 contains 方法源码分析
接下来我们看下 ArrayList 是怎么判断是否包含某一元素的.
contains(Object object) 源码如下:
- public boolean contains(Object object) {
- Object[] a = array;
- int s = size;
- if (object != null) {
- for (int i = 0; i < s; i++) {
- if (object.equals(a[i])) {
- return true;
- }
- }
- } else {
- for (int i = 0; i < s; i++) {
- if (a[i] == null) {
- return true;
- }
- }
- }
- return false;
- }
比较简单, 无论 object 是否为 null, 都需要遍历整个数组比较, 所以效率是比较低的.
六, 总结
以上就是 ArrayList 主要方法的分析, 整体下来感觉和数组差不多, 其优势就是数据的随机访问, 对于指定位置插入数据以及删除数据性能都比较 "费劲", 在初始化完成后如果我们想插入大量数据可以调用 ensureCapacity(int minimumCapacity) 来提前对 ArrayList 进行扩容, 而不是在不断插入数据的时候自身不断扩容, 如果是数据频繁的增加删除 LinkedList 则是最佳选择.
好了, 本片到此结束, 希望对你有用.
来源: https://www.cnblogs.com/leipDao/p/9391755.html