Java ArrayList

本章是整理知识内容，为强化知识长期更新。

List 是是一个有序的集合，是Collection的实现类之一。

概述

list接口是Java Collection Framework的成员。
列队允许添加重复的元素。
列队允许null存在。
列队是从0开始，也就是列队头元素的下标是0。
列队支持泛型，这样可以避免ClassCastException异常。

数组与数组列表

Array(数组)它是在内存中划分出一块连续的地址空间进行元素的存储，由于它直接操作内存，所以性能比其他的集合要高一点点。但是数组也有一个严重的缺陷，就是需要指定初始化大小，并且在后续的操作中不能修改数组的结构，这很不友好。

ArrayList可以很好的进行动态扩容，它会随之元素的不断增加而调整数组大小。它的底层是基于数据实现的，所以也集成了数组的一些特性。比如查找、修改很快，但是新增和删除比较慢。

Array数组

ArrayList底层是由数组实现的，那么就回顾下Java中数组的特性。

public class Array1Test {

    @Test
    public void test1() {
        String[] arr = new String[5];
        System.out.println("数组的长度" + arr.length);
        for (int i = 0 ; i < arr.length ; i++) {
            arr[i] = String.valueOf(i);
            System.out.print(" ");
        }
        System.out.println(arr[0].toString());
        // 打印出0 , 数组的下表是从0开始的。
        arr[6] = null;
        // 强行添加一个元素到6的位置,然后取出来抛出ArrayIndexOutOfBoundsException。数组的大小是不能修改的。
    }
}

输出：

数组的长度5
	0
java.lang.ArrayIndexOutOfBoundsException: 6

List列表

Java的List是一个有序的集合，List是Collection接口的扩展接口。

List特性

Java List接口是Java Collection Framework的成员。
列表允许添加重复的元素。
列表允许有null元素。
列表索引是从0开始，和数组一样的。
列表接受泛型，尽量使用它。以免出现ClassCastException

源码分析

ArrayList中的常量以及变量

// 默认初始化容器的大小
private static final int DEFAULT_CAPACITY = 10;

// 空的对象数组。
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认的对象数组。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 被transient修饰不会被序列化，集合中元素个数。
transient Object[] elementData; // non-private to simplify nested class access

// 容器中元素的个数
private int size;

// 容器的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

创建ArrayList的实例。

@Test
public void test3(){
    List list1 = new ArrayList();
    List list2 = new ArrayList(3);
    String[] vowels = {"a","e","i","o","u"};
    // 使用Arrays工具将数组转换成列表。
    List<String> vowelsList = Arrays.asList(vowels);
    List list3 = new ArrayList(vowelsList);
	
    System.out.println(list1.toString());
    System.out.println(list2.toString());
    System.out.println(list3.toString());
}

[]
[]
[a, e, i, o, u]

这分别使用了ArrayList三个构造方法。

// list1
public ArrayList() {
    // 参数为空的构造方法，元素是空的数组。
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 // list2
 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);
     }
 }
    
 // 对应list3
 public ArrayList(Collection<? extends E> c) {
    // 将一个Collection容器的元素都复制进来。
    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;
    }
 }

这让我想起了面试题目。

@Test
public void test4(){
    List list = new ArrayList(20);
}

题目是：生成list实例需要扩容几次。实际上是0次。因为创建的时候就指定了大小。

add方法

@Test
public void test4(){
    List list = new ArrayList();
    System.out.println(list.add(1));
    list.add(0,2);
    System.out.println(list.toString());
}

输出

true
[2, 1] // 是不是很神奇，下标0的位置是2，下标1位置值是1。

带着上面的疑问我们好好看看，顺便看看经常说ArrayList到底是如何扩容的。

// 直接添加元素
public boolean add(E e) {
    // 确保内部容量足够，不够就扩容。 size 是当前容器的数量
    ensureCapacityInternal(size + 1);  // Increments modCount!! 
    // 将元素添加到数组中
    elementData[size++] = e;
    return true;
}

// 在指定索引的位置添加元素。
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++;
}

System.arraycopy 是一个本地静态方法，使用它可以对数组之间进行复制。

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

src:源数组；
srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置；
length:复制的长度。

上面的操作结果就是将数组中的元素位置进行了移动，当然神奇的地方是这个方法可以自己复制自己。

// 1
private void ensureCapacityInternal(int minCapacity) {
    // 当前实际存储的数组是空的的时候
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 最小的数字 就是容量大小。
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

// 2
  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
		// 如果当前数组的长度小于 需要的最小容量大小就扩容。
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
  }

