一、ArrayList
- 1、初步小理解

一、ArrayList

1、初步小理解

默认值是多少？

（1）查看源码可知默认值是10，但是没找到初始化为10的代码？

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
  * Constructs an empty list with an initial capacity of ten.
  */
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

（2）查看新增方法，在calculateCapacity中可知默认的容量是10。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
// 确定容量
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
// 判断是否需要扩容
 private void ensureExplicitCapacity(int minCapacity) {
          modCount++;
          // 如果最小需要空间比elementData的内存空间要大，则需要扩容
          if (minCapacity - elementData.length > 0)
              //扩容
              grow(minCapacity);
      }
// 计算出容量，小于10，则返回10（可知默认的容量是10）
private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
// 进行扩容 1.5倍
private void grow(int minCapacity) {
          // 获取到ArrayList中elementData数组的内存空间长度
          int oldCapacity = elementData.length;
         // 扩容至原来的1.5倍
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         // 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组，
          // 不够就将数组长度设置为需要的长度
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         //若预设值大于默认的最大值检查是否溢出
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         // 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
         // 并将elementData的数据复制到新的内存空间
         elementData = Arrays.copyOf(elementData, newCapacity);
     }

由上述代码也可以看出，扩容是扩容到原来的1.5倍

为什么线程不安全

add方法没有加synchronized

线程不安全示例

public class NoSafeDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i <= 30; i++) {
            new Thread(()->{
               list.add(UUID.randomUUID().toString().substring(0,9));
                System.out.println(list);
            }).start();
        }
        // 报错：java.util.ConcurrentModificationException 线程不安全常见的异常（并发修改异常）
          // 报错原因：并发争抢修改导致
    }
}

报错位置如下，可知

modCount是ArrayList中的一个成员变量。它表示该集合实际被修改的次数
expectedModCount 是 ArrayList中的一个内部类——Itr中的成员变量。expectedModCount表示这个迭代器期望该集合被修改的次数。其值是在ArrayList.iterator方法被调用的时候初始化的。只有通过迭代器对集合进行操作，该值才会改变。

A线程 add走到checkForComodification()的时候，B线程刚add改变了modCount的值，就会出现modCount != expectedModCount

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}
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;
        Itr() {}
        public boolean hasNext() {
            return cursor != size;
        }
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            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];
        }

变成线程安全

1、使用方法Collections.synchronizedList()

public class SafeDemo2 {
    public static void main(String[] args) {
        List<String> list = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i <= 30; i++) {
            new Thread(()->{
               list.add(UUID.randomUUID().toString().substring(0,9));
                System.out.println(list);
            }).start();
        }
    }
}

这个方法会返回一个新的同步list，如下。

 public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
    }

该方法的新建和查询有一个互斥锁（mutex），每次只能要么查询要么新建

public boolean add(E e) {
            synchronized (mutex) {return c.add(e);}
}
 public E get(int index) {
            synchronized (mutex) {return list.get(index);}
 }

2、使用java.util.concurrent包中的CopyOnWriteArrayList，写时复制

public class SafeDemo3 {
    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();
        for (int i = 0; i <= 30; i++) {
            new Thread(()->{
               list.add(UUID.randomUUID().toString().substring(0,9));
                System.out.println(list);
            }).start();
        }
    }
}

参考源码add()

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
public E get(int index) {
        return get(getArray(), index);
}

CopyOnWrite容器即写时复制容器，往一个容器中添加元素的时候，不直接往当前容器Object[]添加，而是先将当前容器进行copy，复制出一个新容器 Object[] newElements，新容器容量比原容器大1，将新元素放入新容器的最后，最后将原容器的引用指向新容器setArray(newElements);这样做的好处是可以对CopyOnWrite容器进行并发读，而不需要加锁，因为当前容器不会添加任何元素，所以CopyOnWrite容器也是一种读写分离的思想，读和写时不同的容器。写的时候加锁，保证线程安全。

注意和ArrayList增加元素的区别：ArrayList是先设置好一个具备容量的数组，然后将元素放进去；而CopyOnWriteArrayList是直接在新的数组里添加元素，然后将老数组的引用指向新数组。

Java 进阶之路

2-集合