Java Collection ArrayList Source Code Analysis

Today, I’ll take a look at the source code of ArrayList. Unlike other blogs, many of them translate comments from the source code and post them directly into an article. Xiaobian is going to change a writing style, with a problem to see the source code may be more harvest, this article will be around the following several issues to discuss.

First, problems arise

• [] elementData; [] elementData; [] elementData; ?

• 2. Since ArrayList can automatically expand, how is its expansion mechanism implemented?

• 3. What is the iterator returned by iterator() that calls ArrayList?

• 4, adopt the ArrayList iterators iterate through collection, the collection performs relevant modification operations why throw ConcurrentModificationException, how can we avoid?

• 5, When the collection is expanded or cloned, it is inevitable to copy the collection. So how does ArrayList copy the array?

• Serialization mechanism in ArrayList

ArrayList, ArrayList, ArrayList, ArrayList, ArrayList, ArrayList, ArrayList

Second, answer questions

1. WhyArrayListThe container that stores elements in the collection is declared astransient Object[] elementData;?

An ArrayList is a collection container, and if you’re a container, you have to store something, and if you need to store something, you have to store it somewhere. It’s like saying you need a ton of water, you have to have a pool for it! Or if you want to fill dozens of milliliters of water, you have to fill that bottle or bag for you. The difference is that we need different containers for different sizes of water!

Since ArrayList already supports generics, why should the container definition of ArrayList source be defined as the following Object[] type?

transient Object[] elementData;

Transient E[] elementData; Or use transient Object[] elementData; Declarations are allowed. The difference is that the former requires us to perform a cast when we instantiate elementData, and this cast requires us programmers to ensure that the cast is error-free. To warn programmers about possible casting exceptions, the compiler will issue a Type safety: Unchecked cast from String[] to E[] warning, which will throw you into confusion: Unchecked Type safety: Unchecked from String[] to E[] warning

Public class MyList<E> {// Declare an array of type E[] E[] DATAS; Public MyList(int initialCapacity) {DATAS = (E[]) new Object[initialCapacity]; } public E getDATAS(int index) {return DATAS[index];
    }
    public void setDATAS(E[] dATAS) { DATAS = dATAS; }}Copy the code

The above code declares the array E[] at 1. The type depends on the actual type you pass in, but note that when you initialize a DATAS, you can’t initialize it like this:

E[] DATAS = new E[10]; // This code will report an error

That is, arrays of generics cannot be externalized by new generics [size]; In other words, the JVM itself does not support generics, just compiler type erasure. There are two ways:

• 1. Do a transformation as described above, but not recommended

  As the code above shows, you can initialize to Object[] and then convert to E[], but you have to make sure that the conversion is error-free. This is usually not recommended!

• Object[]

  This is how ArrayList source code is defined, so let’s see how ArrayList is initialized:

public ArrayList(int initialCapacity) {
    if(initialCapacity > 0) {// This. ElementData = new Object[]; }else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

There’s one more thing to note, though, but you can get unexpected results when you call ArrayList’s toArray method to turn collections into arrays of objects, as I’ll explain in another blog post.

[ArrayList actually has twins, but there are big differences!]

Summary: In general, we need to know that generic arrays cannot be externalized, and the solution! You might be wondering why I didn’t talk about transient, but I’ll put that in the serialization deserialization.

2, sinceArrayListIt can automatically expand capacity, so how is its expansion mechanism implemented?

Sometimes, we need to make sure that when we add water, the original container can also fill the new water without overflowing, which is the automatic expansion mechanism of ArrayList. As we can imagine, if the list size is 10, it normally only holds 10 elements. We wonder what magic the bottom layer does when we call add() after that, so let’s look at how the add() method is implemented:

Public Boolean add(E E) {// Ensure the internal size of the list, size is the actual number of elements ensureCapacityInternal(size + 1); elementData[size++] = e;return true;
}
Copy the code

ElementData [size++] = e; elementData[size++] = e; Otherwise, you need to expand, so how to expand? Let’s go to the ensureCapacityInternal() method, and it’s important to remember the following parameters:

• minCapacityAlways represents the actual total number of elements after the increment
• newCapacityAlways indicates that the list satisfies the storageminCapacityTo expand the size of the element list

Private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData,  minCapacity)); } // This method is only used for the first time, MinCapacity private static int calculateCapacity(Object[] elementData, int minCapacity) { Indicates that the ArrayList is newly initialized and has not yet added any elementsif (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    returnminCapacity; } private void ensureExplicitCapacity(int minCapacity) {modCount++; Elementdata. length is the total size of the list, not the actual number of elements in the list. Size is the actual number of elements in the listif (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
Copy the code

If the add() method has not been called, the set will be expanded to 10 by default. The value of DEFAULT_CAPACITY is 10, the maximum value. Grow () is valid only if the number of elements in the container is greater than 10 and no space is available.

