ArrayList

前言

上面我们说完了Java中最重要的一个类——String，现在我们要说的同样是一个非常重要的类，也是最常用的一个集合ArrayList。现在我们就来简单的学习一下这个类的使用方式，然后简单的看一下这个类的源码。

ArrayList漫谈

ArrayList声明

先来看看ArrayList的声明。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

public abstract class AbstractCollection<E> implements Collection<E>

public interface Collection<E> extends Iterable<E>

public interface List<E>
extends Collection<E>

上面是ArrayList的声明，和与其有关的类或者接口的一些声明。现在就简单的介绍一下就完事了。

• List<E>，Collection<E>：是两个基本的接口。其中Collection是Java中存储单列数据集合的接口，而List是存储有序的单列数据的集合，无序的接口是Set。使用双列数据也就是键值对的形式的接口是Map，其中Map和Collection是并列的。

• RandomAccess是一个标记接口，表示这个集合是支持随机访问的，因为ArrayList的底层是使用数组来实现的，而LinkedList的底层是使用链表来实现的，不可以使用RandomAccess接口。

  上面既然说了RandomAccess是一个标记接口，就代表这个接口是没有方法需要实现的。此接口的主要目的是允许通用算法改变其行为，以便在应用于随机访问列表或顺序访问列表时提供更好的性能。而Serializable也是我们常见的标记接口。

• Cloneable其实也是一个标记接口，因为这个接口中其实没有方法需要实现的。这个接口代表这个类可以通过clone方法进行克隆。但是这个接口可以说又不是一个标记接口，因为实现这个接口我们都需要重写Object中的clone方法。我们来看一下Object中的clone方法。

  @HotSpotIntrinsicCandidate
  protected native Object clone() throws CloneNotSupportedException;

  注释HotSpotIntrinsicCandidate代表着该方法在HotSpot中有更加高效的实现，该高效的实现是基于CPU指令的。native关键词代表着这个方法不是使用Java代码实现的，据悉Java中大多数的native方法都是使用C++来实现的。native方法是没有方法体的。

  另外需要注意的是这个方法是一个protected方法，外界是无法调用的。所以说我们实现了Cloneable接口之后还是要重写这个方法，将这个方法变成public的方法。

  @Override
  public Object clone() throws CloneNotSupportedException {
      return super.clone();
  }

  如何没有使用Cloneable接口，但是重写了clone方法并调用，会抛出java.lang.CloneNotSupportedException异常。还有一点需要注意的是，默认的clone是浅拷贝，对于引用类型的拷贝需要当心了！

• Iterator接口是有迭代器接口，需要实现iterator方法返回一个迭代器。而一个迭代器又是实现了iterable接口，其中有迭代器的基本的next，hasNext，remove方法需要实现。

上面基本上就是对ArrayList声明的一些说明了。

ArrayLIst源码

ArrayList的源码也是有几千行，但是这个看起来要比String类的源码舒服多了，没用那么多完全看不懂的地方了。我们还是从构造函数看起。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

注释告诉我们他是创建了一个初始容量为10的一个数组。但是看起来没有那么简单。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

这个明明是一个没有长度的数组，我寻思你这个注释不是骗我的嘛。不过我们添加元素的时候ArrayList是如何做的呢？

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

上面是我们添加元素的时候的调用add所执行的函数。一开始elementData.length是为0的。然后调用了grow(1)开始扩容。关键是看一下函数newCapacity，第二十八行，二十九行的代码，DEFAULT_CAPACITY是10，通过上面的方式会创建一个长度为10的数组。看来ArrayList采取的是懒加载的形式，只有调用了add方法的时候才会去创建数组。不过如果是使用带参数的构造器的话，就不会懒加载。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

其实上面的懒加载也是从JDK8之后改动的。JDK7及之前都不是懒加载，我们可以看一下Vector的源码。

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

/**
 * Constructs an empty vector so that its internal data array
 * has size {@code 10} and its standard capacity increment is
 * zero.
 */
public Vector() {
    this(10);
}

之所以改动的时候没有修改Vector的源码，是因为Vector在Java中是真的没有人使用了，所以写JDK的人不改进他的源码也是很正常的。想我vector在c++中那么牛逼，没想到在Java中竟然沦落到如此的底部，呜呼，哀哉！！

再看一下那个newCapacity函数，感觉这个函数名字非常的熟悉。因为好像我们昨天看StringBuilder的源码，观察StringBuilder底层的数组的扩容的时候也看到了这个函数。不过StringBuilder的默认大小是16，扩容的规则是两倍加上二，但是ArrayList的默认的大小是10，扩容的规则是变成原来的1.5倍。Vector是变成原来的2倍。

我们发现出去对数组的基本的操作的API之外，ArrayList中竟然还常有三个内部类。他们分别是

private class Itr implements Iterator<E>

final class ListItr extends Itr implements ListIterator<E>

final class VectorSpliterator implements Spliterator<E>

看来这个三个都是迭代器，这里就不深入的了解了。ArrayList中也有获取这些迭代器对象的对应的方法。

public synchronized Iterator<E> iterator() {
    return new Itr();
}

public synchronized ListIterator<E> listIterator() {
    return new ListItr(0);
}

