JAVA 深入集合-- ArrayList
程序员文章站
2022-07-12 16:00:38
...
一、介绍
ArrayList 简单的说就是一个存放元素的集合，也是一个数组，只是提供了大量方便我们操作的方法， 比数组的优势就是不用我们手动维护了，相信大家用得比较多了，还是看代码吧！
二、源码介绍
2.1 类：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看出，继承了AbstractList<E> 实现了 List<E> 和 RandomAccess,这里List 只一个接口，定义了该集合的一些方法，
AbstractList 是实现了List 接口的抽象类，继承他 只是为了减少我们常用的一些操作，这里和hashMap 的设计一样，具体请看hashMap 的介绍。
RandomAccess 这东西作为一个接口定义，允许一般的算法更改其行为，- -比较抽象，暂时不管，后期再谈！
2.2 构造
private transient Object[] elementData;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
// 从上面看出，当我们new一个 ArrayList 的时候，实际是创建了一个elementData 的数组，当 // 然默认长度为10，很简单对吧！
// 这里集合扩展，就是数组复制，也没啥奇特的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
2.3 我们切入点从常用的 add set 方法开始看：
add:这里进行的重写
// 属性获得获得元素的个数
private int size;
public boolean add(E e) {
// size 默认是0，其实这里仅仅是进行一个是否扩容的判断
ensureCapacity(size + 1); // Increments modCount!!
// 可以看出 这就仅仅是给数组放值
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
// 依然是控制集合修改次数，用于迭代的时候控制异常
modCount++;
// 数组长度
int oldCapacity = elementData.length;
// 如果当前容量大于的数组长度
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
// 进行扩容后的长度，这里有点意思，要扩容成奇数，不知道为啥
int newCapacity = (oldCapacity * 3)/2 + 1;
// 这里为了addAll的时候，可能一次性添加多了
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// 这里就是扩容啦，也看看源码吧，虽然在工具类Arrays里面的
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
// 扩容源码
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
// 这里用于返回U类型的T 数组
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// 这里进行了地址判断，判断参数是否是Object类型,否则就从新 new 一个newType 类型的数 // 组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 这是JAVA数组扩容最快的方法了，参数解释 看看API 就行了
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
2.3.2 继续看方法：add(index, element)
// 这里我们知道是方法是将元素element 加入到集合的指定位置index
public void add(int index, E element) {
// 先进行判断，位置是否超出了界限，当然这里判断只是判断size,而非数组界限
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
// 这里就是刚才的了
ensureCapacity(size+1); // Increments modCount!!
// 这里看出还是数组的复制，只是将当前数组elementData 的index + 1位置 向后移动了一位，就完成了插入
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
2.3.3 方法addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
// 数组扩容
ensureCapacity(size + numNew); // Increments modCount
// 数组复制
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
2.4 get方法
public E get(int index) {
// 仅仅判断数组是否越界，抛出自己定义的错误信息
RangeCheck(index);
// 直接访问的数组下标，因此访问元素很快
return (E) elementData[index];
}
private void RangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
2.5 方法：remove(int index)
public E remove(int index) {
// 同上
RangeCheck(index);
// 看来在迭代的时候不允许删除的
modCount++;
E oldValue = (E) elementData[index];
// 获取删除的位置
int numMoved = size - index - 1;
if (numMoved > 0)
// 当前数组在numMoved 位置，向左复制，
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将数组最后一个元素设为null,我们发现虽然元素删除了，但是数组的长度并没减少，还占 // 空间
elementData[--size] = null; // Let gc do its work
return oldValue;
}
// 这里要提到另一个方法，在remove(Object o)中使用了，其实内容和上面一样，只是JDK 人 // 员忘记掉了
// 看到这些我总会相信，大神也会失误的，也是不完美的~。~
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; // Let gc do its work
}
2.6 方法：indexOf(Object o)
public int indexOf(Object o) {
if (o == null) {
// 这里小技巧发现，对null 的判断总是要特殊一些
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 总的来说就是便利数组啦，有就返回，没有返回-1
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
// 同时contains方法额也是调用的这个
return -1;
}
2.7 方法：toArray，带参数和不带参数差不多
public <T> T[] toArray(T[] a) {
// 带参数情况就是，如果a 数组length 比较大，那么剩余的都是null,而不带参数 仅仅是将
// list元素放进数组返回
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.8 方法：removeRange
// 这个方法可以一次移除 指定两个位置的所有元素，但是不知道为什么是protected ，调用 // 不了
// 当然实现这个功能 我们可以用 list.sublist(int b,int e).clear() 完成此功能
protected void removeRange(int fromIndex, int toIndex) {
// 内容和remove 比较类似
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
2.9 方法：trimToSize
// 上面讲到我们删除元素的时候，数组还是占着位置，这个方法就是将那些没有元素的位置删 // 除掉
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
2.9.1 方法：subList(fromIndex, toIndex)
// 这里实际上是在AbstractList 里面了，arrayList 没进行重写
public List<E> subList(int fromIndex, int toIndex) {
// 这两个内部类...其实对象都访问到SubList 里面去了
return (this instanceof RandomAccess ?
new RandomAccessSubList<E>(this, fromIndex, toIndex) :
new SubList<E>(this, fromIndex, toIndex));
}
// 先来看看 内部类吧
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
// 从构造看出，其实操作了 SubList<E> 的构造，super() 继续往下看
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<E>(this, fromIndex, toIndex);
}
}
// 这个内部类 就是我们需要返回RandomAccessSubList<E> 的父类，看看做了什么操作
class SubList<E> extends AbstractList<E> {
private AbstractList<E> l;
private int offset;
private int size;
private int expectedModCount;
// 构造线对位置进行了判断
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
// 然后赋值，注意这个是强引用
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
expectedModCount = l.modCount;
}
// ...
}
// 这里可以看出其实我们调用subList 方法的同时，返回的其实是一个RandomAccessSubList 对象，
// 但是该对象继承了SubList<E> ，而SubList<E> 内容是原来list 的的一个引用。
// 既然是引用，那么为什么还要单独设计一个类呢，为什么不直接引用，操作数组呢？
// 这个是SubList<E> 内部的方法，看看区别
public E set(int index, E element) {
// 检查参数大小
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
// 这里看到 我们获得元素的位置 已经发生了变化
return l.get(index+offset);
}
public int size() {
checkForComodification();
return size;
}
// 大家都调用了这个方法，也就是说当我们操作这个sublist 返回的类的时候
// 都是不允许影响集合的操作
// 包括原list 也不允许删除 等操作
private void checkForComodification() {
if (l.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
// 下面继续看内部类的通用方法：
// 下面所有的方法我们都可以看出一点
// 所有元素的位置 都跟index 和 offset 相关，也就是和我们定义的位置有关，实质内容没变
public void add(int index, E element) {
if (index<0 || index>size)
throw new IndexOutOfBoundsException();
checkForComodification();
l.add(index+offset, element);
expectedModCount = l.modCount;
size++;
modCount++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = l.remove(index+offset);
expectedModCount = l.modCount;
size--;
modCount++;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
l.removeRange(fromIndex+offset, toIndex+offset);
expectedModCount = l.modCount;
size -= (toIndex-fromIndex);
modCount++;
}
// 上面的元素操作，参考前面的介绍，我们来模拟一下这个内部类干了什么。
// 1.假设我们有个ArrayList m,存放了元素 1,2,3,4,5,6,7,8,9
// 2.假设我们要得到1,2,3 的元素，从而调用sublist(0,3) 方法。
// 3.这个时候内部类给我们定义变量 private AbstractList<E> l ,size 等属性
// 4.为属性赋值l = list; offset = fromIndex = 0; size = toIndex - fromIndex = 3;
// 5.我们可以看出，现在 我们操作的实际是m的引用l,但是操作的范围只能是 0,3 这个区间。
// 6.也就是说，大家共用一块区域，但是sublist 的结果，只能从大的区域m,划分出一片小的区域
// 7.但是如果操作任何一个变量，都会引起大家的变化，我们做个尝试
public static void main(String[] args) {
ArrayList<Object> m = new ArrayList<Object>();
System.out.println(new Test() instanceof RandomAccess);
for(int i =1;i<10;i++){
// 放9个元素
m.add(i);
}
// 取3个元素1,2,3
List<Object> l = m.subList(0, 3);
// 这里已经拿到 1,2，3 了
System.out.println(l);
// 这里是没变化的
System.out.println(m);
// 如果l 添加一个值，我们发现m 的数据已经变了，多了一个元素10
l.add(10);
System.out.println(m);
System.out.println(l);
// 如果操作m,那么打印l,就会抛ConcurrentModificationException
m.add(11);
System.out.println(m);
// 因为l添加时，先检查 checkForComodification() 变量再自增，
// 而m 元素增加了 ，modCount 数量也加1，打印不报错
// 而m添加元素了，modCount 增加，而l 元素没有增加，期望的expectedModCount // 没变
// 价差不通过 就报错了
System.out.println(l);
// 所以使用的时候要小心啦，当然你可以这样 new ArrayList(l) 创建新的
System.exit(0);
}
关于AbstractList 里面提供的源码，后面再介绍吧，大概的都差不多，只是iterator 迭代 那里不同
关于私有方法writeObject 和 readObject 这是为io 准备的，传输的时候会通过反射查找调用，这里暂时不讲
三、小结：
1.ArrayList 是一个动态数组，动态通过数组的底层复制进行，和Vector差不多，它不是线程安全的
2.为了减小计算，可以手动指定空间或者扩容ensureCapacity ，同时也可以trimToSize 去掉不必要的空间
3.存放元素和获取元素 都是通过数组依次存放，通过下标存放，因此是很快的
上一篇： oracle多列子查询的实现
下一篇： Exists 和In