测试代码
package com.lly.springtest1.collection; import lombok.extern.slf4j.Slf4j; import java.util.ArrayList; import java.util.LinkedList; /** * @ClassName ICollection * @Description TODO * @Author lly * @Date 2019/3/5 9:29 AM * @Version 1.0 **/ @Slf4j public class ICollection { public static void test() { LinkedList<String> links = new LinkedList<>(); int len = 6553631; log.info(len + ""); long btime = System.currentTimeMillis(); for (int i = 0; i < len; i++) { links.add("sss"); } long etime = System.currentTimeMillis(); log.info("耗时:{},大小:{}", etime - btime, links.size()); long btime1 = System.currentTimeMillis(); ArrayList<String> arrays = new ArrayList<>(); for (int i = 0; i < len; i++) { arrays.add("sss"); } long etime1 = System.currentTimeMillis(); log.info("耗时:{},大小:{}", etime1 - btime1, arrays.size()); } public static void main(String[] args) { ICollection.test(); } } 复制代码
测试结果
此时我们的数量级别是百万级别,我们惊讶的发现ArrayList插入效率要比LinkedList快接近20倍,为什么?why?我们明明记得在学习java集合的时候,明确的知道是ArrayList查询快,增删慢的,LinkedList的特细则与之相反的,可是现实测试却跟定义不一样呢,那我们在多做点测试,改变数量级别看看十万,万,千级别的测试结果,我们改变插入集合的数据量大小测试。
首先降低到十万级别
发现测试的插入效率已经很接近了
万级别
这时候我们发现和十万级别的测试结果差不多,还是ArrayList插入快一点
接着我们降低到千级别
此时两者的效率差不多,还是没有体现出书中定义的2者关于插入效率的问题,问题还是没有得到解决,那么我们思考一下,上面的实验我们都是默认插入的末尾的,是否跟我么插入的顺序有关系吗,我们下面测试一下将数据插入的头部
package com.lly.springtest1.collection; import lombok.extern.slf4j.Slf4j; import java.util.ArrayList; import java.util.LinkedList; /** * @ClassName ICollection * @Description TODO * @Author lly * @Date 2019/3/5 9:29 AM * @Version 1.0 **/ @Slf4j public class ICollection { public static void test() { LinkedList<String> links = new LinkedList<>(); int len = 100000; log.info(len + ""); long btime = System.currentTimeMillis(); for (int i = 0; i < len; i++) { links.addFirst("sss"); } long etime = System.currentTimeMillis(); log.info("耗时:{},LinkedList大小:{}", etime - btime, links.size()); long btime1 = System.currentTimeMillis(); ArrayList<String> arrays = new ArrayList<>(); for (int i = 0; i < len; i++) { arrays.add(0,"sss"); } long etime1 = System.currentTimeMillis(); log.info("耗时:{},ArrayList大小:{}", etime1 - btime1, arrays.size()); } public static void main(String[] args) { ICollection.test(); } } 复制代码
此时我们发现,在万级别LinkedList的插入性能就看出来了
此时我们发现,在十万级别LinkedList的插入性能是ArrayList的100+倍,那么我们下面再测试一下在数组中间部分插入数据
package com.lly.springtest1.collection; import lombok.extern.slf4j.Slf4j; import java.util.ArrayList; import java.util.LinkedList; /** * @ClassName ICollection * @Description TODO * @Author lly * @Date 2019/3/5 9:29 AM * @Version 1.0 **/ @Slf4j public class ICollection { public static void test() { LinkedList<String> links = new LinkedList<>(); int len = 10000; log.info(len + ""); long btime = System.currentTimeMillis(); for (int i = 0; i < len; i++) { links.add(links.size() / 2, "sss"); } long etime = System.currentTimeMillis(); log.info("耗时:{},LinkedList大小:{}", etime - btime, links.size()); long btime1 = System.currentTimeMillis(); ArrayList<String> arrays = new ArrayList<>(); for (int i = 0; i < len; i++) { arrays.add(arrays.size() / 2, "sss"); } long etime1 = System.currentTimeMillis(); log.info("耗时:{},ArrayList大小:{}", etime1 - btime1, arrays.size()); } public static void main(String[] args) { ICollection.test(); } } 复制代码
数据量万级别Linkedlist插入效率比ArrayList慢20倍
数据量十万级别Linkedlist插入效率比ArrayList慢160+倍
LinkedList源码
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } 复制代码
ArrayList源码
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++; } 复制代码
ArrayList:影响ArrayList性能的主要因素是扩容和数组复制,但是当size很大时数组扩容影响就会变小,那么此时的效率就会提升,此时如果在中间部分插入数据时候,我们要插入的位置为i,数组长度是n,那么就要变动i之后的n-i的数据。
LinkedList源码
public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } 复制代码
可以看到LinkedList直接在头部时候不必遍历,所以效率很高,体现了LinkedList的插入效率高的特性
ArrayList源码解释同(指定位置插入)
LinkedList源码
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } 复制代码
LinkedList:用传入的值new一个Node对象,然后尾指针指向该新的Node
ArrayList源码
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } 复制代码
ArrayList:如果超出容量需要扩容,不需扩容时直接数组元素赋值
结论:当数据量越来越大时,ArrayList比LinkedList快
原因:当数据量大时,ArrayList每次扩容都能得到很大的新空间,解决了前期频繁扩容的劣势,而LinkedList虽然有尾指针,但是每次add都要将对象new成一个Node(而ArrayList直接数组对应位置元素赋值)
数据量/插入位置 | 头部 | 中间 | 尾部 |
---|---|---|---|
万 | LinkedList插入快 | ArrayList插入快 | ArrayList插入快 |
十万 | LinkedList插入快 | ArrayList插入快 | ArrayList插入快 |