本文转自JavaGuide,并加入了自己的部分见解
ArrayList简介
ArrayList 的底层是数组队列,相当于动态数组。与 Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用ensureCapacity
操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
它继承于 AbstractList,实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
在我们学数据结构的时候就知道了线性表的顺序存储,插入删除元素的时间复杂度为O(n),求表长以及增加元素,取第 i 元素的时间复杂度为O(1)
ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandomAccess 接口, RandomAccess 是一个标志接口,表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中,我们即可以通过元素的序号快速获取元素对象,这就是快速随机访问。
ArrayList 实现了Cloneable 接口,即覆盖了函数 clone(),能被克隆。
ArrayList 实现java.io.Serializable 接口,这意味着ArrayList支持序列化,能通过序列化去传输。
和 Vector 不同,ArrayList 中的操作不是线程安全的!所以,建议在单线程中才使用 ArrayList,而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。
ArrayList核心源码
1 | package java.util; |
ArrayList源码分析
System.arraycopy()和Arrays.copyOf()方法
通过上面源码我们发现这两个实现数组复制的方法被广泛使用而且很多地方都特别巧妙。比如下面add(int index, E element)方法就很巧妙的用到了arraycopy()方法让数组自己复制自己实现让index开始之后的所有成员后移一个位置:
1 | /** |
又如toArray()方法中用到了copyOf()方法
1 |
|
两者联系与区别
联系:
看两者源代码可以发现copyOf()
内部调用了System.arraycopy()
方法
区别:
- arraycopy()需要目标数组,将原数组拷贝到你自己定义的数组里,而且可以选择拷贝的起点和长度以及放入新数组中的位置
- copyOf()是系统自动在内部新建一个数组,并返回该数组。
ArrayList 核心扩容技术
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//下面是ArrayList的扩容机制
//ArrayList的扩容机制提高了性能,如果每次只扩充一个,
//那么频繁的插入会导致频繁的拷贝,降低性能,而ArrayList的扩容机制避免了这种情况。
/**
* 如有必要,增加此ArrayList实例的容量,以确保它至少能容纳元素的数量
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取默认的容量和传入参数的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容,上面两个方法都要调用
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果说minCapacity也就是所需的最小容量大于保存ArrayList数据的数组的长度的话,就需要调用grow(minCapacity)方法扩容。
//这个minCapacity到底为多少呢?举个例子在添加元素(add)方法中这个minCapacity的大小就为现在数组的长度加1
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容,调用此方法代表已经开始扩容了
grow(minCapacity);
}
1 | /** |
扩容机制代码已经做了详细的解释。另外值得注意的是大家很容易忽略的一个运算符:移位运算符
简介:移位运算符就是在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种:<<(左移)、>>(带符号右移)和>>>(无符号右移)。
作用:对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
比如这里:int newCapacity = oldCapacity + (oldCapacity >> 1);
右移一位相当于除2,右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。
另外需要注意的是:
java 中的length 属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
java 中的length()方法是针对字 符串String说的,如果想看这个字符串的长度则用到 length()这个方法.
.java 中的size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!
内部类
1 | (1)private class Itr implements Iterator<E> |
ArrayList有四个内部类,其中的Itr是实现了Iterator接口,同时重写了里面的hasNext(), next(), remove() 等方法;其中的ListItr 继承 Itr,实现了ListIterator接口,同时重写了hasPrevious(), nextIndex(), previousIndex(), previous(), set(E e), add(E e) 等方法,所以这也可以看出了 Iterator和ListIterator的区别: ListIterator在Iterator的基础上增加了添加对象,修改对象,逆向遍历等方法,这些是Iterator不能实现的。
ArrayList经典Demo
1 | package list; |