Java List集合比较

太过爱你忘了你带给我的痛 2022-09-29 15:44 233阅读 0赞

# 概述 #

Java集合类位于java.util包下，主要包含Collection和Map两大类，在该包下还包含一些常用的集合工具类如Collections等。这里我们可以看一下java下集合框架的整体继承关系图，如下  
![这里写图片描述][SouthEast]

其中，Queue（队列）是在Java SE1.5中引入的新的集合类，除此之外在Java SE1.5中还引入了一些用于多线程并发的集合框架，这个在这里不做介绍。

今天，我们主要介绍的框架类Colleciton下的一些常用的集合类。这里我们可以看下Collection的整体继承关系图，该图中隐藏了一些抽象类及接口，仅仅列举了具体实现类。如下所示。  
![这里写图片描述][SouthEast 1]

# List介绍 #

List是有序的Collection，依赖索引能够准确对元素进行CRUD操作。同时，List允许插入重复的元素（包括null）。

通过上面的继承图可知，List类下主要有四个实现类：

1.  ArrayList：基于线性表的数据结构，内部使用数组实现（可变数组，自动扩容）。ArrayList的相关操作都没有进行同步，所以是线程不安全的。
2.  LinkedList：基于链表（而且是双向链表）的数据结构，LinkedList除了实现List接口外，还实现了Queue接口，所以LinkedList可以被当做堆栈（stack），队列（queue）或双向队列（deque）。同样LinkedList和ArrayList一样，也是线程不安全的。
3.  Vector：基本的实现ArrayList一样，但是Vector是线程同步的。
4.  Stack：继承自Vector，主要实现栈的功能（后进先出）。

其中Vector和Stack都不被建议使用了，主要原因就是Vector的操作是线程安全的导致操作效率较低，同时使用LinkedList也可以实现Stack的功能。

## List CRUD性能比较 ##

测试代码如下：

import java.util.*;
    
    /**
     *
     * @author zhangke
     */
    public class TestList {
        
    
        private static final int COUNT = 20000;
    
        private static ArrayList arrayList = new ArrayList<>();
        private static LinkedList linkedList = new LinkedList<>();
        private static Vector vector = new Vector<>();
    
        private static Random random = new Random();
    
        private static final String FIRST_INSERT = "首位插入：list.add(0, i)";
        private static final String LAST_INSERT = "末位插入：list.add(i, i)";
        private static final String RANDOM_INSERT = "随机插入：list.add(random.nextInt(i), i)";
    
        private static final String FIRST_QUERY = "首位查询：list.get(0)";
        private static final String LAST_QUERY = "末位查询：list.get(i)";
        private static final String RANDOM_QUERY = "随机查询：list.get(random.nextInt(i))";
    
        private static final String FIRST_DELETE = "首位删除：list.remove(0)";
        private static final String LAST_DELETE = "末位删除：list.remove(i)";
        private static final String RANDOM_DELETE = "随机删除：list.remove(random.nextInt(i))";
    
        public static void main(String[] args) {
    
            System.out.println(RANDOM_INSERT);
            randomInsert(arrayList);
            randomInsert(linkedList);
            randomInsert(vector);
    
            System.out.println("\n" + RANDOM_QUERY);
            randomQuery(arrayList);
            randomQuery(linkedList);
            randomQuery(vector);
    
            System.out.println("\n" + RANDOM_DELETE);
            randomDelete(arrayList);
            randomDelete(linkedList);
            randomDelete(vector);
        }
    
        /**
         * 插入
         */
        private static void randomInsert(List list) {
            long startTime = System.currentTimeMillis();
            Random random = new Random();
    
            list.add(0);
            for (int i = 1; i < COUNT; i++) {
    
                // 首位插入
                // list.add(0, i);
                // 末位插入
                // list.add(i, i);
                // 随机插入
                list.add(random.nextInt(i), i);
            }
    
            long interval = System.currentTimeMillis() - startTime;
            System.out.println("\t" + getListName(list) + " : 随机插入 " + COUNT + "个元素花费时间：" + interval + "ms");
        }
    
        /**
         * 删除
         */
        private static void randomDelete(List list) {
            long startTime = System.currentTimeMillis();
            for (int i = COUNT - 1; i >= 1; i--) {
                // 首位删除
                // list.remove(0);
                // 末位删除
                // list.remove(i);
                // 随机删除
                list.remove(random.nextInt(i));
            }
    
            long interval = System.currentTimeMillis() - startTime;
            System.out.println("\t" + getListName(list) + " : 随机删除 " + COUNT + "个元素花费时间：" + interval + "ms");
        }
    
        /**
         * 查询
         * 
         * @param list
         */
        private static void randomQuery(List list) {
            long startTime = System.currentTimeMillis();
    
            for (int i = 0; i < COUNT; i++) {
    
                // list.get(0);
    
                // list.get(i);
    
                list.get(random.nextInt(COUNT));
            }
    
            long interval = System.currentTimeMillis() - startTime;
            System.out.println("\t" + getListName(list) + " : 随机读取 " + COUNT + "个元素花费时间：" + interval + "ms");
        }
    
        /**
         * 获取List具体实现类名称
         */
        private static String getListName(List list) {
            if (list instanceof LinkedList) {
                return "LinkedList";
            } else if (list instanceof ArrayList) {
                return "ArrayList";
            } else if (list instanceof Vector) {
                return "Vector";
            }
    
            return null;
        }
    
    }

