集合笔记

ArrayList

实现接口

List

表示集合类
RandomAccess

表示支持随机访问
Cloneable

表示已经重写clone方法，非Object的clone方法，Object的clone方法的访问权限为protected，不适合调用
java.io.Serializable

序列化

add()

数组添加方法有两种追加和插入

add(E e)

追加方法

1，首先调用ensureCapacityInternal()方法判断当前数组是否已满，满则进入4，未满则进入5

2，判断是否初次调用add方法，是则进入到3

3，数组会初始化到DEFAULT_CAPACITY = 10大小

4，进入grow方法，调用Arrays.copyOf()方法扩容，默认扩容1.5倍

5，使用elementData[size++] = e;追加值
add(int index, E element)
插入与追加类似

1，检验下标合法性,rangeCheckForAdd(index);

2，判断数组是否需要扩容ensureCapacityInternal(size + 1);

3，调用System.arraycopy(src, srcPos, dest, destPos, length)方法，将~ixd—size~的元素复制至~ixd+1—size~
1
2
3
4
5
>src：原数组
>srcPos：原数组起点
>dest：目标数组
>destPos：目标数组起点
>length：复制多少元素至目标数组

remove()

数组删除有两种删除元素和删除指定下标元素

remove(Object o)

可以看到remove传入的对象是Object，说明不一定要删除泛型定义的类型，只有equals()方法符合即可

1，从先往后使用equals()对比数组内元素

2，使用fastRemove()方法删除元素，System.arraycopy()方法覆盖要删除的元素，置空数组最后一个元素elementData[–size] = null;
remove(int index)

1，rangeCheck(index);检测下标合法性

2，System.arraycopy()方法覆盖要删除的元素

3，置空数组最后一个元素elementData[–size] = null;

Arrays.copyOf()和System.arraycopy()

System.arraycopy()

System.arraycopy()是个本地方法，实现高效率复制元素,

本质是将原数组src的~srcPos—(srcPos+length)~范围的元素复制到目标数组dest的~destPos—(destPos+length)~内

不会发生数组的扩容，就是用来复制数组

/**
src：原数组
srcPos：原数组起点
dest：目标数组
destPos：目标数组起点
length：复制多少元素至目标数组
**/
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

Arrays.copyOf()

Arrays.copyOf()本质是调用System.arraycopy()，不过Arrays.copyOf()方法中会创建一个新的数组并返回，也就是会产生数组的扩容

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;

区别

Arrays.copyOf()因为需要扩容，所以会产生新数组，
Arrays.copyOf()本质是调用System.arraycopy()
System.arraycopy()用于复制元素

缩容

之前我一直在找remove方法中的缩容方法但是没找到，也就是删除元素并不会发生缩容，

但是ArrayList类中是定义了缩容方法的，但是内部并没有调用

实现也很简单，创建一个和size大小一直的数组把原数组复制进去并返回

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

快速失败

快速失败是用来避免多线程对线程不安全的集合进行操作，造成错误，针对这种情况应当快速失败。

fail-fast 机制是java集合(Collection)中的一种错误机制。它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。

以下代码就会产生快速失败

public static void main(String[] args) {
        // 构建ArrayList
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        for (int i : list) {
            System.out.println(i);
            list.remove(1);
        }
    }

使用增强for遍历时，相当于使用迭代器

ArrayList内部的迭代器为

public ListIterator<E> listIterator(final int index) {
            checkForComodification();
            rangeCheckForAdd(index);
            final int offset = this.offset;

            return new ListIterator<E>() {
                int cursor = index;
                int lastRet = -1;
                int expectedModCount = ArrayList.this.modCount;

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

其中引发快熟失败的主要因素是expectedModCount = ArrayList.this.modCount;

modCount:是记录集合发生变化的次数

在add()方法和remove()方法等都可以看到modCount++

迭代器进行迭代时会经常调用checkForComodification方法

如果发现modCount != expectedModCount则会马上抛出异常

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

鸟窝

Java集合