ArrayList

ArrayList的底层是动态数组，它的容量能动态增长。

索引存取元素，有序，可重复，允许多个null

1、ArrayList初始容量

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;

// 无参构造器，初始化为空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 传入初始容量，根据容量初始化
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);
    }
}
// 根据传入集合做初始化，若集合为空，则为空，还要对得到的数组判断是否为对象数组类型
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;
    }
}

2、扩容

ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍

// list结构变化的次数（影响迭代器）
protected transient int modCount = 0; 
// 一些JVM需要保存数组头信息，申请更大的数组可能会OOM
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

// 第一次添加元素，size=0
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e; // 末尾插入元素
    return true;
}
// 对容量判断，不足则扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 若使用无参构造器初始化，则容量为默认10和需要的最小容量之间的最大值（第一次添加变为10）
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity; // 若使用带参构造器初始化，不管是否为空，都取需要的最小容量，即第一次添加为1
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 记录结构变动

    // overflow-conscious code
    if (minCapacity - elementData.length > 0) // 容量不足，扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5倍
    if (newCapacity - minCapacity < 0) // 1.5倍不够，则取需要的最小容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 最大的数组容量不满足，最大可取Integer.MAX_VALUE
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

3、删除元素

安全的删除元素：使用迭代器

使用for删除，会导致ConcurrentModificationException

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("1111");
        list.add("2222");
        list.add("3333");
        list.add("4444");
        list.add("5555");

        for (String str : list){
            if (str == "2222"){
                list.remove(str);
            }
        }

        for (String str : list){
            System.out.println(str);
        }
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at file.Test.main(Test.java:15)

Process finished with exit code 1

反编译后代码为

import java.util.ArrayList;
import java.util.Iterator;

public class Test {
   public static void main(String[] var0) {
      ArrayList var1 = new ArrayList();
      var1.add("1111");
      var1.add("2222");
      var1.add("3333");
      var1.add("4444");
      var1.add("5555");
      Iterator var2 = var1.iterator();

      String var3;
      while(var2.hasNext()) {
         var3 = (String)var2.next();
         if(var3 == "2222") {
            var1.remove(var3); // 迭代器中调用了list的remove方法
         }
      }

      var2 = var1.iterator();
      while(var2.hasNext()) {
         var3 = (String)var2.next();
         System.out.println(var3);
      }
   }
}

ArrayList的remove方法：

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
}

迭代器的变动次数modCount

 private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;  // 初始化时为当前list的变动次数

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification(); // 先判断modCount
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
     
     	final void checkForComodification() {
            if (modCount != expectedModCount)  // list调用remove后已经加1，不一致
                throw new ConcurrentModificationException();
        }
     // ...
 }

4、迭代器

Iterator

Iterator模式用同一种逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来，不需要了解集合内部实现便可以遍历集合元素，统一使用 Iterator 提供的接口去遍历。它的特点是更加安全，因为它可以保证，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常

主要有三个方法：hasNext()、next()和remove()

**ListIterator **

ListIterator 是 Iterator的增强版。

• ListIterator遍历可以是逆向的，因为有previous()和hasPrevious()方法，而Iterator不可以。
• ListIterator有add()方法，可以向List添加对象，而Iterator却不能。
• ListIterator可以定位当前的索引位置，因为有nextIndex()和previousIndex()方法，而Iterator不可以。
• ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
• ListIterator只能用于遍历List及其子类，Iterator可用来遍历所有集合

5、fail fast

fast-fail是Java集合的一种错误机制。当多个线程对同一个集合进行操作时，就有可能会产生fast-fail事件。例如：当线程a正通过iterator遍历集合时，另一个线程b修改了集合的内容，此时modCount（记录集合操作过程的修改次数）会加1，不等于expectedModCount，那么线程a访问集合的时候，就会抛出ConcurrentModificationException，产生fast-fail事件。边遍历边修改集合也会产生fast-fail事件（上面例子）。

解决方法：

• 使用Colletions.synchronizedList方法或在修改集合内容的地方加上synchronized。这样的话，增删集合内容的同步锁会阻塞遍历操作，影响性能。
• 使用CopyOnWriteArrayList来替换ArrayList。在对CopyOnWriteArrayList进行修改操作的时候，会拷贝一个新的数组，对新的数组进行操作，操作完成后再把引用移到新的数组（每写一个就要复制一次，很耗时，推荐读多写少的场景）

6、CopyOnWrite

Copy-On-Write，写时复制。当我们往容器添加元素时，不直接往容器添加，而是先将当前容器进行复制，复制出一个新的容器，然后往新的容器添加元素，添加完元素之后，再将原容器的引用指向新容器。这样做的好处就是可以对CopyOnWrite容器进行并发的读而不需要加锁，因为当前容器不会被修改

