java源码赏析--java.util.ArrayList
1. 简介
ArrayList
是可以动态增长和缩减的索引序列,它是基于数组实现的 List
类。
该类封装了一个动态再分配的 Object[]
数组,每一个类对象都有一个 capacity
属性,表示它们所封装的 Object[]
数组的长度,当向 ArrayList
中添加元素时,该属性值会自动增加。如果向 ArrayList
中添加大量元素,可使用 ensureCapacity
方法一次性增加 capacity
,可以减少增加重分配的次数提高性能。
ArrayList
的用法和 Vector
相类似,但是 Vector
是一个较老的集合,具有很多缺点,不建议使用。另外,ArrayList
和 Vector
的区别是:ArrayList
是线程不安全的,当多条线程访问同一个 ArrayList
集合时,程序需要手动保证该集合的同步性,而 Vector
则是线程安全的。
【java源码赏析--java.util.ArrayList】size
、isEmpty
、get
、set
、iterator
和listIterator
操作的运行时间是常量。add
操作对于添加n个元素,需要O(n)的时间。其他的操作需要线性时间。
1.1 继承关系
文章图片
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
- 继承
AbstractList
抽象父类,AbstractList提供了List接口的默认实现(个别方法为抽象方法)。
- 实现了
List
接口(规定了List
的操作规范),List接口(extends Collection)定义了列表必须实现的方法。
RandomAccess
(可随机访问),是一个标记接口,用来标记可适用与随机访问算法的类。
Cloneable
(可拷贝),可以调用Object.clone方法返回该对象的浅拷贝。
Serializable
(可序列化)。
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//空数组
private static final Object[] EMPTY_ELEMENTDATA = https://www.it610.com/article/{};
//默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 不会被序列化
transient Object[] elementData;
//ArrayList实际元素容量
private int size;
//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
ArrayList
的默认容量DEFAULT_CAPACITY
为10。
- 数据存放在
elementData
中,且访问级别为包内私有,是为了使内部类能够访问到其中的元素。并且被标记为transient,也就意味着在序列化的时候,此字段是不会被序列化的。
size
表示数组中元素的个数
EMPTY_ELEMENTDATA
与DEFAULTCAPACITY_EMPTY_ELEMENTDATA
是为了在构造函数中初始化elementData
使用的。
MAX_ARRAY_SIZE
为ArrayList
最大分配容量。
public ArrayList() {
this.elementData = https://www.it610.com/article/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
无参构造函数,
elementData
中没有元素,size
为0,且elementData
的长度也为0。使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA
为elementData
赋值。public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = https://www.it610.com/article/new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
elementData
中没有元素,size
为0,不过elementData
的长度有可能不同。使用EMPTY_ELEMENTDATA
为elementData
赋值。public ArrayList(Collection extends E> c) {
elementData = https://www.it610.com/article/c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
首先将集合
c
转化为数组,然后检查转化的类型,如果不是 Object[]
类型,使用 Arrays
类中的 copyOf
方法进行复制;同时,如果 c
中没有元素,使用 EMPTY_ELEMENTDATA
初始化。2.3 主要方法
2.3.1
boolean add(E e)
确保容量足够后,在尾部添加一个元素public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
动态扩容
ensureCapacityInternal
在 Arraylist
中多次使用,着重理解。private void ensureCapacityInternal(int minCapacity) {//第一次添加元素时,如果是无参构造函数构造而来,那么所需最小容量为DEFAULT_CAPACITY
if (elementData =https://www.it610.com/article/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}ensureExplicitCapacity(minCapacity);
}
上面代码中
if
判断为了区分对象是由哪一种构造函数构造而来。第一次添加元素时需要确定最小扩容容量。而DEFAULTCAPACITY_EMPTY_ELEMENTDATA
与 EMPTY_ELEMENTDATA
用来区分三个构造函数。private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//列表修改次数加1//如果所需最小容量大于数组长度时,才许真正扩容。
if (minCapacity - elementData.length > 0){
grow(minCapacity);
}
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
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 = https://www.it610.com/article/Arrays.copyOf(elementData, newCapacity);
}
一般正常情况下,新的容量一般为旧容量的
1.5
倍(oldCapacity + (oldCapacity >> 1)
)。private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) {// 这种情况,如何出现?
throw new OutOfMemoryError();
}
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}
minCapacity
在超出最大限制时允许达到 Integer.MAX_VALUE
,而不仅仅是Integer.MAX_VALUE - 8
2.3.2
void ensureCapacity(int minCapacity)
供外部调用的扩容方法。在大致了解List大小时,可用此方法一次性增加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);
}
}
- 如果是通过无参构造函数构造且
elementData
中没有元素,则不需要扩容。
- 在
ensureExplicitCapacity
方法中,如果扩容大小小于elementData
长度,则不需要扩容。
void add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
//
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
检查
index
是否数组越界。private void rangeCheckForAdd(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
- 先调用
rangeCheckForAdd
检查索引是否合法。 - 合法再调用上面讲过的
ensureCapacityInternal
执行扩容。 - 调用系统的
arraycopy
函数将索引处及其后的元素后移一位。 - 在
index
处插入该元素。
2.3.4
boolean addAll(Collection extends E> c)
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;
}
- 将
c
转换为数组a
。 - 调用
ensureCapacityInternal
动态扩容。 - 调用系统函数
arraycopy
。 - 增加
elementData
的size
。 - 有意思的小细节,
numNew
!= 0,则返回true
。
- 为什么不从一开始就判断
numNew
的值呢,如果等于0,直接返回,后面的函数也就不用执行了?
boolean addAll(int index, Collection extends E> c)
public boolean addAll(int index, Collection extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// Increments modCountint 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;
}
- 和
add(int index, E element)
一样,先调用rangeCheckForAdd
检查索引合法性。 - 将
c
转换为数组a
。 - 调用
ensureCapacityInternal
扩容。 - 如果插入位置不是
Arraylist
的末尾,则调用arraycopy
将索引及其后的元素后移。 - 将
a
的元素arraycopy
到elementData
中。 - 增加
size
。 -
numNew != 0
,则返回true。
E get(int index)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
注意和
rangeCheckForAdd
的不同之处。private void rangeCheck(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
- 检查索引合法性。
- 返回指定数据。
void clear()
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0;
i < size;
i++){
elementData[i] = null;
}size = 0;
}
- 从结构上修改 此列表的次数加1;
- for循环将每个元素置空;
-
size
置为0,elementData
的长度并没有修改,如果确定不再修改list
内容之后最好调用trimToSize
来释放掉一些空间)。
void trimToSize()
返回一个新数组,新数组不含null,数组的 size
和 elementData.length
相等,以节省空间。此函数可避免 size
很小但 elementData.length
很大的情况。public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = https://www.it610.com/article/(size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
2.3.8
int indexOf(Object o)
public int indexOf(Object o) {
if (o == null) {
for (int i = 0;
i < size;
i++) {
if (elementData[i]==null) {
return i;
}
}
} else {
for (int i = 0;
i < size;
i++) {
if (o.equals(elementData[i])) {
return i;
}
}
}
return -1;
}
ArrayList
中可以添加 null
,且可以在任意位置。2.3.9
boolean contains(Object o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
不建议使用
contains(Object o)
方法。效率极差。原因是通过for循环分别 equals
2.3.10
boolean containsAll(Collection> c)
继承java.util.AbstractCollection
的 containsAll
public boolean containsAll(Collection> c) {
for (Object e : c) {
if (!contains(e)) {
return false;
}
}
return true;
}
不建议使用,效率更差。
2.3.11
int hashCode()
继承 java.util.AbstractList
的 hashCode
public int hashCode() {
int hashCode = 1;
for (E e : this) {
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
}
return hashCode;
}
2.3.12
Object clone()
返回ArrayList实例的浅拷贝public Object clone() {
try {
ArrayList> v = (ArrayList>) super.clone();
v.elementData = https://www.it610.com/article/Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
2.3.13
boolean remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = https://www.it610.com/article/elementData(index);
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 workreturn oldValue;
}
- 检查索引合法性
- 通过
System.arraycopy
挪动数组 -
size
减一,并将elementData
最后设为null
boolean remove(Object o)
public boolean remove(Object o) {
if (o == null) {
for (int index = 0;
index < size;
index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0;
index < size;
index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
由于
ArrayList
中可以存储 null
,所以需要判断参数 o
是否为空的判断。直观从代码上看,不建议使用此方法删除对象,性能太差。建议使用
boolean remove(int index)
删除元素。private void fastRemove(int index) {
modCount++;
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
}
需要注意
fastRemove(int index)
与 boolean remove(int index)
的区别,仅仅是没有返回值,作者为什么将相同的代码写两遍呢?2.3.15
boolean removeAll(Collection> c)
public boolean removeAll(Collection> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
判断对象是否为空
public static T requireNonNull(T obj) {
if (obj == null){
throw new NullPointerException();
}
return obj;
}
batchRemove
这个类中最精妙的代码private boolean batchRemove(Collection> c, boolean complement) {
final Object[] elementData = https://www.it610.com/article/this.elementData;
int r = 0, w = 0;
// r 用来遍历整个数组的索引w 用来标记需要替换的索引
boolean modified = false;
try {
for (;
r < size;
r++) {
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;
}
if (w != size) { // 如果 w != size, 则说明 w之后的元素都是需要丢弃掉的。而如果 w == size, 则说明没有发生替换,不需要删除。
// clear to let GC do its work
for (int i = w;
i < size;
i++) {
elementData[i] = null;
}
modCount += size - w;
//本次修改次数就应该是 size - w
size = w;
//替换次数 = size
modified = true;
}
}
return modified;
}
2.3.16
boolean retainAll(Collection> c)
保留 c
中的元素,与 remoteAll
的区别在于 batchRemove(c, complement)
。public boolean retainAll(Collection> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
2.3.17
E set(int index, E element)
替换对应索引的元素public E set(int index, E element) {
rangeCheck(index);
E oldValue = https://www.it610.com/article/elementData(index);
elementData[index] = element;
return oldValue;
}
2.3.18
Object[] toArray()
浅拷贝public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
2.3.19
T[] toArray(T[] a)
public T[] toArray(T[] a) {
if (a.length < size){
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
}
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size){
a[size] = null;
}
return a;
}
2.3.20
void sort(Comparator super E> c)
public void sort(Comparator super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
ConcurrentModificationException
是用来判断在数组排序时是否被修改。推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- Android事件传递源码分析
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用(一)
- java之static、static|java之static、static final、final的区别与应用