JDK源码阅读_集合框架(2)_List的常见疑问分析

/ 默认分类 / 0 条评论 / 1072浏览

集合框架jdk源码java并发编程

Q1：ArrayList和LinkedList的比较？

其实，他们之间的比较，就是动态数组和链表之间的比较

操作 | ArrayList| LinkedList ---|---|--- 插入头部 |可以直接随机下标获取0位置元素然后赋值 O(1)| 直接操作新元素和头结点指针，无需遍历 O(1) 插入尾部 |可以直接随机下标获取size-1位置元素然后赋值 O(1)| 直接操作新元素和尾结点指针，无需遍历 O(1) 插入中间指定位置 |可以直接随机下标获取然后赋值 O(1)| 需要遍历到指定的待插入元素节点位置然后移动指针 O(n) 获取头部 |直接下标获取 O(1)| 直接返回头指针元素 O(1) 获取尾部 |直接下标获取 O(1)| 直接返回尾指针元素 O(1) 获取中间指定元素 |可以直接随机下标获取然后赋值O(1)| 需要遍历然后移动指针 o(n) 删除头部 | stop，stop，stop......想啥呢，还在继续跑偏？？？

这是我以前在网上看到的一个比较，我只能说，连ArrayList的简单操作源码都没有看过就敢这样比较，哈哈哈

首先ArrayList在插入的时候，插入尾部的时候，可以直接将size，长度下标赋值给当前待插入的元素，所以为O(1),但是如果遇到刚好需要扩容，那么就需要进行一次数组全量拷贝，这样效率就会低了.

    public boolean add(E e) {
        //这里可能会扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

如果是插入头部或者其他中间部位，那么都是需要进行数组元素的移位（给新插入的元素让出位置），并且在移位之前如果运气不好还会进行扩容，所以效率其实是比较低的，上面出现错误的理解，因为以为直接将元素覆盖即可了

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

在LinkedList中插入头部和尾部都是直接O（1）的操作，直接移动头尾指针（在LinkedList中保存了头尾指针，典型的空间换时间），如果是插入中间部位，那么就需要遍历链表了，即O（n），效率也是比较低的

对于查找，ArrayList中可以直接根据下标获取，所以是O（1）,LinkedList如果是直接获取头节点或者尾节点（其实也就是头尾节点周围不是很远的地方，因为这样就不需要进行很长的遍历），那么可以认为速度很快，但是如果获取中间部位并且需要遍历很久，那么就会显得效率很低了，LinkedList也做了优化 ,按照位置靠近前还是后来决定使用头结点遍历还是尾节点遍历

    Node<E> node(int index) {
        // assert isElementIndex(index);
        //如果更靠近头部
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

删除其实也就和插入也是一样的道理了

Q2:为什么ArrayList和LinkedList中每次进行add或者其他操作的时候都需要修改modCount属性？

先来写一段代码看一下，下面的几种情况

 @Test
    public void testModCount(){
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        list.remove(1);
        System.out.println(list);
    }

[1, 3, 4]

@Test
    public void testModCount1(){
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            Integer val = iterator.next();
            if(val == 2) {
                iterator.remove();
            }
        }
        System.out.println(list);
    }

[1, 3, 4]

如果在迭代的时候,另外一个线程直接操作元素进行删除

@Test
    public void testModCount2() throws InterruptedException {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            list.remove(3);
            System.out.println("线程2已经删除元素");
        }).start();
        Iterator<Integer> iterator = list.iterator();
        System.out.println("线程1迭代器已创建");
        while (iterator.hasNext()){
            Integer val = iterator.next();
            if(val == 3) {
                TimeUnit.SECONDS.sleep(2);
                System.out.println("线程1迭代器开始删除元素");
                try{
                    iterator.remove();
                    System.out.println("线程1迭代器开始删除元素成功");
                }catch(Exception e)
                {
                   System.out.println("线程1迭代器开始删除元素失败");
                   e.printStackTrace();
                }

            }
        }
        System.out.println(list);

    }

线程1迭代器已创建
线程2已经删除元素

线程1迭代器开始删除元素
线程1迭代器开始删除元素失败
java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:966)
	at java.util.LinkedList$ListItr.remove(LinkedList.java:921)

