[Java]-Collection源码分析-ArrayList 和线程安全

发表于 | 分类于 | 阅读次数

Java集合是我么最经常使用的工具，我们称这些集合类为容器，和数组的不同： 数组长度固定，集合类长度可变，数组存放基本类型，集合类存放对象的引用。

常用集合： List， Set， Map。

Collection UML:

要学习Collection，除了数据结构基础之外还要有Iterable概念

Iterable

Iterable接口为高效遍历更多的数据结构提供了支持。

常见的循环方式：

for 循环：

1
2
3
for (int i = 0, len = strings.size(); i < len; i++) {
    System.out.println(strings.get(i));
}

foreach循环

1
2
3
for (String var : strings) {
    System.out.println(var);
}

Iterator循环

1
2
3
4
Iterator iterator = strings.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

for循环针对数组这种可以直接取下标的类型，foreach则主要对类似链表的结构提供遍历支持，链表没有下标，所以使用for循环遍历会大大降低性能。Iterator实际上就是foreach。

但是什么样的集合可以用foreach遍历，怎么让对象支持foreach遍历就需要了解Iterator迭代器，迭代器为JAVA集合类对象提供foreach遍历的支持（只能向前不能退后）。

让一个对象实现foreach遍历需要实现Iterable/Iterator接口

Iterator接口的声明

1
2
3
4
5
public interface Iterator<E> {
    boolean hasNext();  //是否有下一个对象
    E next();   //hasnext为true时调用，返回下一个对象
    void remove(); // //hasnext为true时调用，删除当前值
}

Iterable接口的声明

1
2
3
public interface Iterable<T> {
    Iterator<T> iterator();  //只有一个方法：返回iterator对象。
}

这两个接口不合二为一的原因是：一个实现了Iterable接口的类可以实现多个Iterator内部类，如一个向前迭代器一个向后迭代器。

Iterator还有一个子接口，是为需要双向遍历数据时准备的，在后续分析ArrayList和LinkedList时都会看到它。它主要增加了以下几个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 是否有前一个元素
boolean hasPrevious();

// 获取前一个元素
E previous();

// 获取下一个元素的位置
int nextIndex();

// 获取前一个元素的位置
int previousIndex();

// 添加一个元素
void add(E e);

// 替换当前元素值
void set(E e);

Collection

接口可以继承，List、Queue和Set接口继承于Collection接口，所以Collection是一个超级接口,他直接继承于Iterable接口，所以所有的Collection集合类都能实现foreach循环。

Collection也是面向接口编程的典范，通过它可以在多种实现类间转换，这也是面向对象编程的魅力之一。

Collection提供了一些方便操作集合的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//返回集合的长度，如果长度大于Integer.MAX_VALUE，返回Integer.MAX_VALUE
int size();

//如果集合元素总数为0，返回true
boolean isEmpty();

//判断集合中是否包含指定的元素，其依据是equals()方法
boolean contains(Object o);

//返回一个包含集合中所有元素的数组
Object[] toArray();

//与上个类似，只是增加了类型的转换
<T> T[] toArray(T[] a);

//向集合中加入一个元素，如果成功加入则返回true，如果加入失败，或者因集合本身已经包含同个元素而不再加入时，返回false
boolean add(E e);

//从集合中删除指定元素的单个实例
boolean remove(Object o);

//如果集合包含指定集合中的所有元素，返回true
boolean containsAll(Collection<?> c);

//把指定集合中的所有元素添加到集合中，但在此期间，如果指定的集合发生了改变，可能出现意想不到的事情
boolean addAll(Collection<? extends E> c);

//从集合中删除所有包含在指定集合中的元素
boolean removeAll(Collection<?> c);

//仅保留集合中包含在指定集合中的元素
boolean retainAll(Collection<?> c);

//清空集合
void clear();

//将此方法抽象，是保证所有子类都覆写此方法，以保证equals的正确行为
boolean equals(Object o);

//同上
int hashCode();

