OpenJDK源码研究笔记(三)-RandomAccess等标记接口的作用

标识接口是没有任何方法和属性的接口。

它仅仅表明它的类属于一个特定的类型,供其他代码来测试允许做一些事情。

下面来看一个标记接口RandomAccess。

public interface RandomAccess
List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。
此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

将操作随机访问列表的最佳算法(如 ArrayList)应用到连续访问列表(如 LinkedList)时,可产生二次项的行为。
如果将某个算法应用到连续访问列表,那么在应用可能提供较差性能的算法前,鼓励使用一般的列表算法检查给定列表是否为此接口的一个 instanceof,如果需要保证可接受的性能,还可以更改其行为。

现在已经认识到,随机和连续访问之间的区别通常是模糊的。
例如,如果列表很大时,某些 List 实现提供渐进的线性访问时间,但实际上是固定的访问时间。
这样的 List 实现通常应该实现此接口。
实际经验证明,如果是下列情况,则 List 实现应该实现此接口,即对于典型的类实例而言,此循环:
     for (int i=0, n=list.size(); i < n; i++)
         list.get(i);
 的运行速度要快于以下循环:
     for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();
        
OpenJDK源码 java.util.Collections
public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i = size; i > 1; i--)
                swap(list, i - 1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i = size; i > 1; i--)
                swap(arr, i - 1, rnd.nextInt(i));

            // Dump array back into list
            ListIterator it = list.listIterator();
            for (int i = 0; i < arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }

如果List集合实现了RandomAccess标记接口,表明该List可以随机访问。这样访问List中的第i个元素(任意一个)时间是一个常量。

如果没有实现,访问第i个元素list.get(i)的会花费更多的时间。

为了节省时间,先将list转换为“数组”,再对“数组”进行 随机访问,最后将“数组”转换为list。

JDK中文API文档对标记接口RandomAccess的说明和OpenJDK源码中的这个例子是值得我们去学习的。

参考资料: OpenJDK源码,JDK中文API文档

相关阅读http://www.voidcn.com/cata/493

原文参见http://FansUnion.cn/articles/2828

相关文章