★ FEATURED ARTICLE 面试现场。面试官ArrayList 和 LinkedList 的区别候选人AArrayList 底层是数组查询快LinkedList 底层是链表增删快。面试官那这两句里的快和慢各自对应什么复杂度LinkedList 头插是快那 get(1000) 呢候选人A……也是快吧链表嘛。面试官还有你遍历一个 ArrayList 的时候如果顺手 remove 了一个元素会发生什么候选人A应该没问题吧面试官摇摇头问候选人B。候选人B会抛ConcurrentModificationException。ArrayList 里有个 modCount每次结构性修改都自增迭代器创建时记下当时的 modCount 当基准每次 next 前对一下不一致就抛。这不是并发问题是你一边迭代一边改了结构迭代器直接不干了。面试官那要怎么正确地删候选人B用迭代器自己的remove()它会同步基准值。一、ArrayList 和 LinkedList差在底层结构ArrayList 底下是一个数组以下源码来自 JDK 8 java.util.ArrayListtransient Object[] elementData; // 真正存元素的数组 private int size; // 实际元素个数注意不等于数组长度 private static final int DEFAULT_CAPACITY 10;size是元素个数elementData.length是数组容量两者不是一回事。get(i)直接取elementData[i]随机访问是 O(1)。但往中间插一个、删一个得用System.arraycopy把后面的元素整体挪一格是 O(n)。LinkedList 底下是双向链表以下源码来自 JDK 8 java.util.LinkedListtransient int size 0; transient NodeE first; transient NodeE last; private static class NodeE { E item; NodeE next; NodeE prev; }每个节点记住前后邻居。头插尾插是 O(1)但按下标取元素得从头或从尾一步步走过去是 O(n)。有个小优化node(index)会判断下标靠前还是靠后靠前从头走、靠后从尾走相当于把距离砍掉一半但复杂度还是 O(n)。所以LinkedList 增删快是有前提的——你得已经拿到那个节点比如用迭代器遍历时删当前节点否则光是定位就 O(n)反而不如 ArrayList。真正在工程里ArrayList 用得多得多内存连续、缓存友好随机访问快中间增删的场景本来就不多。反过来说LinkedList 的每个节点除了存数据还要额外存 next、prev 两个引用和一个对象头同样多的元素它占的内存明显比 ArrayList 大节点在堆上又是散着放的CPU 缓存命中率低从头到尾遍历起来通常也没数组快。顺带把 Vector 也说了。它和 ArrayList 一样是数组实现但方法都加了synchronized所以是线程安全的代价是每次都加锁、并发性能差。它的扩容策略是翻倍没指定capacityIncrement时ArrayList 是 1.5 倍。和它同族的还有个Stack继承自 Vector也是老式同步的产物现在要在栈或队列场景下用它换成ArrayDeque更合适。Vector 这一脉基本可以不用了。ArrayList 从默认容量到逐次扩容的过程看图关于扩容还有个常被误答的点DEFAULT_CAPACITY是 10但new ArrayList()之后并没有马上分配一个长度 10 的数组底层是一个共享的空数组常量。真正的 10 是在第一次add时才分配的属于懒加载。扩容发生在容量不够时grow里算old (old 1)也就是约 1.5 倍再用Arrays.copyOf整段复制过去。所以如果你提前知道大概要放多少元素构造时就把容量传进去能省掉几次扩容复制。怎么选给个一句话版默认用 ArrayList需要频繁在头部插入、或者把它当队列、当栈用优先考虑ArrayDeque它比 LinkedList 更省内存操作也更快确实要按已定位的节点增删才轮到 LinkedList多线程读多写少用 CopyOnWriteArrayList。日常里绝大多数场景ArrayList 就是那个正确答案。二、fail-fastmodCount 在数什么现在进正题。为什么遍历时删元素会炸ArrayList 里有个字段叫modCount记录结构被修改过多少次protected transient int modCount 0; public boolean add(E e) { ensureCapacityInternal(size 1); elementData[size] e; modCount; // 结构变了计数 1 return true; }add、remove 这类会改变结构的操作都会让modCount自增。迭代器创建的时候会把当时的modCount记下来作为自己的基准值expectedModCount之后每次next()之前都对一下这两个值final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); }你用 for-each底层就是迭代器遍历时集合自己remove会改modCount而迭代器的基准值没动。下次next()一比对数值对不上直接抛ConcurrentModificationException。这就是 fail-fast——发现不对立刻失败不让你用一份已经不一致的数据。机制看图正确的删法是让迭代器自己删IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); if (s.equals(target)) { it.remove(); // 迭代器的 remove 会同步 expectedModCount } }Iterator.remove()在删完之后会把expectedModCount更新成最新的modCount两边重新对齐就不会再抛。JDK 8 起Collection还提供了removeIf一行就能安全地做条件删除list.removeIf(s - s.equals(target));它内部也是通过迭代器来删的比手写循环清爽。有一点必须说清楚fail-fast 是尽力检测不是并发安全的承诺。Javadoc 里的原话大意是这种快速失败机制是在尽力而为的基础上实现的不能拿它来保证正确性。换句话说多线程下真正同时改它不一定检测得到它主要拦的是单线程里边遍历边改这种逻辑错误。拿它当线程安全手段是要出事的。再顺带辟个谣这个异常叫ConcurrentModificationException但它跟多线程并发没有必然关系。单线程里用 for-each 遍历、同时又调用list.remove()一样会触发它——因为它检测的是迭代器记下的基准值和当前 modCount 对不上跟有几个线程无关。三、fail-safeCopyOnWriteArrayList 为什么绕得开既然 fail-fast 在并发下不可靠那多线程想安全地边读边写怎么办CopyOnWriteArrayList走的是另一条路写时复制。它的写操作是这样的以下源码来自 JDK 8 java.util.concurrent.CopyOnWriteArrayListpublic boolean add(E e) { final ReentrantLock lock this.lock; lock.lock(); try { Object[] elements getArray(); int len elements.length; Object[] newElements Arrays.copyOf(elements, len 1); // 复制出新数组 newElements[len] e; // 写在新数组上 setArray(newElements); // 原子地换掉引用 return true; } finally { lock.unlock(); } }要点写的时候先加锁把整个底层数组复制一份改副本再把内部的数组引用换成副本。读的时候不加锁读的是当前那一刻的数组。迭代器拿到的也是一个快照所以遍历过程中即使有别的线程在写迭代器看到的还是老数组不会抛异常——这叫 fail-safe或者叫弱一致。它能保证不炸但不保证你读到的一定是最新的数据。代价也很实在每次写都要复制整个数组内存开销大、写性能低。所以它适合读多写少的场景比如监听器列表、配置列表这种读得频繁、几乎不改的地方。读多写少拿它写多读少就得另想办法了。顺便说一句Vector虽然每个方法都加锁但它的迭代器同样是 fail-fast 的——锁只保护了单次方法调用不保护你遍历 修改这整段跨多次调用的操作。所以想靠 Vector 解决遍历中删除的问题是行不通的。 面试官真正想听的答案问 ArrayList 和 LinkedList 的区别他真正想听的是你对 fail-fast 的理解以及遇到遍历中删除你会怎么办。第一层给结论ArrayList 是数组随机访问 O(1)、中间增删 O(n)LinkedList 是双向链表定位节点 O(n)、拿到节点后增删 O(1)。但更值得说的是遍历安全——ArrayList 的迭代器有 modCount 校验遍历中直接改结构会抛 ConcurrentModificationException。第二层讲机制modCount每次结构性修改自增迭代器创建时快照出expectedModCountnext()前对比不一致就抛。正确的做法是用Iterator.remove()会同步基准值或 JDK 8 的removeIf。要说清 fail-fast 只是尽力检测不是并发安全保证。第三层给选型判断单线程读多写少用 ArrayList中间频繁插入删除、且能通过迭代器定位的才考虑 LinkedList多线程读多写少用 CopyOnWriteArrayList写时复制、读不加锁、弱一致Vector 的老式同步已基本被淘汰。下篇预告下一篇聊泛型擦除。为什么new T[10]编译不过为什么ListString和ListInteger在运行时其实是同一个类还有那个藏在字节码里的桥接方法以及面试爱考的 PECS 原则——什么时候用? extends、什么时候用? super。这一题能把你对 Java 类型系统的理解问到底。唠点键盘之外的 · 第 30 篇
阅读完成 · 觉得有帮助？