Private void grow(int minCapacity) {// Get the old list size int oldCapacity = elementdata.length; / / expansion after the new container size, the default add half... 1 int newCapacity = oldCapacity + (oldCapacity >> 1); / / if the expansion after less than half, the new container size equals minCapacity... 2if(newCapacity - minCapacity < 0) newCapacity = minCapacity; // If the new container is larger than MAX_ARRAY_SIZE,if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); } // Maximum value Integer.MAX_VALUE private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
    	throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the code

The top 1 >> represents a shift to the right, which is equal to dividing by 2 and reducing by half, which may be true when addAll() is called at 2.

Here are a few:

Conclusion:

The capacity expansion mechanism is as follows:

• 1. Set the list size by defaultnewCapacityIncrease the size by half, that is, if it was 10, the new size is 15;
• 2, if the new sizenewCapacityStill can’t get enoughaddThe total number of entries that came inminCapacity, changes the list size to andminCapacityAs large; That is, if I expand it by halfnewCapacityAt 15, butaddThe total number of elements that came inminCapacityIs 20, then 15 obviously cannot store 20 elements, then willnewCapacityEnlarged to 20, just enough to store 20 elements;
• 3. If the size of the expanded list is larger than that of the expanded list2147483639That is greater thanInteger.MAX_VALUE - 8, where additional processing is required, because the actual total element size may be larger thanInteger.MAX_VALUEAnd it’s going to be bigger when the actual total element size isminCapacityThe value is greater thanInteger.MAX_VALUEThat is greater than the2147483647When, at this timeminCapacityThe value of int will become negative because int is signed and becomes negative when the maximum value is exceeded

The third point above also reflects a kind of wisdom, that is, when something is likely to go wrong, we should deal with it in advance, rather than wait for the error to happen and then deal with it. That’s why we monitor operations.

3, callArrayListtheiterator()What is the iterator returned?

We know that all collections are implementation classes of the Collection interface, and because collections inherit from the Iterable interface, all collections are Iterable. We often use iterators for collections to iterate over collection elements, as in the following code:

ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b"); Iterator<String> iter = list.iterator();while (iter.hasNext()) {
    String item = iter.next();
    System.err.println(item);
}
Copy the code

We can get the iterator object of a collection by calling its iterator() method. How does the iterator() method work in an ArrayList?

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

Super simple. I just created an object called Itr so what is this Itr? The Itr class is an inner class of ArrayList, defined as follows:

 private class Itr implements Iterator<E> {
    int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; - 1ifno such int expectedModCount = modCount; . 1Itr() {}
    public boolean hasNext() {... }// The implementation is removed by public Enext() {... } public voidremove() {... } public voidforEachRemaining(Consumer<? super E> consumer) {... } final voidcheckForComodification() {...}
}
Copy the code

This Iterator implements the Iterator interface and implements related methods, providing us with the ability to traverse collections. Summary: The iterators of ArrayList are implemented as inner classes by default. Implementing a custom Iterator requires only implementing the Iterator interface and related methods. Implementing the Iterable interface means that the implementation class has the ability to iterate like a for-each loop.

4,ArrayListWhy is the iterator that iterates through the collection thrown when performing related modification operations on the collectionConcurrentModificationExceptionHow can we avoid it?

In section 3 we looked at the ArrayList iterator’s source code, as we all know, if in the process of iteration calls the iterator internal remove or clear method will throw ConcurrentModificationException, that is why on earth? Let’s take a look. First design are two important variables, here is a expectedModCount, another is modCount expectedModCount defined in set internal iterators, as the third section source 1 space, modCount defined in AbstractList. As you can see in section 3 (1), the default is equal, i.e., expectedModCount = modCount, which only throws an exception if it doesn’t want to wait. Is really don’t want to wait to throw an exception? Let’s look at the next method inside the iterator:

public E next() {// Check the checkForComodification() of the two variables before iteration; int i = cursor;if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return(E) elementData[lastRet = i]; } // Check final voidcheckForComodification() {
    if(modCount ! = expectedModCount) throw new ConcurrentModificationException(); }Copy the code

You can see that they do get an error when they don’t want to wait between them, so the question is, when does that cause them not to want to wait? Let’s take a look at the ArrayList remove method:

public E remove(int index) { rangeCheck(index); ModCount ++; E oldValue = elementData(index); int numMoved = size - index - 1;if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    
    return oldValue;
}
Copy the code

You can see that when the remove() method is called, modCount is actually changed, causing an error. So what can we do to avoid the error that we want to add or delete data during the iteration? The answer is to use the remove() method inside the iterator.

Conclusion:

The iterator cannot modify the set being iterated because the modCount and expectedModCount variables do not want to wait.

5. When the collection is expanded or cloned, it is inevitable to copy the collection, soArrayListHow is array copy implemented?

Copying collections in ArrayList is done by calling the copyOf method of Arrays as follows:

public static <T> T[] copyOf(T[] original, int newLength) {
    return(T[]) copyOf(original, newLength, original.getClass()); . 2 } public static <T,U> T[] copyOf(U[] original, int newLength, Class<? Extends T[]> newType) {// The data type passed in is checked before a new array object is created. @suppressWarnings ("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
Copy the code

Finally, the ArrayCopy method of System is called.

6,ArrayListSerialization mechanism in

In the first section, we learned that an ArrayList stores data as follows:

transient Object[] elementData;
Copy the code

We will find it very strange that this is a collection to store the core elements, but declared as transient, does not serialize? It’s not scientific! The writeObject method is used to serialize the data stored in an ArrayList.

writeObject

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    
    // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // This place does a serialization operationfor (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
Copy the code

From the above code we can see that the ArrayList actually serializes elementData, but it does so because elementData can have a lot of null elements. In order not to serialize null elements, Therefore, the writeObject and readObject methods are customized.

Thanks for reading and welcome to comment