CopyOnWriteArrayList源码解析-Java8

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CopyOnWriteArrayList源码解析-Java8，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10283字，纯文字阅读大概需要15分钟。

内容图文

目录

一.写时复制介绍

二.CopyOnWriteArrayList介绍

三.CopyOnWriteArrayList源码解析

　　3.1 重要属性

　　3.2 getArray和setArray

　　3.3 构造方法

　　3.4 获取元素

　　3.5 添加元素

　　　　3.5.1 追加元素

　　　　3.5.2 指定位置插入元素

　　3.6 删除元素

　　　　3.6.1 删除指定位置的元素

　　　　3.6.2 删除指定元素

　　3.7 修改元素

　　3.8 元素增删改查的总结

四.总结

一.写时复制介绍

　　写时复制（copy on write），具体的介绍可以查看百度百科-写时复制，这里就举一个简单的例子来介绍写时复制是什么样的。

有一份大家共享的文档，所有都可以查看、编辑这份文档；

小A和小B想要查看文档，那么他们俩可以将这份文档复印一份（人手一份），但是为了节约纸张和钱，他们俩就决定不复印文档了，两人先将就一下，一起查阅这份文档吧（共享）；

在小A和小B正在查看文档的过程中，小C想要修改文档，而修改文档的话，就会影响他们俩查看文档，于是小C就将文档复制了一份，将原件给小A和小B继续查阅文档（不影响他们俩），而小C就可以在复印的文档上进行修改了；

小C将文档修改完后，就将文档放回存放文档的地方；

而小A和小B正在查看的那份文档就没有意义了（等待小A和小B阅读后，就可以销毁了）；

小A和小B下一次再想看文档时，就拿到的是经过小C修改过后的文档了。

　　理解了上面这个过程，也就理解了“写时复制”的原理了。

　　原文地址：https://www.cnblogs.com/-beyond/p/13130040.html

二.CopyOnWriteArrayList介绍

　　Java中的ArrayList是一个非线程安全的集合类，也就是说，当多个线程对ArrayList进行并发读写时，就可能会出现问题。

　　虽然可以使用Vector来保证同步操作，解决线程安全问题，但是由于Vector只是简单的在接口上加synchronized关键字进行同步，即使synchronized已经做了很多优化（性能极大地提升），但是Vector中在方法级别加synchronized，同步的代码区域太大，吞吐量并不会太高。

　　CopyOnWriteArrayList，就是线程安全版的ArrayList，可以支持多线程并发修改获取数组元素，利用的就是上面写时复制的原理。

三.CopyOnWriteArrayList源码解析

3.1 重要属性

/**
 * 用于加锁（可重入，默认为非公平锁）
 */
final transient ReentrantLock lock = new ReentrantLock();

/**
 * 保存数据的数组
 */
private transient volatile Object[] array;

　　对的，CopyOnWriteArrayList就只有上面两个属性，比ArrayList少了很多，ArrayList中初始容量、扩容阈值、树化阈值、负载因子....

　　随着后面对源码的学习，就会知道CopyOnWriteArrayList中的数组（也就是array），每次都是毫不浪费，刚好装下所有元素（其实是每次添加元素的时候则增加一个位置，删除元素后就释放一个位置，所以数组的长度始终和元素的个数相同）。

3.2 getArray和setArray

　　CopyOnWriteArrayList中有两个私有的方法，用来获取和设置array属性值，几乎贯穿CopyOnWriteArrayList整个源码。

/**
 * 获取当前的数组
 */
final Object[] getArray() {
    return array;
}

/**
 * 将传入的数组替换掉已有的数组（修改数据后替换掉旧数组）
 */
final void setArray(Object[] a) {
    array = a;
}

3.3 构造方法

/**
 * 创建一个空数组的CopyOnWriteArrayList实例
 */
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

/**
 * 利用已有的集合元素创建CopyOnWriteArrayList实例
 */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements; // 副本

    if (c.getClass() == CopyOnWriteArrayList.class) {
        elements = ((CopyOnWriteArrayList<?>) c).getArray();
    } else {
        // 将传入的集合转为数组形式
        elements = c.toArray();
        if (elements.getClass() != Object[].class) {
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
    }

    // 将array属性设置指向本次创建的副本
    setArray(elements);
}