//这个方法在JDK1.8中提供了默认的实现，会使用Iterator的形式删除符合条件的元素
default boolean removeIf(Predicate<? super E> filter){
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

Collection 接口有一个超级实现类AbstractCollection，为了减少实现类所需要实现的借口方法。

List

List接口的一些不同于Collection的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//在指定位置，将指定的集合插入到当前的集合中
boolean addAll(int index, Collection<? extends E> c);

//这是一个默认实现的方法，会通过Iterator的方式对每个元素进行指定的操作
default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

//排序，依据指定的规则对当前集合进行排序，可以看到，排序是通过Arrays这个工具类完成的。
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

//获取指定位置的元素
E get(int index);

//修改指定位置元素的值
E set(int index, E element);

//将指定元素添加到指定的位置
void add(int index, E element);

//将指定位置的元素移除
E remove(int index);

//返回一个元素在集合中首次出现的位置
int indexOf(Object o);

//返回一个元素在集合中最后一次出现的位置
int lastIndexOf(Object o);

//ListIterator继承于Iterator，主要增加了向前遍历的功能
ListIterator<E> listIterator();

//从指定位置开始，返回一个ListIterator
ListIterator<E> listIterator(int index);

//返回一个子集合[fromIndex, toIndex)，非结构性的修改返回值会反映到原表，反之亦然。
//如果原表进行了结构修改，则返回的子列表可能发生不可预料的事情
List<E> subList(int fromIndex, int toIndex);

相应的，她也有一个超级实现类AbstractList。

ArrayList

直接继承于AbstractList超级类，并实现了List接口，RandomAccess接口支持随机访问，Cloneable表示实现类支持克隆，具体表现为重写了clone方法，java.io.Serializable则表示支持序列化，如果需要对此过程自定义，可以重写writeObject与readObject方法

ArrayList其实是用数组实现的，是但是他是Resizable-array implementation of the <tt>List</tt> interface.就是说它可以动态的改变数组大小。为了实现这一点，需要有复制的过程，如声明一个大小为5的ArrayList（有参构造函数），前五个数据插入无序改变数组大小，若要继续添加元素，需要将数组扩容，声明一个更大容量的数组，将前五个元素复制再进行新的添加。这样的结构在数组元素很大时性能快速下降，但是有实现优化措施。接下来会进行研究

成员变量

1
2
3
4
5
6
7
8
//这是一个用来标记存储容量的数组，也是存放实际数据的数组。
//当ArrayList扩容时，其capacity就是这个数组应有的长度。
//默认时为空，添加进第一个元素后，就会直接扩展到DEFAULT_CAPACITY，也就是10
//这里和size区别在于，ArrayList扩容并不是需要多少就扩展多少的
transient Object[] elementData;

//这里就是实际存储的数据个数了
private int size;

构造函数

有参构造函数：

  • 参数为初始容量，生成一个大小为initialCapacity的类型为Object的数组,参数小于0抛出非法参数异常。
  • 参数是一个集合c，从另一个集合来构造， 调用toArray方法复制给elementData。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

无参构造函数：初始化为空数组{}，当插入第一个参数时数组大小会扩充为默认值：10

1
2
3
  public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public int size() {
        return size;
    }


public boolean isEmpty() {
    return size == 0;
}

public int indexOf(Object o) {
    if (o == null) { //null没有equals方法
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else { //用equals判断是否相同
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;//无此元素返回-1
}
    
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

//从后往前遍历
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//将数组截断为size大小
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
 
 //参数是类型，转为T类型的数组   
public <T> T[] toArray(T[] a) {
if (a.length < size)
    // Make a new array of a's runtime type, but my contents:
    return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
    a[size] = null;
return a;
}

增删改查和获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//查
public E get(int index) {
    rangeCheck(index); //检查index是否在合法范围

    return elementData(index);
}

//改
public E set(int index, E element) {  //返回修改前的值
    rangeCheck(index);//检查index是否在合法范围

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

增删涉及数组大小变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//增
public boolean add(E e) {//确定增加一个元素的话，容量是否允许，确保elementData数组的长度足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}


//判断数组大小是否满足minCapacity
private void ensureCapacityInternal(int minCapacity) {
    
    //调用ensureExplicitCapacity，把工作交出去
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}



private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
    //若数组是空，则扩充至默认值10或给出的最小容量，如前边叙述，向空数组添加元素时会扩充长度。
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
    
    
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); 
        //若需要的长度大于现在的数组长度，则调用grow扩充
    }
    
    
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //二进制右移，相当于除以2。扩充1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //若扩充后仍不满则，直接扩充为minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //若扩充后超出了最大范围（溢出）则调用hugeCapacity防止溢出
    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);
}

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;//返回新数组
}

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