缺点：

• 内存占用问题。由于CopyOnWrite的写时复制机制，在进行写操作的时候，内存里会同时驻扎两个对象的内存。
• CopyOnWrite容器不能保证数据的实时一致性，可能读取到旧数据。

CopyOnWriteArrayList

CopyOnWriteArrayList中add方法添加的时候是需要加锁的，保证同步，避免了多线程写的时候复制出多个副本。读的时候不需要加锁，如果读的时候有其他线程正在向CopyOnWriteArrayList添加数据，还是可以读到旧的数据。

CopyOnWrite并发容器用于读多写少的并发场景。

优点：

读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。Java的list在遍历时，若中途有别的线程对list容器进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的list容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。

缺点：

一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC；

二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据

7、fail safe

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的

8、让集合不能被修改

Collections包下的unmodifiableMap/unmodifiableList/unmodifiableSet方法，通过这个方法返回的集合，是不可以修改的。如果修改的话，会抛出 java.lang.UnsupportedOperationException异常

List<String> list = new ArrayList<>();
list.add("1111");
list.add("2222");

List list1 = Collections.unmodifiableList(list);

list1.remove(1);

报错：
    Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.Collections$UnmodifiableList.remove(Collections.java:1319)
	at file.Test.main(Test.java:18)

public static <T> List<T> unmodifiableList(List<? extends T> list) {
    return (list instanceof RandomAccess ?
            new UnmodifiableRandomAccessList<>(list) :
            new UnmodifiableList<>(list));
}

9、ArrayList、Vector、LinkedList

ArrayList与Vector：

• ArrayList在内存不够时扩容为原来的1.5倍，Vector是扩容为原来的2倍。

• Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为操作Vector效率比较低。

ArrayList与LinkedList：

• ArrayList基于动态数组实现，LinkedList基于链表实现
• 对于随机index访问的get和set方法，ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止
• 新增和删除元素，LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedList实例化对象需要时间外，只需要修改指针即可

10、ArrayDeque

ArrayDeque实现了双端队列，内部使用循环数组实现，默认大小为16。它的特点有：

1. 在两端添加、删除元素的效率较高
2. 根据元素内容查找和删除的效率比较低。
3. 没有索引位置的概念，不能根据索引位置进行操作。

ArrayDeque和LinkedList都实现了Deque接口，如果只需要从两端进行操作，ArrayDeque效率更高一些。如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除（LinkedList有相应的 api，如add(int index, E e)），则应该选LinkedList。

ArrayDeque和LinkedList都是线程不安全的，可以使用Collections工具类中synchronizedXxx()转换成线程同步

11、ConcurrentLinkedQueue

非阻塞队列。高效的并发队列，使用链表实现。可以看做一个线程安全的 LinkedList，通过 CAS 操作实现。

如果对队列加锁的成本较高则适合使用无锁的 ConcurrentLinkedQueue 来替代。适合在对性能要求相对较高，同时有多个线程对队列进行读写的场景

对于非阻塞队列，一般情况下建议使用offer(插入队尾)、poll（获取并移除队头）和peek（获取队头）三个方法，不建议使用add和remove方法。因为使用offer、poll和peek三个方法可以通过返回值判断操作成功与否，而使用add和remove方法却不能达到这样的效果（失败抛异常）

12、阻塞队列

阻塞队列是java.util.concurrent包下重要的数据结构，BlockingQueue提供了线程安全的队列访问方式：当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞等待直到队列非满；从阻塞队列取数据时，如果队列已空，线程将会阻塞等待直到队列非空。并发包下很多高级同步类的实现都是基于BlockingQueue实现的。BlockingQueue 适合用于作为数据共享的通道。

使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。

阻塞队列和一般的队列的区别就在于：

• 多线程支持，多个线程可以安全的访问队列

• 阻塞操作，当队列为空的时候，消费线程会阻塞等待队列不为空；当队列满了的时候，生产线程就会阻塞直到队列不满

本栏目推荐文章
• ArrayList源码阅读
• 24-集合（主要介绍ArrayList）
• java，ArrayList类
• 浅析 ArrayList
• Java 数组和ArrayList排序
• Java 字符串、数组、ArrayList转换
• 【JavaSE】集合Collection{List(ArrayList, LinkedList), Set(TreeSet, HashSet, LinkedHashSet)} + Map(HashMap, TreeMap, LinkedHashMap)
• 第1章. 动态数组(ArrayList)
• java练习：json字符串转map、arrayList
• java集合框架(三)之ArrayList的常见使用

ArrayListarraylist源码 arraylist1 linkedlist arraylist arraylist对象 arraylist java arraylist方式 arraylist源码06 juc4_arraylist arraylist元素java arraylist基础java