Java RandomAccess 接口有什么用？

你的名字 2022-12-17 07:23 151阅读 0赞

文档上是这样描述这个接口的

Marker interface used by List 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.

通俗点讲，RandomAccess 接口是一个标记性接口(它没有方法)，表明实现类支持快速随机访问。

RandomAccess 接口的目的就是使算法选择一个性能更好的行为，当这个算法应用到随机访问列表( 例如 ArrayList )或者顺序访问列表( 例如 LinkedList )时。

是不是不好理解，我们可以看到 `Collections.fill()` 方法

public static <T> void fill(List<? super T> list, T obj) { 
            int size = list.size();
    
            if (size < FILL_THRESHOLD || list instanceof RandomAccess) { 
                for (int i=0; i<size; i++)
                    list.set(i, obj);
            } else { 
                ListIterator<? super T> itr = list.listIterator();
                for (int i=0; i<size; i++) { 
                    itr.next();
                    itr.set(obj);
                }
            }
        }

从这个实现可以看出，如果列表实现来 RandomAccess 接口，那么使用 for 循环进行遍历，否则使用迭代器进行遍历。

下面通过一个例子来看看 ArrayList 和 LinkedList 遍历的速度

public class Hello { 
    
    	public static void main(String[] args) { 
    		List<Integer> list = new ArrayList<>();
    		init(list);
    		System.out.println("ArrayList traverse : " + traverse(list));
    		System.out.println("ArrayList traverse by iterator : " + traverseByIterator(list));
    		System.out.println("ArrayList traverse by foreach : " + traverseByForeach(list));
    		
    		list = new LinkedList<>();
    		init(list);
    		System.out.println("LinkedList traverse : " + traverse(list));
    		System.out.println("LinkedList traverse by iterator: " + traverseByIterator(list));
    		System.out.println("LinkedList traverse by foreach : " + traverseByForeach(list));
    	}
    	
    	public static void init(List<Integer> list) { 
    		for (int i = 0; i < 100000; i++) { 
    			list.add(i);
    		}
    	}
    	
    	public static long traverse(List<Integer> list) { 
    		long start = System.currentTimeMillis();
    		for (int i = 0; i < list.size(); i++) { 
    			list.get(i);
    		}
    		return System.currentTimeMillis() - start;
    	}
    	
    	public static long traverseByIterator(List<Integer> list) { 
    		long start = System.currentTimeMillis();
    		Iterator<Integer> iterator = list.iterator();
    		while (iterator.hasNext()) { 
    			iterator.next();
    		}
    		return System.currentTimeMillis() - start;
    	}
    	
    	public static long traverseByForeach(List<Integer> list) { 
    		long start = System.currentTimeMillis();
    		for (Integer i : list) { }
    		return System.currentTimeMillis() - start;
    	}
    
    }

执行结果为

ArrayList traverse : 13
    ArrayList traverse by iterator : 31
    ArrayList traverse by foreach : 34
    
    LinkedList traverse : 6422
    LinkedList traverse by iterator: 19
    LinkedList traverse by foreach : 7

从这个结果可以看出，ArrayList 的三种遍历方式的时间其实差不多，但是还是优先使用 for 循环进行遍历。

LinkedList 使用 for 循环遍历的时间，与使用迭代器( foreach 语法是通过迭代器实现的 )进行遍历的时间，相差巨大。因此，对于 LinkedList 绝对优先使用迭代器进行遍历，当然为来方便，可以使用 foreach 遍历。

LinkedList 使用 for 循环遍历，为何速度如此之慢？因为它是链表结构， `get()` 方法需要按顺序进行搜索

public E get(int index) { 
            checkElementIndex(index);
            return node(index).item;
        }
        
        Node<E> node(int 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;
            }
        }

对于指定的索引 index ，首先使用来一次二分法进行分组，然后再执行线性查找。因此当数据量特别大时，搜索的时间就长了。

ArrayList 通过 `get()` 方法搜索元素的时间明显快于 LinkedList，这是因为 ArrayList 是通过数组实现的，支持通过索引随机访问

public E get(int index) { 
            rangeCheck(index);
            return elementData(index);
        }
        
        E elementData(int index) { 
            return (E) elementData[index];
        }

程序的性能是要在小细节上，一点一点累积起来的，所以叫优化性能问题，而不是叫解决性能问题。