至此整个扩容过程结束。首先创建一个空数组elementData，第一次插入数据时直接扩充至10，然后如果elementData的长度不足，就扩充1.5倍，如果扩充完还不够，就使用需要的长度作为elementData的长度。

但是数据量很大的时候还是会频繁拷贝影响性能，所以如果数据相较大可以用有参构造函数直接声明一个大容量的ArrayList，但是这样会一直占用较大内存。

我们也可以在添加元素之前提前根据添加操作次数扩容，来减少拷贝次数，且可以不用一直占用大内存。

1
2
3
4
5
6
7
8
9
10
11
12
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);
    }
}

删除：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除某个下标的元素
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);//把index之后的内容复制到index之前的元素的后边。
    elementData[--size] = null; // clear to let GC do its work
    //数组长度-1，让垃圾回收机制收回

    return oldValue;
}

结论： 了解了ArrayList的原理之后明白他实际上是用数组实现，虽然可以动态改变大小，但是改变大小由于需要进行拷贝所以是耗费性能的，虽然她的扩容机制已经做了优化（每次扩容1.5倍，减少拷贝次数），但是还是要根据情况使用，比如数据量大且对内存不做要求时可以在实例化的时候一步到位声明大数组，若对内存有要求可以根据业务需要在添加操作之前扩充足够的容量。

ArrayList还是和数组一样，更适合于数据随机访问，而不太适合于大量的插入与删除

了解了底层机制才能更好的使用，提高程序效率和内存使用，不踩坑

参考：https://www.jianshu.com/p/407afb4a267a

线程安全-ArrayList vs Vector

ArrayList是非线程安全的，Vector是线程安全的；HashMap是非线程安全的，HashTable是线程安全的；StringBuilder是非线程安全的，StringBuffer是线程安全的。

线程安全

　当多个线程类并发操作某类的某个方法，(在该方法内部)来修改这个类的某个成员变量的值，不会出错，则我们就说，该的这个方法是线程安全的。

　　某类的某方法是否线程安全的关键是：

　　(1) 该方法是否修改该类的成员变量（有没有数据共享）;

　　(2) 是否给该方法加锁(是否用synchronized关键字修饰），在调用该方法的过程中别的线程的调用无法执行

线程不安全

当多个线程类并发操作某类的某个方法，(在该方法内部)来修改这个类的某个成员变量的值，很容易就会发生错误，故我们就说，这个方法是线程不安全的。如果要把这个方法变成线程安全的，则用 synchronized关键字来修饰该方法即可。

当1线程正在使用或修改某个成员变量（共享数据），但是这个过程中线程2将该变量修改，那么线程1的执行结果会受到影响。

但是用synchronized进行同步控制影响了这个方法的效率，要慎重使用这个关键字

ArrayList， Vector

ArrayList是线程不安全的，Vector是线程安全的，如果需要多线程操作同一个对象，就需要用Vector，否则ArrayList有更高的效率。

但并不是非线程安全的就一定不安全，只有当不同线程操作同一个对象时才会有可能发生错误，如果每个线程都new一个ArrayList就不会发生这样的问题了。

modCount

经常看到类的成员变量modCount

修改次数modCount，这个变量记录了对象的修改次数，再Iterator中使用，Iterator中有变量expectedModCount也记录了对象的更改次数，在遍历的时候若expectedModCount和modCount不同则说明有其他线程已经修改了这个对象，抛出异常。

modCount通常在线程不安全的类中才会看到，是一个避免多线程操作错误的方式：fast-fail策略。所以当大家遍历那些非线程安全的数据结构时，尽量使用迭代器。