java集合类源码学习三——ArrayList

时间:2022-05-24 14:41:14

  ArrayList无疑是java集合类中的一个巨头,而且或许是使用最多的集合类。ArrayList继承自AbstractList抽象类,实现了List<E>, RandomAccess, Cloneable, java.io.Serializable这些接口,这意味着ArrayList可以随机取数据,支持浅拷贝和序列化。ArrayList可以存放各种类型的值,有序、可重复而且可以存放null,这里的有序指的是按顺序存放,而不是自动排序。它有一个默认容量DEFAULT_CAPACITY = 10,还定义了两个空数组EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA,同样都是静态私有不可变的Object数组,那么为什么要弄两个,从取名上看EMPTY_ELEMENTDATA指的是空数组,而DEFAULTCAPACITY_EMPTY_ELEMENTDATA指的是默认容量的未存放元素的空数组。从后面的代码可以看出,给数组长度赋默认值之前,是与DEFAULTCAPACITY_EMPTY_ELEMENTDATA比较的,而让数组为空数组则是与EMPTY_ELEMENTDATA比较的,如果非要说有差别,也就这点了,有点脱裤子放屁的意味。然后定义了一个object数组elementData,用transient修饰的,表示不可以被序列化,这就是ArrayList的底层实现,本质是个数组。提供了三个构造器,一个无参,一个可指定长度,还有一个可将其他Collection的集合转化成ArrayList,下面是第三个构造器的代码

public ArrayList(Collection<? extends E> c) {
elementData = 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;
}
}

  里面有个判断class的操作,用于把从其他集合转到数组的非Object类型转化成Object类型数组。ArrayList底层既然是数组,那么最大长度也就为Integer的最大值减8,同样在扩容的时候如果这个长度不够,可以用hugeCapacity,也即Integer的最大值。下面是插入到一个位置和获取一个位置的值的代码

public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

public E get(int index) {
rangeCheck(index);

return elementData(index);
}

  可以看到,插入元素需要把该位置及后面的元素全部往后移一位,时间复杂度为O(n),而获取一个元素,只需要根据索引定位过去就行,时间复杂度为O(1)。其余的操作基本就是各种对数组的操作,每次操作都会有一个modCount++,表示修改过一次,用的最多的方法System.arraycopy(Object src, int srcPos,Object dest, int destPos,int length),这是一个native方法,用于快速拷贝一段数组到另一个位置。后面还有迭代器Iterator和listIterator的具体实现,这个之前也分析过了,没什么区别。

  后面还有些JDK1.8加的支持函数式编程的方法,先不提。由于ArrayList的方法不是同步的,因此在多线程访问的时候如果有对其进行操作,不是线程安全的。所以在多线程用的时候需要加个同步锁,或者别的线程安全的集合类。