Java性能调优实战
刘超
金山软件西山居技术经理
立即订阅
7535 人已学习
课程目录
已完结 48 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 怎样才能做好性能调优?
免费
模块一 · 概述 (2讲)
01 | 如何制定性能调优标准?
02 | 如何制定性能调优策略?
模块二 · Java编程性能调优 (10讲)
03 | 字符串性能优化不容小觑,百M内存轻松存储几十G数据
04 | 慎重使用正则表达式
05 | ArrayList还是LinkedList?使用不当性能差千倍
加餐 | 推荐几款常用的性能测试工具
06 | Stream如何提高遍历集合效率?
07 | 深入浅出HashMap的设计与优化
08 | 网络通信优化之I/O模型:如何解决高并发下I/O瓶颈?
09 | 网络通信优化之序列化:避免使用Java序列化
10 | 网络通信优化之通信协议:如何优化RPC网络通信?
11 | 答疑课堂:深入了解NIO的优化实现原理
模块三 · 多线程性能调优 (10讲)
12 | 多线程之锁优化(上):深入了解Synchronized同步锁的优化方法
13 | 多线程之锁优化(中):深入了解Lock同步锁的优化方法
14 | 多线程之锁优化(下):使用乐观锁优化并行操作
15 | 多线程调优(上):哪些操作导致了上下文切换?
16 | 多线程调优(下):如何优化多线程上下文切换?
17 | 并发容器的使用:识别不同场景下最优容器
18 | 如何设置线程池大小?
19 | 如何用协程来优化多线程业务?
20 | 答疑课堂:模块三热点问题解答
加餐 | 什么是数据的强、弱一致性?
模块四 · JVM性能监测及调优 (6讲)
21 | 磨刀不误砍柴工:欲知JVM调优先了解JVM内存模型
22 | 深入JVM即时编译器JIT,优化Java编译
23 | 如何优化垃圾回收机制?
24 | 如何优化JVM内存分配?
25 | 内存持续上升,我该如何排查问题?
26 | 答疑课堂:模块四热点问题解答
模块五 · 设计模式调优 (6讲)
27 | 单例模式:如何创建单一对象优化系统性能?
28 | 原型模式与享元模式:提升系统性能的利器
29 | 如何使用设计模式优化并发编程?
30 | 生产者消费者模式:电商库存设计优化
31 | 装饰器模式:如何优化电商系统中复杂的商品价格策略?
32 | 答疑课堂:模块五思考题集锦
模块六 · 数据库性能调优 (8讲)
33 | MySQL调优之SQL语句:如何写出高性能SQL语句?
34 | MySQL调优之事务:高并发场景下的数据库事务调优
35 | MySQL调优之索引:索引的失效与优化
36 | 记一次线上SQL死锁事故:如何避免死锁?
37 | 什么时候需要分表分库?
38 | 电商系统表设计优化案例分析
39 | 数据库参数设置优化,失之毫厘差之千里
40 | 答疑课堂:MySQL中InnoDB的知识点串讲
模块七 · 实战演练场 (4讲)
41 | 如何设计更优的分布式锁?
42 | 电商系统的分布式事务调优
43 | 如何使用缓存优化系统性能?
44 | 记一次双十一抢购性能瓶颈调优
结束语 (1讲)
结束语 | 栉风沐雨,砥砺前行!
Java性能调优实战
登录|注册

05 | ArrayList还是LinkedList?使用不当性能差千倍

刘超 2019-05-30
你好,我是刘超。
集合作为一种存储数据的容器,是我们日常开发中使用最频繁的对象类型之一。JDK 为开发者提供了一系列的集合类型,这些集合类型使用不同的数据结构来实现。因此,不同的集合类型,使用场景也不同。
很多同学在面试的时候,经常会被问到集合的相关问题,比较常见的有 ArrayList 和 LinkedList 的区别。
相信大部分同学都能回答上:“ArrayList 是基于数组实现,LinkedList 是基于链表实现。”
而在回答使用场景的时候,我发现大部分同学的答案是:“ArrayList 和 LinkedList 在新增、删除元素时,LinkedList 的效率要高于 ArrayList,而在遍历的时候,ArrayList 的效率要高于 LinkedList。”这个回答是否准确呢?今天这一讲就带你验证。

初识 List 接口

