This is the fifth day of my participation in the More text Challenge. For details, see more text Challenge

An overview of the

ArrayList is one of the most commonly used container classes

First, ArrayList is based on arrays at the bottom, and data is stored contiguously in memory, making it extremely efficient to find data

In addition, the source code analysis is based on JDK11 (“11.0.10”), depending on the JDK version you use. Keep in mind that the implementation of Java classes varies from JDk version to JDk version

Here, you’ll see the basic use of ArrayList, container initialization, container expansion, and its implementation of iterators

If there are any mistakes or omissions, please kindly correct them

The basic use

For the basic use of ArrayList, the common methods are as follows

void add(int index, E element: Inserts the element at the specified position
boolean add(E e): Inserts the element at the end of the list
boolean addAll(int index, Collection<? extends E> c): Inserts the container at the specified location
boolean addAll(Collection<? extends E> c): Inserts the container, at the end of the list
void clear(): Clears the current container
boolean contains(Object o): Whether the specified element exists
void forEach (Consumer<? super E> action): Traversal of data elements
E get(int index): Retrieves the element at the specified position
int indexOf(Object o): returns the index of the first occurrence of an element
boolean isEmpty(): Whether the current container is empty
iterator<E> iterator(): Returns an iterator object for a list instance
int lastIndexOf(Object o): returns the index of the last occurrence of an element
ListIterator<E> listIterator(): Returns a list iterator
ListIterator<E> listIterator(int index): Returns an iterator for part of the current list
E remove(int index): Deletes the element with the specified index
boolean remove(Object o): Deletes the specified element

// The generic type of the right instance object may not be specified
List<String> list = new ArrayList<>();

// Add the element
list.add("A");
list.add("B");
list.add("C");

// Get the element
System.out.println(list.get(0));

// Delete the element
System.out.println(list.remove(0));

// Replace the element
list.set(0."D");

// Empty the container
list.clear();

// Check whether the container is empty
System.out.println(list.isEmpty());

// Check whether the container contains the specified element
list.add("E");
System.out.println(list.contains("C"));

// Find the location of the element
System.out.println(list.indexOf("E"));

// Turn the singleton collection into an array
Object[] objects = list.toArray();
Copy the code

Above, is about the partial use of ArrayList, the following, will introduce the internal implementation details of ArrayList

Initialize the

Initialization with no parameter

The first is the empty expansion of ArrayList. That is, the expansion is performed through the constructor with no parameters. The expansion length is not specified, and the elements are not added

public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

DEFAULTCAPACITY_EMPTY_ELEMENTDATA: Static immutable array of type Object. The array is empty

ElementData: An empty array of type Object, responsible for recording the array length of the ArrayList

As you can see, the array capacity of the ArrayList is 0 when expanding to empty, and there is a problem here

Constructs an empty list with an initial capacity of ten: Constructs an empty list with an initial capacity of ten

The default size of an ArrayList is 10. The default size of an ArrayList is 10

There are parameters for initialization

The following is an ArrayList initialization with a parameter, passing an int parameter, specifying the size of the initialization

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

There are three simple ways to specify an initialization capacity

initialCapacityAs a formal parameter, representing the length of the array specified at instantiation time
EMPTY_ELEMENTDATA: static immutableObjectAn empty array
ifinitialCapacityIs greater than0, the corresponding length is createdObjectArray, assigned to elementData
ifinitialCapacityIs equal to the0, a new value is assignedObjectAn empty arrayEMPTY_ELEMENTDATATo elementData
ifinitialCapacityLess than0, an exception is thrownIllegalArgumentExceptionParameter receiving error

capacity

Scaling is an important part and is at the heart of ArrayList source analysis. For ArrayList expansion, start by adding elements

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
Copy the code

Here, you first call the method that the element added, passing in a data element

ModCount: an integer of type int. The default value is 0. It is responsible for recording the number of modification operations in the ArrayList

This is very important to effectively detect problems with concurrent modification operations. Of course, only discovery, not avoidance

Next, add(e, elementData, size) is called, passing three arguments. E is the data element to be added; ElementData is the capacity of the current container; Size is understood as the used capacity of the container, that is, the number of existing elements

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
Copy the code

In the above method, it is determined whether the capacity that is actually being used is the maximum (excluding the data elements that are currently being added)

If the capacity limit is not reached, data elements are added to the end of the array (the index starts at 0) and size is increased by 1

If the capacity limit has been reached, grow() is called to expand the ArrayList container. The following is the actual operation of container expansion

private Object[] grow() {
    // Make sure you can add an element after expansion
    return grow(size + 1);
}
Copy the code

private Object[] grow(int minCapacity) {
    // Copy the expanded array and assign it to elementData
    return elementData = Arrays.copyOf(elementData,
                                        newCapacity(minCapacity));
}
Copy the code

private int newCapacity(int minCapacity) {
    // Create oldCapacity, which is the current array capacity
    int oldCapacity = elementData.length;
    // Create newCapacity, 1.5 times the current array capacity, using bit operation
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // Check whether the current capacity is larger than the old capacity. If the value is smaller than or equal to, run the branch
    if (newCapacity - minCapacity <= 0) {
        // Check whether the current capacity of the container is empty
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // Expand the current array to 10, DEFAULT_CAPACITY = 10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        // Very important! There is a limit value for container expansion, which will be negative when exceeded
        if (minCapacity < 0)
            // Heap memory overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity// Call hugeCapacity(minCapacity) if you are approaching the capacity limit
        : hugeCapacity(minCapacity);
}
Copy the code

private static int hugeCapacity(int minCapacity) {
    // Check whether the capacity expansion limit is exceeded
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    MAX_VALUE specifies the maximum value of the capacity to be expanded
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}
Copy the code

The above code, which describes the ArrayList container expansion process, can be summarized into three points

When all capacity is used, a new array is created, 1.5 times the size of the original array
Determine whether the capacity expansion is close to the container capacity limit
If the capacity expansion limit is not reached, copy the new array to the old array and expand the capacity by 1.5 times
If the capacity expansion limit is near, the capacity expansion limit is set to Integer.MAX_VALUE
If the capacity expansion limit is exceeded, an exception is thrown, and the capacity expansion fails and the element addition fails

As an Easter egg, the ArrayList will load lazily when it first adds a single element, expanding the container’s capacity to 10. This also proves that official comments do have some ambiguity and lag when it comes to the actual code

Iterator implementation

In the process control, there is a writing method for each, without indexing, subscript, you can complete the array element traversal. In fact, it is implemented on an iterator basis, and the Java class being iterated must implement the iterator methods internally

Here, through the iterator in the ArrayList container implementation, a brief introduction to the implementation principle of iterators

ArrayList<Integer> ArrayList = new ArrayList<>();
ArrayList.add(1);
ArrayList.add(1);
ArrayList.add(1);
Iterator<Integer> iterator = ArrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}
Copy the code

The above is an example of the use of iterators, which the IDE might suggest can be enhanced for loops instead. This also reinforces the fact that the underlying implementation of the enhanced for loop is based on iterators

The method called is iterator(), and the source code is analyzed from there, showing only the general implementation and a few details

public Iterator<E> iterator(a) {
    return new Itr();
}
Copy the code

The iterator() method actually returns a private inner class object new Itr()

private class Itr implements Iterator<E> {
    // Return the next index of the element to be returned
    int cursor;
    // We need to return the last index of the element. -1 indicates that there is no next index
    int lastRet = -1;
    // Record the number of modification operations of the ArrayList
    int expectedModCount = modCount;

    // prevent creating a synthetic constructor
    Itr() {}

    // Whether there is a next element
    public boolean hasNext(a) {
        // If the next index is the same as the actual stored data element, there is no next element
        returncursor ! = size; }// Get the next data element
    @SuppressWarnings("unchecked")
    public E next(a) {
        // Check whether there are concurrent modification operations
        checkForComodification();
        int i = cursor;
        // No data elements are traversable
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            // The concurrent modification is abnormal
            throw new ConcurrentModificationException();
        // Move the index back one bit
        cursor = i + 1;
        // Return the element at the current index and change lastRet to the index of the current element
        return (E) elementData[lastRet = i];
    }

    // Delete the data element
    public void remove(a) {
        // Determine whether the data element at the current index is the last
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            // Try to delete an element by calling the remove method in the ArrayList to remove the element in the current index
            ArrayList.this.remove(lastRet);
            // To return the next index of the element, advance by 1
            cursor = lastRet;
            / / modify lastRet
            lastRet = -1;
            // Synchronize the number of modifications. Remove is the modification operation
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw newConcurrentModificationException(); }}// Check whether the iterator and ArrayList are modified the same number of times
    final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

That’s a simple description of the iterator implementation in the ArrayList. It can be found that for each is very similar to the positioning of the iterator. There is also a method forEachRemaining in the iterator. Specific no longer repeat, interested in their own exploration

This is the implementation of an iterator in an ArrayList

Here, be aware of the remove() method inside the iterator, which can cause unnecessary trouble

Deletes the element at the current index positionArrayList.this.remove(lastRet);
The index of subsequent elements is collectively moved one bit forwardcursor = lastRet;
forremove(), needs to be called firstnextOtherwise, it will causeIllegalStateException

Now, the source code once again read the doubt, 2021-04-15 16:14

Exceptions can easily arise if multiple threads operate simultaneously, modify an ArrayList container, or use iterators

Therefore, the ArrayList iterator implementation requires modCount to record the number of container operations in real time to avoid concurrent changes

Iterators themselves are useful, of course, for containers that have no index subscripts, such as traversing sets

It is worth noting that iterators operate on elements more efficiently than methods such as get(), just so you know

summary

For the container class source reading, and no imagined in the difficult. Also very interesting, the following LinkedList, HashMap container class, but also to deepen their understanding of data structure, algorithm, very useful

Of course, any source reading must be in conjunction with the current JDK version, which is constantly changing

Don’t be obsessed with JDK8, there is no possible to fight all over the world, and don’t let the previous understanding interfere with the current reading

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

ArrayList analysis

An overview of the

The basic use

Initialize the

Initialization with no parameter

There are parameters for initialization

capacity

Iterator implementation

summary

ArrayList analysis

An overview of the

The basic use

Initialize the

Initialization with no parameter

There are parameters for initialization

capacity

Iterator implementation

summary

Related Posts

SpringBoot integration Swagger (10) used annotations | Java with notes

Linear programming for programming problems

Redis Distributed lock: A simplified version of distributed lock based on AOP and Redis implementation