Prologue

最近遇到一道笔试题(版权问题，有所改动)：

What performance optimizations could be made in this method:

public List<String> getNames(List<User> users){
    List<String> names = new List();
    int size = users.size();
    for(int i = 0; i < size; i++){
        names.add(users.get(i).getName());
    }
    return names;
}

User作为一个POJO，并拥有属性name以及对应的setter、getter。

Optimization 1

这段代码有个错误的地方，List是一个interface，不能直接new（这也是后来我在电脑上测试的时候才发现）。
在这个地方我们需要用具体实现的ArrayList或者LinkedList代替。

对于ArrayList和LinkedList的区别，顾名思义其实就是数组和链表的区别：

数组在内存中分配的是一块连续的地址，通过首地址和偏移量就可以找到对应索引的元素（严格说是首地址+偏移量*单个元素所占的内存大小）。
链表则是通过指针将下一个节点的地址保存在当前节点（Java没有指针这么一说，可以理解为内存地址引用），多个节点的内存分配没有连续性要求。

从数组和链表的内存分配及实现方式上来看，可以得出结论：

对于元素的读写操作，数组相对更快。数组内的任意一个元素都可以同样地通过首地址加偏移量来快速获取；而链表则需要从表头开始遍历。
对于元素的增删，链表相对更快。

增加元素，链表将该元素所在的节点指向下一个节点，再把上一个节点指向该元素节点即可；而数组为了保持内存的连续性，则需要将该元素所在内存之后的所有元素依次向后挪一个元素大小的位置，从而腾出一个元素的内存空间。

删除元素，链表将该元素的上一节点指向该元素的下一节点即可（对于C语言需要手动free删除的元素节点；而Java在下一次GC的时候，删除的元素节点会因为没有被引用而自动回收）。同样，数组为了保持内存的连续性，需要将该元素所在内存之后的所有元素依次向前挪一个元素大小的位置。

什么时候用ArrayList，什么时候用LinkedList，一般来说需要根据具体业务逻辑情况而视。对于上面的代码来说，可以预料到names更多的是用于后续的展示，如果业务涉及增删的情况更为妥当的做法应该是去操作原生的users，所以这里使用ArrayList显然更合适。

Optimization 1:

public List<String> getNames(List<User> users){
    List<String> names = new ArrayList();
    int size = users.size();
    for(int i = 0; i < size; i++){
        names.add(users.get(i).getName());
    }
    return names;
}

Optimization 2

ArrayList初始化容量：
对于没有设置容量参数的ArrayList，初始化的时候会有个默认的容量10，然后在每次执行add()方法的时候都会去判断当前容量是否足够，不够的时候就会增添容量（一般是每次增添当前容量的一半，具体的实现可以参考源码，增添方法判断情况比较多）。
而且对于增添容量，实际在内存中执行更为复杂，首先会新分配一块增添容量后的连续内存，再将原来容量大小的那块内存数据依次拷贝过来，拷贝完之后GC回收掉原来的内存。
而设置了初始化容量，只要保证容量足够，在add的时候便不会再去执行增添容量，也不会出现整块内存数据拷贝。

Optimization 2:

public List<String> getNames(List<User> users){
    int size = users.size();
    List<String> names = new ArrayList(size);
    for(int i = 0; i < size; i++){
        names.add(users.get(i).getName());
    }
    return names;
}

多说一句，LinkedList的内存分配方式就决定了没有初始化容量这么一说（也没有这样的构造方法）。事实上查看对应的add方法源码就能发现，如果是空表则增添的节点作为表头，如果不为空则直接将尾节点指向新节点，当然内部还是存在着size计数。

Optmization 3

接下来就要进入到今天的主题forEach。
让我们暂时抛开上面的优化问题，先来讨论一下for循环的几种写法（码农都是孔乙己，嗯嗯）：

List<String> list = new ArrayList<>(); // or new LinkedList<>()

//普通写法
for(int i = 0; i < list.size(); i++){
    System.out.println(list.get(i));
}

//一般迭代器的写法
for(Iterator iterator = list.iterator(); iterator.hasNext();){
    String str = (String) iterator.next();
    System.out.println(str);
}

//forEach隐藏迭代器的写法
for(String str : list) {
    System.out.println(str);
}

一般for循环大致就以上三种写法，而对于效率我们还要考虑给定的list分ArrayList和LinkedList两种情况，所以总共有六种情况，下面我们就从ArrayList和LinkedList的源码去分析对于给定的list什么样的for循环效率更高。

普通for循环

ArrayList.class源码的get()方法：
```
public E get(int index){
    if(index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    return (E) elementData[index];
}
```
从源码得知elementData依然是个数组：transient Object[] elementData，这也证实了之前所说的ArrayList是通过数组首地址加索引偏移量来取数据。

LinkedList.class源码的get()方法：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

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;
    }
}