在学习 List 集合类之前,我们先来通过这张图,看下 List 集合类的接口和类的实现关系:
我们可以看到 ArrayList、Vector、LinkedList 集合类继承了 AbstractList 抽象类,而 AbstractList 实现了 List 接口,同时也继承了 AbstractCollection 抽象类。ArrayList、Vector、LinkedList 又根据自我定位,分别实现了各自的功能。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《Java性能调优实战》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(52)

  • 陆离 置顶
    对于arraylist和linkedlist的性能以前一直都是人云亦云,大家都说是这样那就这样吧,我也从来没有自己去验证过,没想过因操作位置的不同差异还挺大。
    当然这里面有一个前提,那就是arraylist的初始大小要足够大。
    思考题是第一个是正确的,第二个虽然用的是foreach语法糖,遍历的时候用的也是迭代器遍历,但是在remove操作时使用的是原始数组list的remove,而不是迭代器的remove。
    这样就会造成modCound != exceptedModeCount,进而抛出异常。

    作者回复: 陆离同学一直保持非常稳定的发挥,答案非常准确!

    2019-05-30
    35
  • 刘天若Warner 置顶
    老师,为什么第二种就会抛出`ConcurrentModificationException`异常呢,我觉得第一种迭代器会抛这个异常啊

    作者回复: for(:)循环[这里指的不是for(;;)]是一个语法糖,这里会被解释为迭代器,在使用迭代器遍历时,ArrayList内部创建了一个内部迭代器iterator,在使用next()方法来取下一个元素时,会使用ArrayList里保存的一个用来记录List修改次数的变量modCount,与iterator保存了一个expectedModCount来表示期望的修改次数进行比较,如果不相等则会抛出异常;

    而在在foreach循环中调用list中的remove()方法,会走到fastRemove()方法,该方法不是iterator中的方法,而是ArrayList中的方法,在该方法只做了modCount++,而没有同步到expectedModCount。

    当再次遍历时,会先调用内部类iteator中的hasNext(),再调用next(),在调用next()方法时,会对modCount和expectedModCount进行比较,此时两者不一致,就抛出了ConcurrentModificationException异常。

    所以关键是用ArrayList的remove还是iterator中的remove。

    2019-05-30
    17
  • 皮皮
    第一种写法正确,第二种会报错,原因是上述两种写法都有用到list内部迭代器Iterator,而在迭代器内部有一个属性是exceptedmodcount,每次调用next和remove方法时会检查该值和list内部的modcount是否一致,不一致会报异常。问题中的第二种写法remove(e),会在每次调用时modcount++,虽然迭代器的remove方法也会调用list的这个remove(e)方法,但每次调用后还有一个exceptedmodcount=modcount操作,所以后续调用next时判断就不会报异常了。

    作者回复: 关键在用谁的remove方法。

    2019-05-30
    8
  • 建国
    老师,您好,linkList查找元素通过分前后半段,每次查找都要遍历半个list,怎么就知道元素是出于前半段还是后半段的呢?

    作者回复: 这个是随机的,因为分配的内存地址不是连续的。

    2019-06-10
    2
    3
  • JasonZ
    linkedlist使用iterator比普通for循环效率高,是由于遍历次数少,这是为什么?有什么文档可以参考么?

    作者回复: 因为for循环需要遍历链表,每循环一次就需要遍历一次指定节点前的数据,源码如下:

    // 获取双向链表中指定位置的节点
        private Entry<E> entry(int index) {
            if (index < 0 || index >= size)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
            Entry<E> e = header;
            // 获取index处的节点。
            // 若index < 双向链表长度的1/2,则从前先后查找;
            // 否则,从后向前查找。
            if (index < (size >> 1)) {
                for (int i = 0; i <= index; i++)
                    e = e.next;
            } else {
                for (int i = size; i > index; i--)
                    e = e.previous;
            }
            return e;
        }

    而iterator在第一次拿到一个数据后,之后的循环中会使用Iterator中的next()方法采用的是顺序访问。

    2019-06-09
    5
    3
  • 业余草
    请问:List<A> list = new ArrayList<>();
    for(int i=0;i++;i<1000){
     A a = new A();
     list.add(a);
    }

    和 这个 List<A> list = new ArrayList<>();
    A a;
    for(int i=0;i++;i<1000){
     a = new A();
     list.add(a);
    }
    效率上有差别吗?不说new ArrayList<>(); 初始化问题。单纯说创建对象这一块。谢谢!

    作者回复: 没啥区别的,可以实际操作试试

    2019-05-31
    3
  • 涛哥
    arrayList,for循环访问快是因为内存连续,可以整个缓存行读取进cpu缓存中,遍历下个的时候无需去内存中获取。并不是实现什么随机获取接口

    作者回复: 是的,是因为连续内存。在代码中,程序是不知道底层开辟的内存情况,所以需要一个类似序列化的接口标志,这个接口仅仅是一个标志,并不是实现。

    2019-07-17
    1
    2
  • Loubobooo
    这一道我会。如果有看过阿里java规约就知道,在集合中进行remove操作时,不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator方式,如果并发操作,需要对 Iterator 对象加锁。
    <!-- 规约第七条 -->

    作者回复: 👍

    2019-06-01
    2
  • ABC
    谢谢老师明白了,如果第二种写法换成for(;;)就会直接调用ArrayList的remove()方法就不会报错了。

    在第二种写法里面用foreach相当于是使用ArrayList内部的Itr类进行遍历,但删除数据又是用的ArrayList里面的remove()方法。从而导致状态不一致,引发报错。
    2019-05-31
    2
  • DebugDog
    写法一正确。
    虽然都是调用了remove方法,但是两个remove方法是不同的。
    写法二是有可能会报ConcurrentModificationException异常。
    所以在ArrayList遍历删除元素时使用iterator方式或者普通的for循环。

    作者回复: 对的,使用普通循环也需要注意。

    2019-05-30
    2
  • mickle
    第二种不行吧,会报并发修改异常的
    2019-05-30
    2
  • 老杨同志
    写法一正确,写法二会快速失败
    2019-05-30
    2
  • 张三丰
    first/last 方式可以在初始化 LinkedList 的时候节省 new 一个 Entry;

    来回看老师的专栏,这是第三遍了,每次都会有新的理解,同时也有新的疑问产生,比如上边的那句话今天一直没有想明白。。。。麻烦老师详细解答一下。
    2019-11-06
    1
  • L.
    老师,随机访问到底是什么意思?怎么个随机法?谢谢~

    作者回复: 这里指的是不需要通过遍历寻址,可以通过index直接访问到内存地址。

    2019-08-06
    1
  • TerryGoForIt
    老师您好,我比较好奇的是为什么 ArrayList 不像 HashMap 一样在扩容时需要一个负载因子呢?

    作者回复: HashMap有负载因子是既要考虑数组太短,因哈希冲突导致链表过长而导致查询性能下降,也考虑了数组过长,新增数据时性能下降。这个负载因子是综合了数组和链表两者的长度,不能太大也不能太小。而ArrayList不需要这种考虑。

    2019-05-31
    1
  • 晓杰
    写法2不正确,使用for循环遍历元素的过程中,如果删除元素,由于modCount != expectedModCount,会抛出ConcurrentModificationException异常

    作者回复: 对的!

    2019-05-30
    1
  • 每天晒白牙
    需要用迭代器方式删除
    for循环遍历删除会抛并发修改异常

    作者回复: 是的,不要使用迭代器循环时用ArrayList的remove方法,具体分析可以看留言区。

    2019-05-30
    1
  • 思忆
    这两种都不正确,因为增强for循环的底层使用的是迭代器,再删除过程中,指针发生变化,所以会异常
    2019-11-18
  • 赤城
    思考题是初级开发者在使用remove的时候普遍遇到的问题,第一个使用迭代器成功,第二个会报错!
    2019-11-07
  • 张三丰
    看了老师如下的回答不是很明白,为什么数组过长新增数据的性能就下降了呢?因为数组越长hash碰撞的几率越小,那么性能越高才对。

    老师您好,我比较好奇的是为什么 ArrayList 不像 HashMap 一样在扩容时需要一个负载因子呢?

    作者回复: HashMap有负载因子是既要考虑数组太短,因哈希冲突导致链表过长而导致查询性能下降,也考虑了数组过长,新增数据时性能下降。这个负载因子是综合了数组和链表两者的长度,不能太大也不能太小。而ArrayList不需要这种考虑。

    作者回复: 因为数组是连续性的存储结构,在新增数据时,如果不是想数组尾部顺序插入元素,则会涉及到其他数据的重新排列,性能就会差了。虽然查询性能很优秀,但在新增和删除数据时,性能就会变差了。

    第二个问题已经回答了。

    2019-10-21
收起评论
52
返回
顶部