// 3
  private void grow(int minCapacity) {
        // 增加最小扩容，保证元素能添加进容器。
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 位运算 ， 新的容量大小 = 当前数组长度 右移动一位  就是 newCapacity = oldCapacity + (oldCapacity / 2) 取整。也就是经常说的扩容1.5倍。
        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:
        // 关键的时候来了，通过Arrays.copyOf复制元素并指定新的数组大小。这个方法最终还是调用了System.arraycopy方法，其它参数是由Array.copyOf预设好的。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
// 4 抛出OutOfMemoryError异常咯。内存溢出
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

每次扩容都是通过Arrays.copyOf(elementData, newCapacity)的来实现的。

set方法

这个方法其实就是更新方法。

@Test
public void test5(){
    List list = new ArrayList();
    list.add(1);
    System.out.println(list.set(0,1));
    System.out.println(list.toString());
}

输出

1
[1]

看下源代码。

public E set(int index, E element) {
    rangeCheck(index); //检查所以是否越界，这里要注意，该下标没有值会抛出越界异常。

    E oldValue = elementData(index); // 获取下标原始的值
    elementData[index] = element;	 // 将新值复制给对应的下标
    return oldValue;				// 返回原始的值
}

remove方法

@Test
public void test6(){
    List list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("b");
    list.add("c");
    list.add("d");
    System.out.println(list.toString());
    list.remove("b"); //根据元素匹配删除
    System.out.println(list.toString());
}

输出

[a, b, b, c, d]
[a, b, c, d] //会删除匹配到的第一个元素

// 根据下标删除元素。删除成功就返回被删除的元素。
public E remove(int index) {
    rangeCheck(index); // 检查下标是否越界

    modCount++;
    E oldValue = 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 work

    return oldValue;
}

// 删除元素，如果删除成功返回true
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;
}

// 删除索引上的元素
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
}

这两个删除方法可以看出，动作都比较大。这种操作会慢很多。

get方法。

相比上面3种方法确实轻量级太多了。

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

    return elementData(index);
}

平时也就听大家说新增修改删除慢，也就访问速度比较快。看了源码之后才清晰很多。

contains方法

这也是一个重量级的方法

// 判断对象存在与当前集合中。
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 */
public int indexOf(Object o) {
    // 当找不到该对象的时候返回-1，找到了就返回它的下标。
    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;
}

安全删除

@Test
    public void test2(){
        //  1、创建一个二维数组
        String[] vowels = {"a","e","i","o","u"};
        //  2、将二维数组转换成列表,在转换成容器
        Collection<String> collection = new ArrayList(Arrays.asList(vowels));
        // 3、获取容器迭代器实例
        Iterator<String> itr = collection.iterator();
        // 4、逻辑判断itr 中下个元素是否存在。
        while (itr.hasNext()){
            String var = itr.next(); // 获取将要访问的下一个元素。
            // 5、尝试修改其中的一个元素。
            if(var == "a"){
                // 5、删除掉 `a`
                itr.remove();
            }else{
                System.out.print(var);
            }
        }
    }

线程安全

由于所有的方法都没有进行同步。所以很直观的认为有线程安全的问题，还是亲自测试下避免迷迷糊糊的。

场景一：多线程对一个ArrayList进行操作。

假设我们需要添加10000个元素进ArrayList

public class ArrayListTest2 {

    /**
     * 10线程对一个ArrayList进行操作。
     *
     * @param args
     */
    public static void main(String[] args) throws InterruptedException {
        List list = new ArrayList();
        ExecutorService executorService = Executors.newFixedThreadPool(20);
        for (int sum = 0 ; sum < 10 ; sum ++){
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    System.out.println("ThreadId:" + Thread.currentThread().getId() + " start!");
                    for (int i = 0 ; i < 1000 ; i++ ){
                        list.add(i);
                    }
                    System.out.println("ThreadId:" + Thread.currentThread().getId() + " stop!");

                }
            });
        }
        executorService.shutdown();
        while (!executorService.isTerminated()){
            try {
                Thread.sleep(1000*5);  // 这里睡眠下主线程，不然其它线程还没执行完就被关闭了。
            }catch (InterruptedException e){
                e.printStackTrace();
            }
        }
        System.out.println("长度" + list.size());
    }

}

输出

ThreadId:12 start!
ThreadId:11 start!
ThreadId:12 stop!
ThreadId:11 stop!
ThreadId:14 start!
ThreadId:14 stop!
ThreadId:15 start!
ThreadId:15 stop!
ThreadId:13 start!
ThreadId:16 start!
ThreadId:16 stop!
ThreadId:17 start!
ThreadId:17 stop!
ThreadId:13 stop!
ThreadId:18 start!
ThreadId:18 stop!
ThreadId:19 start!
ThreadId:19 stop!
ThreadId:20 start!
ThreadId:20 stop!
长度9950

每次的输出结构都不同，偶尔还会抛出越界异常。

// 直接添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!! 
    elementData[size++] = e;   //应该就是在这里，在多线程的情况下很有可能出现重复添加了元素。
    return true;
}

Fail-Fast场景

fail-fast 机制在遍历一个集合时，当集合结构被修改，会抛出 Concurrent Modification Exception。

fail-fast 会在以下两种情况下抛出 Concurrent Modification Exception

（1）单线程环境

集合被创建后，在遍历它的过程中修改了结构。
注意 remove() 方法会让 expectModcount 和 modcount 相等，所以是不会抛出这个异常。

（2）多线程环境

当一个线程在遍历这个集合，而另一个线程对这个集合的结构进行了修改。

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 Concurrent Modification Exception。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}