Java集合类

集合中的fail-fast

fail-fast其实是一种设计思想，即在程序出现错误时不再继续向下执行，而是抛出异常退出。

for (String name : names) {
    if (...) {
        names.remove(name);
    }
}

上面这段代码就会触发fail-fast错误，抛出异常ConcurrentModificationException。

产生的原因：增强的for循环本质上是一个语法糖，实际上是通过迭代器实现。

通过查看报错位置可以发现，抛出异常的原因是modCount和expectedModCount两个变量不相同。

• modCount：成员变量，记录集合被修改的次数
• expectedModCount：内部类Itr的成员变量，表示这个迭代器预期该集合被修改的次数，在Itr被创建时被初始化为当前modCount值，只有通过迭代器修改集合才会更新该值

而上面的remove代码的核心部分fastRemove更新了modCount，但是由于增强for循环创建了Itr，而没有使用迭代器去删除元素，就导致了modCount和expectedModCount不一致。

解决方法：使用普通for循环...

ArrayList

概述

• RandomAccess：标识类，并无实现，标识该类支持快速随机访问
• Cloneable：可以调用clone()方法克隆对象
• java.io.Serializable：可序列化

和 LinkedList 的比较

• 是否线程安全
• 底层数据结构
• 增删查的复杂度
• 内存空间占用

ArrayList扩容机制

1、ArrayList提供了三个构造函数

要注意的是如果使用无参构造，底层的数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，结合后面的扩容机制可以发现当DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次add元素时就会将扩容至DEFAULT_CAPACITY(10)。

而EMPTY_ELEMENTDATA是真实空的数组（因为只有传进来的容量为0的时候才会赋该值）

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() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

2、每次调用add函数都会经历一次"扩容"（可能没有真实发生）

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

minCapacity：完成add操作的最小扩容量

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 扩容
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity); // max(10, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

实际进行扩容的函数是grow(int)，经过一系列的判断后通过Arrays.copyOf()进行扩容。

newCapacity：扩容机制指定的扩容量（原容量1.5倍）

MAX_ARRAY_SIZE：最大扩容量（Integer.MAX_VALUE-8）

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为原容量的1.5倍
    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:
    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;
}

总的来说扩容机制比较简单，主要是存在多个capacity需要比较，需要弄清这些capacity所代表的含义。

几个重要的函数源码

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

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 使用了System.arraycopy来实现元素的后移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

提供给外部的显示扩容函数ensureCapacity

注意所有的扩容都出现了DEFAULTCAPACITY_EMPTY_ELEMENTDATA（第一次扩容的特殊性）

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}