jdk11源码--CopyOnWriteArrayList源码分析

布满荆棘的人生 2022-03-15 11:28 421阅读 0赞

> 更多java源码分析请见：jdk11源码分析系列文章专栏：[Java11源码分析][Java11]

### 文章目录 ###

*  欢迎关注本人公众号
 *  概述
 *  基本属性
 *  创建\`CopyOnWriteArrayList\`
 *  add(E e)
 *  add(int index, E element)
 *   *  System.arraycopy
     *  关于@HotSpotIntrinsicCandidate
 *  get(int index)
 *  iterator 迭代器

# 欢迎关注本人公众号 #

![在这里插入图片描述][20200515113638671.jpg_pic_center]

# 概述 #

我们都知道`CopyOnWriteArrayList`是线程安全的列表，其内部是数组结构，并且适用于读多写少的应用场景。  
当写比较频繁时不要使用`CopyOnWriteArrayList`，应该使用其他的数据结构代替。  
接下来就从源码角度分析一下为什么会有以上的特性。

# 基本属性 #

//锁
    final transient Object lock = new Object();
    
    /** 内部真实存放数据的数据结构，它只能通过getArray/setArray方法访问. */
    private transient volatile Object[] array;

其中lock是`CopyOnWriteArrayList`实现的关键。类中所有的修改操作都会使用这个全局锁，保证只有一个线程可以对数据进行修改。  
array使用`volatile` 变量修饰，确保可见性，一个线程修改以后其他线程可以获取到最新修改后的值。

# 创建`CopyOnWriteArrayList` #

创建一个空的CopyOnWriteArrayList时，比较简单，就是初始化一个长度是0的数组。

public CopyOnWriteArrayList() { 
        setArray(new Object[0]);
    }

# add(E e) #

添加元素的逻辑也是异常的简单粗暴：

*  首先获取锁
 *  获取当前数组的长度
 *  现有数组copy到一个新的数组，新数组长度=现有数组长度+1
 *  将新元素添加到新数组最后一个位置

public boolean add(E e) { 
        synchronized (lock) { 
            Object[] es = getArray();
            int len = es.length;
            es = Arrays.copyOf(es, len + 1);
            es[len] = e;
            setArray(es);
            return true;
        }
    }

# add(int index, E element) #

想数组中指定位置添加元素。  
原理同上，也是需要拷贝一份数组，并且长度+1.  
唯一的区别是要拷贝两次，将index在新数组中的位置预留出来存放新的元素。详见下面代码注释

public void add(int index, E element) { 
        synchronized (lock) { 
            Object[] es = getArray();
            int len = es.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException(outOfBounds(index, len));
            Object[] newElements;
            int numMoved = len - index;//计算需要移动几个元素。这里指的是index位置后面的元素需要逐个向后移动一位
            if (numMoved == 0)//新元素追加在末尾
                newElements = Arrays.copyOf(es, len + 1);
            else { 
                newElements = new Object[len + 1];
                //通过两次System.arraycopy对数组进行复制，预留出index在新数组中对应的空位。
                System.arraycopy(es, 0, newElements, 0, index);
                System.arraycopy(es, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;
            setArray(newElements);
        }
    }

## System.arraycopy ##

@HotSpotIntrinsicCandidate
    public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);

参数：

*  Object src : 原数组
 *  int srcPos : 从元数据的起始位置开始
 *  Object dest : 目标数组
 *  int destPos : 目标数组的开始起始位置
 *  int length : 要copy的数组的长度

这是一个native方法，并且是有`@HotSpotIntrinsicCandidate`修饰的。所以该方法不仅是本地方法，而且是虚拟机固有方法。在虚拟机中通过手工编写汇编或其他优化方法来进行 Java 数组拷贝，这种方式比起直接在 Java 上进行 for 循环或 clone 是更加高效的。数组越大体现地越明显。

## 关于@HotSpotIntrinsicCandidate ##

这个注解是 HotSpot VM 标准的注解，被它标记的方法表明它为 HotSpot VM 的固有方法， HotSpot VM 会对其做一些增强处理以提高它的执行性能，比如可能手工编写汇编或手工编写编译器中间语言来替换该方法的实现。虽然这里被声明为 native 方法，但是它跟 JDK 中其他的本地方法实现地方不同，固有方法会在 JVM 内部实现，而其他的会在 JDK 库中实现。在调用方面，由于直接调用 JVM 内部实现，不走常规 JNI lookup，所以也省了开销。  
由于这需要阅读JVM虚拟机中的源码，留作后续再深入研究。

# get(int index) #

get的方法和通常的数组操作一样。  
注意：这里没有加锁，

public E get(int index) { 
      return elementAt(getArray(), index);
    }
    final Object[] getArray() { 
        return array;
    }
    static <E> E elementAt(Object[] a, int index) { 
        return (E) a[index];
    }

# iterator 迭代器 #

`CopyOnWriteArrayList`中提供了迭代器的操作。

> 注意：这个迭代器实际上是现有array的一个拷贝，所以他不用添加锁。但是会有**脏数据**的情况。因为在迭代期间，其他线程修改了数据以后，这个迭代器中拷贝的数据看不到最新的数据。

Iterator()方法和listIterator()方法实现是一样的，只不过返回值的类型不同，在使用时差别不大：

public Iterator<E> iterator() { 
        return new COWIterator<E>(getArray(), 0);
    }
    
    public ListIterator<E> listIterator() { 
        return new COWIterator<E>(getArray(), 0);
    }
    
    //这里面所有的修改方法均不可用
    static final class COWIterator<E> implements ListIterator<E> { 
        /** 数组array的快照 */
        private final Object[] snapshot;
        /** 游标 */
        private int cursor;
    
        COWIterator(Object[] es, int initialCursor) { 
            cursor = initialCursor;
            snapshot = es;//在这里进行快照赋值
        }
    
        public boolean hasNext() { 
            return cursor < snapshot.length;
        }
    
        public boolean hasPrevious() { 
            return cursor > 0;
        }
    
        @SuppressWarnings("unchecked")
        public E next() { 
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }
    
        @SuppressWarnings("unchecked")
        public E previous() { 
            if (! hasPrevious())
                throw new NoSuchElementException();
            return (E) snapshot[--cursor];
        }
    
        public int nextIndex() { 
            return cursor;
        }
    
        public int previousIndex() { 
            return cursor - 1;
        }
    
        public void remove() { 
            throw new UnsupportedOperationException();
        }
    
        public void set(E e) { 
            throw new UnsupportedOperationException();
        }
    
        public void add(E e) { 
            throw new UnsupportedOperationException();
        }
    
        @Override
        public void forEachRemaining(Consumer<? super E> action) { 
            Objects.requireNonNull(action);
            final int size = snapshot.length;
            int i = cursor;
            cursor = size;
            for (; i < size; i++)
                action.accept(elementAt(snapshot, i));
        }
    }

编写一个测试类来验证这个迭代器：

public static void main(String[] args) throws InterruptedException { 
            CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList();
            list.add(1);
            list.add(2);
            list.add(3);
    
            System.out.println(list.toString());
    
            new Thread(() -> { 
                ListIterator<Integer> integerListIterator = list.listIterator();
                Integer next = integerListIterator.next();
                System.out.println(next+"*******");
                try { 
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) { 
                    e.printStackTrace();
                }
                next = integerListIterator.next();
                System.out.println(next+"*******");
            }).start();
    
            new Thread(() -> { 
                try { 
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) { 
                    e.printStackTrace();
                }
                list.clear();
                System.out.println(list.toString());
            }).start();
        }

输出结果：

[1, 2, 3]
    1*******
    []
    2*******

可见，在其他线程修改了数据以后，迭代器里的还是老数据。这也就是上面所说的读到了脏数据。.

官方文档中有队这个iterater的注释：

* <p>This is ordinarily too costly, but may be <em>more</em> efficient
     * than alternatives when traversal operations vastly outnumber
     * mutations, and is useful when you cannot or don't want to
     * synchronize traversals, yet need to preclude interference among
     * concurrent threads.  The "snapshot" style iterator method uses a
     * reference to the state of the array at the point that the iterator
     * was created. This array never changes during the lifetime of the
     * iterator, so interference is impossible and the iterator is
     * guaranteed not to throw {@code ConcurrentModificationException}.
     * The iterator will not reflect additions, removals, or changes to
     * the list since the iterator was created.  Element-changing
     * operations on iterators themselves ({@code remove}, {@code set}, and
     * {@code add}) are not supported. These methods throw
     * {@code UnsupportedOperationException}.

大体意思也就是说：迭代器创建的时候会生成一个对数组状态的引用（快照），也就是COWIterator.snapshot。这个快照在迭代器的声明周期中不会发生变化，不会收到其他线程的干扰。并且不会抛出ConcurrentModificationException异常。迭代器创建后，不支持修改的操作，也不会反映其他线程对CopyOnWriteArrayList数据的任何变更。

CopyOnWriteArrayList在每次更新时都会复制一份，然后修改。所以老的数据还在，除非被JVM垃圾回收掉。这也是为什么上面迭代器可以读取到数据的原因之一。

> 更多java源码分析请见：jdk11源码分析系列文章专栏：[Java11源码分析][Java11]

[Java11]: https://it007.blog.csdn.net/column/info/30895
[20200515113638671.jpg_pic_center]: /images/20220315/88ca31d68c5744428a7bba09f232ae31.png