随机访问和内存地址连续性

在对集合的访问中，一般会有两种访问方式：随机访问和顺序访问，不同的底层数据结构，在使用这两种访问方式时，效率是有区别的。一般来讲，内存地址连续的数据结构，在随机访问时的效率比内存地址不连续的要高。因为内存地址连续，可以通过下标很快的检索出对应的元素，反之由于内存地址不连续，在随机访问时，需要从内存地址起始位置按照链接关系一个一个的扫描，效率自然就降低了。典型的例子就是数组和链表。数组是一种内存地址连续的结构，对它的随机访问，效率比较高；链表是一种内存地址不连续的结构，对它的随机访问效率就比较低。

RandomAccess接口

在java语言中，为了方便开发者选择高效的访问方式，系统提供了一个RandomAccess接口，该接口用来标识对应的数据结构是否支持高效的随机访问。大多数以数组为底层结构的数据结构都实现了该接口。比如常见的ArrayList。在官方声明中，也对该接口进行了很详细的描述，原文如下：

 * Marker interface used by <tt>List</tt> implementations to indicate that
 * they support fast (generally constant time) random access.  The primary
 * purpose of this interface is to allow generic algorithms to alter their
 * behavior to provide good performance when applied to either random or
 * sequential access lists.
 *
 * <p>The best algorithms for manipulating random access lists (such as
 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * <tt>instanceof</tt> this interface before applying an algorithm that would
 * provide poor performance if it were applied to a sequential access list,
 * and to alter their behavior if necessary to guarantee acceptable
 * performance.
 *
 * <p>It is recognized that the distinction between random and sequential
 * access is often fuzzy.  For example, some <tt>List</tt> implementations
 * provide asymptotically linear access times if they get huge, but constant
 * access times in practice.  Such a <tt>List</tt> implementation
 * should generally implement this interface.  As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:

该声明对于RandomAccess接口进行很详细的描述，大致包括：

  1. 标识一个对象是否支持良好的随机访问策略
  2. 在满足1的前提下，随机访问策略比顺序访问的效率差不多高出一倍
  3. 如何判定一个集合或者数据结构是否满足这个接口的定义

在上述描述中的第三点，是如何确定一个对象是否应该去实现该接口，Java给出的依据是：

 * for typical instances of the class, this loop:
 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>

也就是说，通过下标检索效率要比通过迭代器的检索效率高。接下来，我们测试下。

效率测试

测试用例1

针对实现了RandomAccess的结构，ArrayList进行测试。我们通过填充100W个整型对象到ArrayList中，然后对该ArrayList集合进行遍历。测试代码如下：

public class RandomAccessTest {

    private final static int MAX = 10000000;

    private static ArrayList<Integer> LIST = new ArrayList<>(MAX);

    static {
        for (int i = 0; i < MAX; i++) {
            LIST.add(i);
        }
    }

    public static void main(String[] args) {
        loop();
        iterator();
    }

    public static void loop() {
        int size = LIST.size();
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            Integer integer = LIST.get(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("for loop cost " + (end - start));
    }

    public static void iterator() {
        long start = System.currentTimeMillis();
        Iterator<Integer> iterator = LIST.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
        }
        long end = System.currentTimeMillis();
        System.out.println("iterator loop cost " + (end - start));
    }
}

我们看下测试结果：

可以看到，通过下标的访问速度明显比迭代器要高，在数据量变得更加庞大的时候，这种优越性会体现得更加明显。

测试用例2

下面，我们看下没有实现RandomAccess的结构LinkedList，它是一种实现了双端队列的数据结构，还是按照测试用例1的方式，先填充10W个元素，然后进行遍历，测试代码如下：

public class SequentialAccessTest {

    private final static int MAX = 100000;

    private static LinkedList<Integer> LIST = new LinkedList<>();

    static {
        for (int i = 0; i < MAX; i++) {
            LIST.add(i);
        }
    }

    public static void main(String[] args) {
        loop();
        iterator();
    }

    public static void loop() {
        int size = LIST.size();
        long start = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            Integer integer = LIST.get(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("for loop cost " + (end - start));
    }

    public static void iterator() {
        long start = System.currentTimeMillis();
        Iterator<Integer> iterator = LIST.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
        }
        long end = System.currentTimeMillis();
        System.out.println("iterator loop cost " + (end - start));
    }
}

我们看下测试结果：

结果很惊人，可以看到，通过下标的访问速度极其缓慢，在数据量变得更加庞大的时候，编译器甚至会长时间无响应。反观迭代器，效率极其高。这个case在一定程度上，在提醒我们，选择合适的访问方式是何等的重要。

结论

任何一种数据结构都有其优点和缺点，在特定的场景下选择合适的数据结构，会让系统的运行效率得到意想不到的提升。当然，如何去选择，需要软件开发者对数据结构有一定的了解。了解常用的数据结构特性，了解他们的实现思路，了解他们的时间空间消耗。这不是一件简单的事情，却是一件有意义的事情。