In learning Java set, the first to learn is the List of ArrayList and LinkedList, learning set is the key to learn its source code, understand the underlying implementation, so today talk about ArrayList implementation of an interface RandomAccess.

The creation of curiosity

When I looked at the source code for ArrayList, I found that it implemented RandomAccess. Out of curiosity, I found that the interface was empty, which of course raised the question: what is the use of this empty shelf?

Delve into

RandomAccess is the markup interface used by the List implementation to indicate that it supports fast (usually fixed-time) RandomAccess. The main purpose of this interface is to allow generic algorithms to change their behavior to provide good performance when applied to random or continuous access lists.

Marker Interface: This explains why RandomAccess is empty. This interface functions only as a Marker.

Isn’t this similar to Serializable interface? If you look closely, there are actually two other empty interfaces that ArrayList implements:

Cloneable interface: The Cloneable interface is implemented to indicate that the Object.clone() method can legally copy instances of this class by field. If does not implement the Cloneable interface Object instance call clone method, will lead to throw CloneNotSupportedException anomalies.

Serializable interface: The class implements the java.io.Serializable interface to enable its serialization capabilities. Classes that do not implement this interface will not be able to serialize or deserialize any of their state.

Continue to discuss

What is the purpose of labeling interfaces? Moving on to the role of RandomAccess, I won’t discuss the other two here.

If a List subclass implements RandomAccess, that means it can quickly and randomly access stored elements. You’re probably thinking of arrays, which are accessed by subscript index. The underlying implementation of ArrayList, which implements this interface, is arrays, also accessed by subscript. Except that we need to use the get() method, the underlying ArrayList is still an array access form.

At the same time, you should think of linked lists. The underlying implementation of LinkedList is linked lists, and LinkedList does not implement RandomAccess interface. Discovering this is the key to breaking through the problem.

Arrays support random access, fast query speed, slow to add and delete elements; Linked lists support sequential access, slow query speed, fast add and delete elements. So the corresponding ArrayList query speed is fast, LinkedList query speed is slow, RandomAccess this tag interface is the tag can randomly access the set of elements, simply put, the bottom is the array implementation of the set.

In order to improve the performance, we can use Instanceof to make judgment before traversing the collection to select the appropriate traversal method. When there is a large amount of data, the performance can be greatly improved.

Random access lists are iterated over, and sequential access lists are iterated over.

Take a look at RandomAccess in action

import java.util.*;
public class RandomAccessTest {
    public static void traverse(List list){

        if (list instanceof RandomAccess){
            System.out.println("RandomAccess interface implemented without iterators");

            for (int i = 0; i < list.size(); i++){ System.out.println(list.get(i)); }}else{
            System.out.println("Didn't implement RandomAccess interface, used iterator");

            Iterator it = list.iterator();
            while(it.hasNext()){ System.out.println(it.next()); }}}public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        arrayList.add("a");
        arrayList.add("b");
        traverse(arrayList);

        List<String> linkedList = new LinkedList<>();
        linkedList.add("c");
        linkedList.add("d"); traverse(linkedList); }}Copy the code

Let’s add a lot of data for performance testing:

import java.util.*;
public class RandomAccessTimeTest {

    // Use the for loop to loop through
    public static long traverseByLoop(List list){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++){ list.get(i); }long endTime = System.currentTimeMillis();
        return endTime-startTime;
    }

    // use iterators to traverse
    public static long traverseByIterator(List list){
        Iterator iterator = list.iterator();
        long startTime = System.currentTimeMillis();
        while (iterator.hasNext()){
            iterator.next();
        }
        long endTime = System.currentTimeMillis();
        return endTime-startTime;
    }

    public static void main(String[] args) {
        // Add data
        List<String> arrayList = new ArrayList<>();
        for (int i = 0; i <30000; i++){ arrayList.add("" + i);
        }
        long loopTime = RandomAccessTimeTest.traverseByLoop(arrayList);
        long iteratorTime = RandomAccessTimeTest.traverseByIterator(arrayList);
        System.out.println("ArrayList:");
        System.out.println("For loop duration :" + loopTime);
        System.out.println("Between iterations of iterators :" + iteratorTime);

        List<String> linkedList = new LinkedList<>();
        // Add data
        for (int i = 0; i <30000; i++){ linkedList.add("" + i);
        }
        loopTime = RandomAccessTimeTest.traverseByLoop(linkedList);
        iteratorTime = RandomAccessTimeTest.traverseByIterator(linkedList);
        System.out.println("LinkedList:");
        System.out.println("For loop duration :" + loopTime);
        System.out.println("Between iterations of iterators :"+ iteratorTime); }}Copy the code

Results:

ArrayList: for loop duration: 3 Iterator duration: 7

LinkedList: for loop duration: 2435 iterator duration: 3

conclusion

Based on the results, we can conclude that ArrayList iterator traversal is better than LinkedList iterator traversal

According to the above conclusions, RandomAccess can be used to judge before traversal, and different traversal methods can be selected according to the different subclasses of List to improve the performance of the algorithm.

Learn to read the source code, discover the subtlety of the underlying implementation, change your thinking, and improve the performance of your code in every small detail.