对不同情况下的操作结果如下：

/***     插入        ***/
    首位插入：list.add(0, i)
        ArrayList : 随机插入 20000个元素花费时间：46ms
        LinkedList : 随机插入 20000个元素花费时间：3ms
        Vector : 随机插入 20000个元素花费时间：44ms
    
    末位插入：list.add(i, i)
        ArrayList : 随机插入 20000个元素花费时间：3ms
        LinkedList : 随机插入 20000个元素花费时间：2ms
        Vector : 随机插入 20000个元素花费时间：2ms
    
    
    随机插入：list.add(random.nextInt(i), i)
        ArrayList : 随机插入 20000个元素花费时间：23ms
        LinkedList : 随机插入 20000个元素花费时间：433ms
        Vector : 随机插入 20000个元素花费时间：24ms
    
    
    /***     查询        ***/
    首位查询：list.get(0)
        ArrayList : 随机读取 20000个元素花费时间：1ms
        LinkedList : 随机读取 20000个元素花费时间：1ms
        Vector : 随机读取 20000个元素花费时间：1ms
    
    末位查询：list.get(i)
        ArrayList : 随机读取 20000个元素花费时间：1ms
        LinkedList : 随机读取 20000个元素花费时间：150ms
        Vector : 随机读取 20000个元素花费时间：1ms
    
    
    随机查询：list.get(random.nextInt(i))
        ArrayList : 随机读取 20000个元素花费时间：1ms
        LinkedList : 随机读取 20000个元素花费时间：1135ms
        Vector : 随机读取 20000个元素花费时间：1ms
    
    /***     删除        ***/
    首位删除：list.remove(0)
        ArrayList : 随机删除 20000个元素花费时间：41ms
        LinkedList : 随机删除 20000个元素花费时间：2ms
        Vector : 随机删除 20000个元素花费时间：40ms
    
    末位删除：list.remove(i)
        ArrayList : 随机删除 20000个元素花费时间：1ms
        LinkedList : 随机删除 20000个元素花费时间：1ms
        Vector : 随机删除 20000个元素花费时间：1ms
    
    随机删除：list.remove(random.nextInt(i))
        ArrayList : 随机删除 20000个元素花费时间：22ms
        LinkedList : 随机删除 20000个元素花费时间：493ms
        Vector : 随机删除 20000个元素花费时间：23ms

总结如下：  
![这里写图片描述][SouthEast 2]

## List性能比较结论 ##

根据上面的测试Log，我们可以得出以下结论：

1.  在不考虑线程同步的，ArrayList和Vector在操作上性能基本是一样的。
2.  在首位插入数据时，LinkedList的性能要明显优于ArrayList，这是因为ArrayList每次在首位插入一次数据，后面的数据都要被整体后移一位，随着数组的长度越来越大，被消耗的时间也就越多。而LinkedList在首位插入只需要修改指针即可。
3.  在末位插入数据，LinkedList的性能和ArrayList基本保持一致。ArrayList在插入时会直接在数组末位添加一位，而LinkedList也只需要在末位添加一位（此时LinkedList会保存末位元素，不需要寻址）
4.  随机插入大量数据的时候，ArrayList的性能要好于LinkedList。虽然ArrayList每次在插入的时候都需要移动大量的元素，但是LinkedList在每次插入到指定位置时，都需要重新寻址，在寻址上回耗费大量的时间，所以会影响LinkedList的插入性能。
5.  LinekedList和ArrayList在插入和删除上的操作性能基本相同。
6.  对于随机访问，ArrayList基本要明显优于LinkeList（首位查询除外）。