/**
 * 利用传入的数组来创建CopyOnWriteArrayList实例
 */
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

3.4 获取元素

　　获取元素，和ArrayList接口一样，都是get(index)，但是需要注意的是，CopyOnWriteArrayList在get元素的时候并不做数组越界检测。

/**
 * 获取数组index位置的元素
 */
public E get(int index) {
    // 先调用getArray获取数组，然后调用内部的get方法进行返回元素
    return get(getArray(), index);
}

/**
 * 获取指定数组的指定位置元素
 */
private E get(Object[] a, int index) {
    return (E) a[index];
}

3.5 添加元素

3.5.1 追加元素

/**
 * 追加元素到集合中
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 先尝试获取锁，未获取到锁则阻塞
    lock.lock();
    try {
        // 获取数组
        Object[] elements = getArray();
        int len = elements.length;

        // 创建一个新的数组（新数组长度比旧数组长度大1）
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 将元素追加到最后新多出来的一个位置（最后）
        newElements[len] = e;

        // 将新数组替换掉旧数组
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

3.5.2 指定位置插入元素

/**
 * 在指定位置插入元素
 */
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取当前数组和数组长度
        Object[] elements = getArray();
        int len = elements.length;

        // 插入位置越界检测
        if (index > len || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + len);
        }

        // 计算需要移动的元素个数
        Object[] newElements;
        int numMoved = len - index;

        if (numMoved == 0) {
            // 需要移动元素的个数为0，表示追加（直接申请len+1长度的数组）
            newElements = Arrays.copyOf(elements, len + 1);
        } else {
            // 有元素需要移动，先申请len+1长度的数组
            newElements = new Object[len + 1];
            
            // 将旧数组中0 - index-1元素拷贝到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 将旧数组中index以及后面的元素拷贝到新数组中（index位置空余）
            System.arraycopy(elements, index, newElements, index + 1, numMoved);
        }
        
        // 将新元素放入空出的index位置
        newElements[index] = element;
        
        // 新数组替换掉旧数组
        setArray(newElements);
    } finally {
        // 解锁
        lock.unlock();
    }
}

3.6 删除元素

3.6.1 删除指定位置的元素

/**
 * 删除指定位置的元素
 */
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取当前最新的数组
        Object[] elements = getArray();
        int len = elements.length;

        // 获取index位置的元素（要删除的元素）
        E oldValue = get(elements, index);

        // 计算要移动的元素
        int numMoved = len - index - 1;
        if (numMoved == 0) {
            // 如果要移动的元素为0，证明删除的最后一个元素
            // 则直接创建一个新数组（长度为len-1），并将前len-1个元素拷贝到新数组中，并替换掉旧数组
            setArray(Arrays.copyOf(elements, len - 1));
        } else {
            // 删除的元素不是在最后，那么就申请len-1长度的数组
            Object[] newElements = new Object[len - 1];

            // 将0~len-1和len+1~end的元素拷贝到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);
            
            // 替换掉旧数组
            setArray(newElements);
        }
        
        // 返回删除的元素
        return oldValue;
    } finally {
        // 解锁
        lock.unlock();
    }
}

3.6.2 删除指定元素

/**
 * 删除元素（删除成功范围true，未找到或者删除失败返回false）
 */
public boolean remove(Object o) {
    // 获取当前数组
    Object[] snapshot = getArray();

    // 在数组中查找要删除的元素
    int index = indexOf(o, snapshot, 0, snapshot.length);

    // index<0，表示未找到元素；否则进行删除元素
    return (index < 0) ? false : remove(o, snapshot, index);
}

/**
 * 在elements数组中的index到fence范围内查找元素o
 *
 * @param o        要查找的元素
 * @param elements 在该数组中查找
 * @param index    查找的其实位置
 * @param fence    屏障（查找结束的位置）
 * @return 如果查找到元素，则返回元素所在位置；如果没有查找到，则返回-1
 */