[1, 2, 3]

如果在迭代的时候,另外一个线程另起一个迭代器进行删除

@Test
    public void testModCount3() throws InterruptedException {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            Iterator<Integer> iterator1 = list.iterator();
            System.out.println("线程2迭代器已创建");
            while (iterator1.hasNext()){

                Integer next = iterator1.next();
                if(next == 2){
                    System.out.println("线程2迭代器开始删除元素");
                    try{
                        iterator1.remove();
                        System.out.println("线程2迭代器删除元素成功");
                    }catch(Exception e)
                    {
                       System.out.println("线程2迭代器删除元素失败");
                       e.printStackTrace();
                    }
                }
            }
        }).start();
        Iterator<Integer> iterator = list.iterator();
        System.out.println("线程1迭代器已创建");
        while (iterator.hasNext()){
            Integer val = iterator.next();
            if(val == 3) {
                TimeUnit.SECONDS.sleep(2);
                System.out.println("线程1迭代器开始删除元素");
                try{
                    iterator.remove();
                    System.out.println("线程1迭代器删除元素成功");
                }catch(Exception e)
                {
                   System.out.println("线程1迭代器删除元素失败");
                   e.printStackTrace();
                }
            }
        }
        System.out.println(list);

    }


线程1迭代器已创建
线程2迭代器已创建
线程2迭代器开始删除元素
线程2迭代器删除元素成功
线程1迭代器开始删除元素
线程1迭代器删除元素失败
java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:966)
	at java.util.LinkedList$ListItr.remove(LinkedList.java:921)
	
[1, 3, 4]

综上,可以看出,当迭代器在遍历的时候,迭代器是可以进行删除的操作的(删除当前元素),但是如果此时还有另外一个线程对同一个集合 进行修改操作(删除或添加),那么迭代器就会在进行删除的时候抛出ConcurrentModificationException异常
我们来看下源码,在list中,每次对集合结构的改变的操作都会被记录起来,也就是我们看到的modCount++语句,比如在add()和remove()方法中都会存在,这条执行语句,来记录当前集合的结构被修改的次数,我们再来看下,迭代器中的一个属性:

以LinkedList的迭代器实现为例:

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

其中存在一个属性为expectedModCount,然后LinkedList中迭代器的删除代码是这样的:

        public void remove() {
            //主要就是这句
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            //删除元素(即上面说的删除链表节点的代码,其中会进行modCount++)
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            //可以看到,这里进行了expectedModCount++
            expectedModCount++;
        }

可以看到,如果发现modCount != expectedModCount则抛出ConcurrentModificationException异常

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

首先，从前面的源码分析我们可以看出，ArrayList和LinkedList都是线程不安全的，crud的操作没有进并发控制。 从上面得到测试可以看出，当集合在迭代的时候，不允许外部其他线程对该集合进行修改操作 当前线程的修改操作也不允许是集合自身的remove方法，必须使用 迭代器的remove，为什么要这样做，这主要是为了实现fail-fast机制，也就是出错，立刻停止的机制，为了保证我们获取到的数据是准确的没有被其他线程修改的脏数据，可以认为这样实现了并发控制，保证线程安全，虽然这种线程安全的控制方法没有起到最终的作用，因为直接一旦出现多线程并发操作就直接停止程序报错，但这样也让LinkedList和ArrayList具备了更高的性能，关于List中的线程安全的实现，我们下一篇文章中再介绍

jdk中关于modCount的注释：

The number of times this list has been structurally modified Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
结构修改是指改变列表的大小，或以其他方式干扰列表，从而导致正在进行的迭代可能产生不正确的结果。

     * <p>This field is used by the iterator and list iterator implementation
     * returned by the {@code iterator} and {@code listIterator} methods.
     * If the value of this field changes unexpectedly, the iterator (or list
     * iterator) will throw a {@code ConcurrentModificationException} in
     * response to the {@code next}, {@code remove}, {@code previous},
     * {@code set} or {@code add} operations.  This provides
     * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
     * the face of concurrent modification during iteration.
     
     fail-fast

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/05/17 00:11