public synchronized ListIterator<E> listIterator(int index) {
    if (index < 0 || index > elementCount)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

@Override
public Spliterator<E> spliterator() {
    return new VectorSpliterator(null, 0, -1, 0);
}

remove 方法

ArrayList中有如下的两个方法。

public E remove(int index)

public boolean remove(Object o)

这两个方法是不是有点不好呢？比如说如下的情况下。

public static void main(String[] args) throws CloneNotSupportedException {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    list.remove(1);
    System.out.println(list);
}

那么到底是输出的是2 3还是1 3呢？也就是调用的是哪个函数呢？或许会有点儿疑惑，但是毫无疑问会调用remove(int index)这个函数，虽然int会执行装箱的操作，但是如果存在不用装箱就可以调用的函数，那他为何还需要装箱呢？如果我们真的是需要调用remove(Object o)的话，我们需要这样子写list.remove(Integer.valueOf(1));。

遍历ArrayList

public static void main(String[] args) throws CloneNotSupportedException {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
}

其实如果要使用这种方式的话，还不如使用增强for循环来实现呢。

使用这个迭代器也是可以的，两个迭代器比起来只是listIterator的方法更多一点而已。可以添加也可以前后的移动。

public static void main(String[] args) throws CloneNotSupportedException {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    ListIterator<Integer> integerListIterator = list.listIterator();
    while (integerListIterator.hasNext()) {
        System.out.println(integerListIterator.next());
    }

    for (int val : list) {
        System.out.println(val);
    }

    list.forEach(System.out::println);

    list.stream().forEach(System.out::println);
}

同样的后面也有两种不是很常用的遍历方式。

ArrayList的拷贝

思来想去说一说关于拷贝的问题的。其实也就是拷贝是浅拷贝韩式深拷贝的问题。clone是浅拷贝，Collections.copy也是浅拷贝。然后普通数组的拷贝方法System.arraycopy和Arrays.copyOf也都是浅拷贝。

其中Collections.copy的使用如下所示

public static void main(String[] args) throws CloneNotSupportedException {
    List<CA> list = new ArrayList<>();
    list.add(new CA("sher"));
    list.add(new CA("hony"));
    list.add(new CA("honysher"));

    List<CA> temp = Arrays.asList(new CA[list.size()]);
    Collections.copy(temp, list);
    System.out.println(temp.get(0).name == list.get(0).name);
}

使用方式，说实话蛮沙雕的。而剩下的两个函数我写一下声明就行了。

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

public static int[] copyOf(int[] original, int newLength)

其实这个copyOf也是用arraycopy来实现的。

public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

上面我们提到的所有的拷贝都是浅拷贝，那么该如何实现深拷贝呢？所谓的深拷贝就是递归的拷贝，遇到引用就要直接拷贝他的源头而不是拷贝引用。我记得之前说IO的时候说过一个东西叫序列化。也就是DataInput/OuputStream这个玩意。我们序列化的时候会保存所有的引用的源头，以便于后面我们读取的时候可以恢复到之前的一模一样的状态。如果只是保存引用，那就直接GG了。我们似乎可以通过序列化的方式进行深拷贝。

public static void main(String[] args) {
    List<CA> list = new ArrayList<>();
    list.add(new CA("sher"));
    list.add(new CA("hony"));
    list.add(new CA("honysher"));

    ObjectOutputStream oos = null;
    ObjectInputStream ois = null;
    List<CA> temp = null;

    try {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        oos = new ObjectOutputStream(baos);
        oos.writeObject(list);
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
        ois = new ObjectInputStream(bais);
        temp = (List<CA>) ois.readObject();
    } catch (IOException e) {
        e.printStackTrace();
    } catch (ClassNotFoundException e) {
        e.printStackTrace();
    } finally {
        if (oos != null) {
            try {
                oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        if (ois != null) {
            try {
                ois.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    System.out.println(temp.get(1).name);
    System.out.println(list.get(1).name);
    System.out.println(temp.get(1).name == list.get(1).name);
}

通过上面的方式我就完成了对ArrayList的深拷贝，但是前提是ArrayList中数据的类型的类必须要实现java.io.Serializable接口，不然程序是会报错的。

不过这个序列化来进行深拷贝的方式效率是比较低的，但是也没办法，似乎也没有什么其他的方法。

但是对于一种特殊的情况还有一种简单的方式。利用JSON字符串的性质。不过也有一个限制，那就是对象的所有的成员都要是基本的数据类型，或者是String也可以的。

这里使用到了阿里巴巴的FastJSON的jar包，不是用的Java原生的类库。

@Test
public void test() {
    CA sher = new CA("sher");
    String str = JSON.toJSONString(sher);
    CA temp = JSON.parseObject(str, CA.class);

    System.out.println(temp.name);
    System.out.println(sher.name);
    System.out.println(sher.name == temp.name);
}

如果是ArrayList那是没办法使用这个方法的。

@Test
public void test2() {
    List<CA> list = new ArrayList<>();
    list.add(new CA("sher"));
    list.add(new CA("hony"));
    list.add(new CA("honysher"));

    String str = JSON.toJSONString(list);
    List<CA> temp = JSON.parseObject(str, List.class);

//        System.out.println(temp.get(1).name);
//        System.out.println(list.get(1).name);
//        System.out.println(temp.get(1).name == list.get(1).name);
}

ArrayLIst与Vector

之前也说过了ArrayList和Vector是相似的，不过一个是线程不安全，一个是线程安全的。那么是不是如果考虑到线程安全的情况下我们就要使用Vector呢？当然不是，Vector这么垃圾，其实也没有人去使用他。我们可以这样把ArrayList变成一个线程安全的容器。

@Test
public void test3() {
    List<CA> list = new ArrayList<>();
    list.add(new CA("sher"));
    list.add(new CA("hony"));
    list.add(new CA("honysher"));

    List<CA> cas = Collections.synchronizedList(list);
}

此时这个cas就是一个线程安全的容器了。

其实我们可以使用这样的集合java.util.concurrent.CopyOnWriteArrayList，这是专门为了多线程设计的ArrayList的变种。

总结

上面就简单的学习了一下ArrayList的使用。看了声明和源码以及一些常用的方法。后面还说到了ArrayList的浅拷贝与深拷贝的问题。