private static int indexOf(Object o, Object[] elements, int index, int fence) {
    // 使用循环进行遍历数组，从头到尾找到第一个匹配的元素位置
    if (o == null) {
        for (int i = index; i < fence; i++) {
            if (elements[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = index; i < fence; i++) {
            if (o.equals(elements[i])) {
                return i;
            }
        }
    }

    // 未找到元素，则返回-1
    return -1;
}

/**
 * 删除snapshot数组中index位置的元素o
 * 不是直接删除快照数组中的index位置的元素，而是经过一番比较，确定要删除的元素的真实位置
 * 然后在申请一个新数组，将index以外的其他元素拷贝到新数组中，并替换新数组，以此达到删除的效果
 */
private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取数组
        Object[] current = getArray();
        int len = current.length;

        // 如果传入的数组快照和当前的最新数组不匹配（发生了增删）
        if (snapshot != current) findIndex:{
            // 获取新数组的长度，与传入的index进行比较（确定查找范围，以小者为准）
            int prefix = Math.min(index, len);

            // 遍历数组，
            for (int i = 0; i < prefix; i++) {
                // 如果数组快照和新数组的元素不匹配，并且最新数组的该位置上的元素就是要删除的元素
                // 此时修改要index（改为要删除元素当前的最新位置），并结束循环
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    index = i;
                    break findIndex;
                }
            }

            // 如果新数组的长度小于传入的要删除元素的index，则证明未找到该元素
            if (index >= len) {
                return false;
            }

            // 如果当前数组的index位置为要删除的元素（找到要删除的元素位置），则跳出if
            if (current[index] == o) {
                break findIndex;
            }

            // 在最新数组中查找要删除的元素，如果最新数组未找到要删除的元素，则删除失败，返回false
            index = indexOf(o, current, index, len);
            if (index < 0) {
                return false;
            }
        }

        // 当前最新的数组为len，因为找到了要删除的元素，则申请一个新的数组（长度为len-1）
        Object[] newElements = new Object[len - 1];

        // 将当前最新的数据，0~index-1的元素拷贝到新数组中
        System.arraycopy(current, 0, newElements, 0, index);
        // 将当前最新的数据，index+1及后面的数据拷贝到新数组中
        System.arraycopy(current, index + 1, newElements, index, len - index - 1);

        // 使用新数组替换掉旧数组，因为删除了元素，所以返回true
        setArray(newElements);
        return true;
    } finally {
        // 解锁
        lock.unlock();
    }
}

3.7 修改元素

/**
 * 修改index位置的元素，设置为element，并返回旧值
 */
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取旧数组中index位置的值
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        // 如果index位置的值和要修改的值不相同，那需要进行修改操作
        if (oldValue != element) {
            // 获取当前数组的长度
            int len = elements.length;
            
            // 创建一个新数组（新数组长度和旧数组长度保持一致），并将旧数组中全部元素拷贝到新数组中
            Object[] newElements = Arrays.copyOf(elements, len);
            // 修改新数组中的index位置的元素
            newElements[index] = element;
            
            // 新数组替换掉旧数组
            setArray(newElements);
        } else {
            // 如果index位置的值和要修改的值相同，那么不用进行修改操作（避免申请数组、拷贝的开销）
            setArray(elements);
        }
        
        // 返回旧值
        return oldValue;
    } finally {
        lock.unlock();
    }
}

3.7 元素增删改的总结

　　上面在添加元素、删除元素、修改元素中，可以看到，CopyOnWriteArrayList每次进行写操作的时候，都是这样一个步骤：

　　1.加锁；

　　2.获取当前数组（snapshot快照）；

　　3.创建新数组，然后在新数组中进行修改操作；

　　4.将修改完后的新数组替换掉snapshot快照数组；

　　5.解锁。

　　需要注意的是，当一个线程A在遍历CopyOnWriteArrayList时，当另外一个线程B对CopyOnWriteArrayList进行了修改操作，线程B修改完成后（已经将新数组替换掉旧数组），但是线程A查看的仍旧是旧的数组（snapshot），除非重新获取数组。

四.总结

　　CopyOnWriteArrayList的源码也挺简单的，但是需要注意的是，CopyOnWriteArrayList最好用在读多写少的场景，从前面介绍的源码中，可以看到每次修改操作，都会进行加锁、申请新数组和拷贝复制，如果频繁修改，则可能造成系统资源浪费和效率降低（频繁申请数组，可能会触发GC）。

　　原文地址：https://www.cnblogs.com/-beyond/p/13130040.html

内容总结

以上是互联网集市为您收集整理的CopyOnWriteArrayList源码解析-Java8全部内容，希望文章能够帮你解决CopyOnWriteArrayList源码解析-Java8所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端