Interface inheritance diagram and related method analysis

What is the entire interface inheritance diagram of ArrayList?

  • So when we look at interfaces, we don’t have to go over the very simple ones, but there are some little details that we’ll mark up in the methods.
  • In addition, the parent class interface and lambda methods are omitted.

可迭代

This encapsulates the iterator’s generic methods

Public interface Iterable<T> {// Return an Iterator<T> Iterator (); // Other lambda methods are omitted here}Copy the code

Collection

This encapsulates some methods that are common to collections

Public interface Collection<E> extends Iterable<E> {//---- query operation ---- // Return length int size(); // The collection is returned emptytrueboolean isEmpty(); // The collection contains the specified element returnedtrueboolean contains(Object o); /** * returns an array containing all the elements of the collection. This method is used for array and collection conversions. Note: * - Deep copies a new array, not sharing a reference with the previous one. * - Ensure that the order is the same as before. */ Object[] toArray(); /** * returns an array containing all the elements of the collection. Note: * - If array A is greater than the length of the collection, the excess portion is filled with NULL */ <T> T[] toArray(T[] a); //---- modify operation ---- /** * add an element, note: * - This method may have a null pointer, and is easier to step on the hole method, specific implementation class if not allowed to add empty elements. */ boolean add(E e); boolean remove(Object o); //---- block operation ---- // returns when containing all elements of c settrueAnd vicefalse. boolean containsAll(Collection<? > c); Boolean addAll(Collection<? extends E> c); // Remove elements from c set. Boolean removeAll(Collection<? > c); // Intersections are operated to preserve elements that exist in both sets. Boolean retainAll(Collection<? > c); Void clear(); //---- compare and hash ---- // determine whether two sets are equal. / / gethashCode
    int hashCode();
}
Copy the code

T[] toArray(T[] a); For this method, let’s do a little test:

The code is as follows:

Test results:

List

This encapsulates some operations that are common to lists

Public interface List<E> extends Collection<E> {public interface List<E> extends Collection<E> {public interface List<E> extends Collection<E> { extends E> c); // get the element at the specified position E get(int index); // Replace the element at the specified position. Eset(int index, E element); // Add the element at the specified location. void add(int index, E element); // Remove the element at the specified position. E remove(int index); // Get the index of the element's first found position without returning -1. int indexOf(Object o); // Gets the index of the element's last found position, without returning -1. int lastIndexOf(Object o); // Return the list iterator ListIterator<E> ListIterator (); ListIterator<E> ListIterator (int index); ListIterator<E> ListIterator (int index); List<E> subList(int fromIndex, int toIndex); }Copy the code

Cloneable

This is a flag interface that you implement to indicate whether or not you support deep copying. Deep replication and shallow replication are not described here, interested students can search related materials. We can get an instance of a deep copy by calling its Clone method.

public interface Cloneable {
}
Copy the code

RandomAccess

This is also a tag interface, implemented to indicate whether you support fast random access to elements in a List.

public interface RandomAccess {
}
Copy the code

AbstractCollection

It mainly implements some common methods in the Collection interface.

There’s an implicit convention here, and AbstractXXX represents some generic logic implementation of XXX in our own design, without having to hand it over to a bunch of subclasses.

Here is a small detail, the maximum array length: MAX_ARRAY_SIZE = integer.max_value – 8; The reason for the -8 is that some virtual machine implementations reserve header information in arrays.

AbstractList

This is mainly the List interface inside some general methods to achieve.

Observing AbstractList in Ideal adds a fieidmodCount, which represents the number of “structural changes”. But when you use an iterator (inerator or listIterator), the iterator will store the modCount, and when you go through each element it will check that the modCount in the iterator is consistent with the modCount in the List, and if it is inconsistent, Just throw ConcurrentModificationException. That’s fast-fail’s strategy.

ArrayList source code analysis

Now that we know about interfaces, let’s get started with the code for ArrayList.

ArrayList data structure:

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * Default initialization size. */ private static final int DEFAULT_CAPACITY = 10; /** * an empty array instance, which is returned whenever an empty array instance needs to be returned. * Writing code encourages reusable instances to be declared in advance and then shared. Reduce the number of useless new's. * This example is used by both the constructor and trimSize. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * is also an empty array for empty instances of the default size. * However, it is not used for the same purpose as EMPTY_ELEMENTDATA, which is used to determine when the first element was added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * Where to store specific elements. */ transient Object[] elementData; // Non-private to simplify nested class access /** * Simplify nested class access /** * Simplify nested class access /** * */ private int size;Copy the code

ArrayList is a typical linear table structure. Here we briefly review the complexity of linear table structures and common operations.

Initialization method analysis

The jdk1.8 constructor no longer defaults to a 10-length example, but instead builds an empty one. So when will it be expanded? The answer is public every time you addArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; Public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;return true; } private static int calculateCapacity(Object[] elementData, int minCapacity) { The role of DEFAULTCAPACITY_EMPTY_ELEMENTDATA comes into play, determining when to add for the first time.if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        returnminCapacity; } // Specify the size of the construct we do not need to say. public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

Analysis of capacity expansion Method

EnsureCapacityInternal (size + 1); // Add (addAll); // When there is not enough capacity that might cause an overflow, the grow method is called to expand the capacity. private void ensureExplicitCapacity(int minCapacity) { modCount++;if(minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) {int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); // Determine the boundary of the new capacityif (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array. copyOf(elementData, newCapacity); }Copy the code

Boundary method analysis

Most of the ArrayList read-write methods call boundary detection logic, which is relatively simple to implement.

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code

So much for the source code analysis of ArrayList, which focuses on the most frequently asked questions in interviews.

Let’s do some problems with ArrayList

Is arrayList concurrency safe?

Obviously not, for example, key variables in the data structure are not even guaranteed visibility, such as size, etc. Not to mention concurrency security.

What is the arrayList expansion strategy?

In the implementation of 1.8, the add class method will perform a capacity test each time, and expand the capacity by 1.5 times each time, and perform boundary detection at the same time.