ArrayList的动态扩容、ModCount及fail-fas

上一篇 <<<ArrayList的添加和删除操作实现原理图解
下一篇 >>>

Arraylist底层是如何实现扩容

原理：计算出新的容量，并将老的数据拷贝到新的对象数组中，数组长度为新的容量。

>> 1表示除以2的意思，扩容为原有数组的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);

<< : 左移运算符，num << 1,相当于num乘以2
>> : 右移运算符，num >> 1,相当于num除以2
>>> : 无符号右移，忽略符号位，空位都以0补齐

ArrayList线程是否安全

不安全，添加和删除的时候都会调用全局变量modCount++;方法。读取的时候会判断全局变量modCount 和当前时候 expectedModCount的值是否一致。多线程时全局变量一致在变，expectedModCount不是最新数据的时候就会抛出异常，出现脏读的现象。

/****************************线程安全测试****************************/
/**
* 报错：
* Exception in thread "Thread-1" java.util.ConcurrentModificationException
*  at java.util.ArrayList.forEach(ArrayList.java:1252)
*  at com.jarye.arraylist.ArrayListTest.lambda$newThreadList$0(ArrayListTest.java:47)
*  at java.lang.Thread.run(Thread.java:748)
*
*  原因：线程不安全，添加和删除的时候都会执行：modCount++;
*                  查询的时候：expectedModCount = modCount; modCount == expectedModCount
*                  由于多线程在走，查询赋值的时候，和真正读取到全局变量modCount不一致，就会抛出异常ConcurrentModificationException();
*/
ArrayListTest test = new ArrayListTest();
test.newThreadJaryeList();
test.newThreadJaryeList();

private void newThreadJaryeList(){
     new Thread(()->{
         for(int i=0;i<10;i++){
             jl.add(i+"");
             jl.forEach(System.out::println);
         }
     }).start();
 }

Arraylist集合中ModCount++作用

modCount为全局变量，保证线程安全。

Arraylist fail-fast机制实现原理

为了解决集合中结构发生改变的时候，快速失败的机制。数组有添加或删除的时候，全局变量modCount++，查询的时候判断请求时的modCount和全局modCount是否一致，不一致则直接抛出异常。

如何防御fail-fast的产生

CopyOnWriteArrayListTest使用的是ReentrantLock锁
Vector使用的是synchronized

/****************************线程安全测试****************************/
/**
 * 添加一切正常，原因：
 *
 * 1、使用了ReentrantLock锁
 * 2、实现机制：
 * a、获得数组元素 Object[] elements = getArray();
 * b、计算长度 int len = elements.length;
 * c、数组容量增1 Object[] newElements = Arrays.copyOf(elements, len + 1);
 * d、数据添加到末位 newElements[len] = e;
 * f、重新设置新的数组 setArray(newElements);
 *
 *  原因：线程不安全，添加和删除的时候都会执行：modCount++;
 *                  查询的时候：expectedModCount = modCount; modCount == expectedModCount
 *                  由于多线程在走，查询赋值的时候，和真正读取到全局变量modCount不一致，就会抛出异常ConcurrentModificationException();
 *
 * 删除也用了ReentrantLock锁机制
 *
 */
CopyOnWriteArrayListTest test = new CopyOnWriteArrayListTest();
test.newThreadList();
test.newThreadList();

private void newThreadList(){
    new Thread(()->{
        for(int i=0;i<10;i++){
            ol.add(i+"");
            ol.forEach(System.out::println);
        }
    }).start();
}

/****************************线程安全测试****************************/
/**
 * 添加一切正常，原因：
 *
 *
 *
 * 和arraylist对比：
 * 共同点： 1、都实现了List接口 2、底层都是用Object[]实现 3、添加删除都有modCount++,遍历都有modCount == expectedModCount判断
 * 不同点：
 * 1、初始化
 *  a、arrayList 长度为0的空对象数组
 *  b、vector 默认长度为10的空对象数组
 * 2、扩容
 *  a、arrayList 1.5倍的速度扩容
 *  b、vector 2倍或自定义capacityIncrement增长容量进行扩容
 *  newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
 * 3、线程安全
 * a、arrayList 线程不安全
 * b、vector 线程安全，添加和删除方法都加了synchronized
 *
 */
 VectorTest test = new VectorTest();
test.newThreadList();
test.newThreadList();


private void newThreadList(){
    new Thread(()->{
        for(int i=0;i<10;i++){
            ol.add(i+"");
            ol.forEach(System.out::println);
        }
    }).start();
}