Xiaobai learns Java: strange randomaccess

When analyzing the source code of the three collections, we said that ArrayList and vector inherit the randomaccess interface, but LinkedList does not. We also know that inheriting this interface means that the elements support fast random access.

What is randomaccess

Out of curiosity, I went to check the official documents of randomaccess, which surprised me! There is nothing in this interface! It's really strange! (in fact, clonable and java.io.serializable are similar to it, which will be discussed later) only a string of cold English is left.

Hey, no matter who he is, the translation will be finished. Today's life is also the life of a highly motivated Porter!

I organize it in my own language:

As we know, ArrayList and vector are implemented based on arrays at the bottom, occupying continuous storage space in memory. The subscript of each element is actually the offset of the first address, In this way, the sub query element only needs to be based on: element address = first address+ (element length * subscript) can quickly complete the query, which usually takes only a constant time, so they should implement the interface. However, the linked list is different. The linked list completes the connection according to the address references between different nodes. It does not require continuous addresses. It needs to traverse during the query, which will lead to the query when the amount of data is large Elements take a long time.

You can judge whether the list is an instance of the interface through xxlist instance of random access. If it is a sequential access list (such as LinkedList), you should not query the elements through subscript index, which will be very inefficient.

/*for循环遍历*/
for (int i=0,n=list.size(); i < n; i++)
    list.get(i);
/*Iterator遍历*/
for (Iterator i=list.iterator(); i.hasNext();)
    i.next();

For lists that implement the randomaccess interface and support fast random access, the for loop + subscript index traversal is faster than the iterator traversal.

The difference between forloop and iterator

In this regard, can we guess whether the iterator is faster if it is a LinkedList that does not support immediate quick access? So we made a wave of attempts:

    /*for循环遍历的测试*/
    public static void forTest(List list){
        long start = Sy@R_502_2354@.currentTimeMillis();
        for (int i = 0,n=list.size(); i < n; i++) {
            list.get(i);
        }
        long end = Sy@R_502_2354@.currentTimeMillis();
        long time = end - start;
        Sy@R_502_2354@.out.println(list.getClass()+" for循环遍历测试 cost:"+time);
    }
    /*Iterator遍历的测试*/
    public static void iteratorTest(List list){
        long start = Sy@R_502_2354@.currentTimeMillis();
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        long end = Sy@R_502_2354@.currentTimeMillis();
        long time = end-start;
        Sy@R_502_2354@.out.println(list.getClass()+"迭代器遍历测试 cost:"+time);
    }

    public static void main(String[] args) {    
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();
        /*ArrayList不得不加大数量观察它们的区别，其实差别不大*/
        for (int i = 0; i < 5000000; i++) {
            arrayList.add(i);
        }
        /*LinkedList 这个量级就可以体现比较明显的区别*/
        for(int i = 0;i<50000;i++){
            linkedList.add(i);
        }
        /*方法调用*/
        forTest(arrayList);
        iteratorTest(arrayList);
        forTest(linkedList);
        iteratorTest(linkedList);
    }

We can find that:

Determine whether it is randomaccess

As mentioned above, This empty interface is responsible for marking (marker) indicates whether random fast access is supported. If it is not supported, it is very inefficient to use the index to traverse. Since there are markers, we must have a way to distinguish between markers. At this time, we need to use the instanceof keyword to help us distinguish to select the correct access method.

public static void display(List<?> list){
    if(list instanceof RandomAccess){
        //如果支持快速随机访问
        forTest(list);
    }else {
        //不支持快速随机访问，就用迭代器
        iteratorTest(list);
    }
}

After another wave of tests, they both found their destination:

In fact, there are many methods for manipulating collections in the collection tool class collections. Let's take one method to fill the collection from front to back:

    public static <T> void fill(List<? super T> list,T obj) {
        int size = list.size();
            
        if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
            //for遍历
            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);
            }
        }
    }

There are many such methods, in which there are many places worth learning. I am a little white who is learning Java. Maybe my knowledge is not deep, but I will try to make a decent summary of what I have learned. By the way, if the article is misunderstood or unclear, please comment and correct it in the comment area.

Reference: jdk1 8 official documents