同样，从源码可以证实LinkedList是通过遍历链表来获取元素，只不过这里使用的是双向链表，做了一个查找的小优化（对于索引不足size一半时从表头向后遍历，否则就从表尾向前遍历）。

一般迭代器

ArrayList.class源码(通过iterator()方法获取对应Iterator，再通过Iterator的next()方法获取元素)：

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    ···               // 方便描述，省略一些不怎么相关的代码

    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such

    @SuppressWarnings("unchecked")
    public E next() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        if (i >= limit)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
}

可以看到，在ArrayList的Iterator中，通过游标cursor来记录下一个元素的索引，执行next()方法的时候便给cursor+1，同时在数组elementData里查找当前索引的元素并返回。这里的重点在于elementData是ArrayList的同一个数组，查找依然是通过数组首地址+索引偏移量的方式，非常快速有效。
lastRet记录上一个元素的索引，该属性主要用于Iterator后面的remove()方法。

LinkedList.class本身没有iterator()方法，该方法存在于LinkedList的父类AbstractSequentialList.class中：

public Iterator<E> iterator() {
    return listIterator();
}

而listIterator()方法又存在于AbstractSequentialList的父类AbstractList.class中：

public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}

看起来最终调用的像是AbstractList带参数的listIterator(index)方法，但是LinkedList重写了AbstractList的该方法，所以实际调用的是LinkedList中的listIterator(index)方法获取对应的Iterator：

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

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

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    ···   // 同样，方便描述省略部分代码
}

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

从LinkedList内部类ListItr的next()方法可以得知，内部保存着当前循环的节点，每次执行next()方法获取下一个元素的时候，把当前节点指向下一个节点，同时返回当前节点的item数据。这种方式和ArrayList的Iterator比较类似，只不过ArrayList记录的是一个索引整数cursor，通过cursor自加实现循环；而LinkedList记录的是一个Node类型的class数据（其实就是C语言的结构体），Node.class里分别定义一个next和prev的Node属性，各自指向下一个节点和上一个节点（达到双向链表），从而实现循环。
LinkedList的Iterator存储临时节点，避免了普通for循环的get()方法每次都需要从表头遍历的低效率重复性动作。

forEach隐藏迭代器
forEach是增强for循环，java5的新特性。
foreach之所以能工作，是因为Collection集合类都实现了Iterable接口，该接口中定义了Iterator迭代器的产生方法iterator()。

Collection源码：

  public interface Collection<E> extends Iterable<E> {
      ···
  }

Iterable源码：

  public interface Iterable<T> {
      Iterator<T> iterator();

      default void forEach(Consumer<? super T> action) {
          Objects.requireNonNull(action);
          for (T t : this) {
              action.accept(t);
          }
      }

      default Spliterator<T> spliterator() {
          return Spliterators.spliteratorUnknownSize(iterator(), 0);
      }
  }

对于ArrayList，重新实现Iterable接口的iterator()方法就是前面在一般迭代器里提及的iterator()方法。
同样，对于LinkedList，也与前面一般迭代器里的描述一致，调用的是父类AbstractSequentialList实现的iterator()方法。
forEach与一般迭代器写法的不同之处在于其隐藏迭代器，并且隐藏的迭代器是通过Iterable接口实现的方式产生，至于Iterator生成及后续则完全一致。但是forEach的写法避免混乱和出错的可能，也更简洁。

讲完了“茴”字的四种写法，让我们再回到前面的笔试题优化。对于该方法我们不能确定传入的参数users是ArrayList还是LinkedList，从代码来看users只涉及到读取操作，显然传入的如果是ArrayList效率会更高，但是在这里我们肯定不能强行要求调用方必须传入一个ArrayList。

这时候我们需要将普通for循环优化为forEach：

  Optimization 3:

  public List<String> getNames(List<User> users){
      int size = users.size();
      List<String> names = new ArrayList(size);
      for(User user : users){
          names.add(user.getName());
      }
      return names;
  }

这样当users的size比较大的时候可以大幅提高传入LinkedList时的运行效率。

Epilogue

最后，不少人测试会发现对于传入ArrayList来说，普通for循环会比forEach快，所以还有这种优化方法：

  Optimization 4:

  public List<String> getNames(List<User> users){
      int size = users.size();
      List<String> names = new ArrayList(size);
      if（users instanceof LinkedList）{
          for(User user : users){
              names.add(user.getName());
          }
      }else if(users instanceof ArrayList){
          for(int i = 0; i < size; i++){
              names.add(users.get(i).getName());
          }
      }
      return names;
  }

从上面对于ArrayList的源码分析我们知道ArrayList的普通for循环和forEach都是调用的数组查找，那为什么普通for循环会快呢？原因是forEach对于Iterator的一系列额外操作所致（一般迭代器也是同理）。但是减少的这部分操作对效率的提升非常有限，实际代码测试也可以发现只快一丢丢，换来的却是代码不统一可读性降低，不推荐这么做。

目录

Prologue

Optimization 1

Optimization 2

Optmization 3

Epilogue