通过上面的结论我们不难发现，有很多说法认为LinkedList做插入和删除更快，这样的说法存在一定的局限性。

1.  LinkedList做增删操作时，慢在寻址，快在只需要修改元素的前驱和后继就能完成。
2.  ArrayList做增删操作时，快在寻址，慢在数组元素的整体移动上。

对于上面所提到的寻址我们可以理解为随机访问，为什么这样说呢？  
因为LinkedList在每次做插入的时候都要先找到所要插入的位置，这就是一个随机访问的过程。所以在增删时主要是寻址的过程会耗费占用整个过程中的大部分时间，这个我们可以通过阅读LinkedList的add(int, E)方法可知。如下：

public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    
        // 寻址的方法
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            // 这个地方就是每次添加时寻址的过程，这里采用了二分查找的思想
            // 因为LinkedList是一个双链表，可以从两头分别查找
            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;
            }
        }
    
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }

如果我们不考虑寻址的问题。LinkedList单独的增删还是非常快的，因为只需要修改前驱和后继即可。

## for和foreach方式对List进行遍历 ##

在上面的测试代码中，我们可以分别使用for和foreach方式对ArrayList和LinkedList对集合进行遍历，代码和结果如下：

private static void randomQuery(List list) {
            long startTime = System.currentTimeMillis();
    
            // foreach方式遍历
            for (Object object : list) {
            }
    
            // for方法遍历
    //      for (int i = 0; i < COUNT; i++) {
        
    //           list.get(i);
    //      }
    
            long interval = System.currentTimeMillis() - startTime;
            System.out.println("\t" + getListName(list) + " : 随机读取 " + COUNT + "个元素花费时间：" + interval + "ms");
        }

// for方式遍历结果
        ArrayList : 随机读取 20000个元素花费时间：1ms
        LinkedList : 随机读取 20000个元素花费时间：1035ms
    
        // foreach方式遍历结果
        ArrayList : 随机读取 20000个元素花费时间：1ms
        LinkedList : 随机读取 20000个元素花费时间：2ms

通过结果可以发现，使用for和foreach方式遍历ArrayList基本上性能差距不大，但是对于LinkedList而言，foreach遍历的性能要明显优于for，对于这样的结果又是什么原因呢？

其实，造成for循环遍历LinkedList比较慢的原因也可以通过上面一段LinkedList.get(int)代码可以说明，当每次使用for遍历时，都需要进行寻址，这样随着集合长度的增加寻址会花费越来越多的时间，这样会造成for循环花费的时间越来越多。

而对于使用foreach循环，是因为foreach循环底层使用的是iterator的方式完成遍历的，这里我们看看LinkedList里面Iterator中的遍历的方法，也就是next()方法，代码如下：

public E next() {
                checkForComodification();
                if (!hasNext())
                    throw new NoSuchElementException();
    
                // lastReturned 表示当前遍历的元素
                lastReturned = next;
                next = next.next;
                nextIndex++;
                return lastReturned.item;
            }

通过代码一目了然，通过iterator遍历linkedList每次都会记住下一个元素的位置，这样在遍历的时候屏蔽了寻址的过程，所以使用foreach完成linkedlist的遍历性能会大大提高。

对于遍历我们可以得出结论：

1.  对于ArrayList我们使用for或者foreach方式遍历都可以。
2.  但是对于LinkedList，最好使用foreach方式遍历避免使用for方式遍历。

[SouthEast]: /images/20220708/6f37da22b9cc4ddfaec97dd5a8abaf44.png
[SouthEast 1]: /images/20220708/0718097bc6d245128e34f9c8208952dd.png
[SouthEast 2]: /images/20220708/25bf75b6f37740b8bd479cb7420a0e74.png