preface

Why read the source code? In a word, to write better programs. On the one hand, only by understanding the code execution process, can we better use the tools and frameworks provided by others to write efficient programs. On the other hand, some of the classic code behind the ideas and skills are worth learning, through reading the source code, to help improve their ability.

Of course, utilitarian speaking, interview like to ask the source code, reading the source code also helps improve the probability of passing the interview.

In line with today’s theme, a very simple question, when we first learned about sets, we all used the following code, but do the following lines of code make a difference?

List list1 = new ArrayList();
List list2 = new ArrayList(0);
List list4 = new ArrayList(10);
Copy the code

One might say, default without an initial value, construct an array with an initial value. Is it really so? If you are wondering about the above question, you should look at the source code.

The process of learning programming must not follow others’ opinions, be sure to see for yourself.

Everyone has a different way of reading the source code, so I’ll just say it in the way I’m used to. For today’s topic, what is an ArrayList? How does it work? It is extended to a line, look at the name of the class and its inheritance system – it is why, look at the constructor – how to build an object, of course, the constructor will use some variables, so before that we need to understand the use of constant values and variable values, and in the end, we need to understand the commonly used methods, and how they are implemented.

For reading most classes, you basically follow: class name — > variable — > constructor — > common methods.

This article will only take a representative sample, not cover every line of code.

Class signature

There is no such thing as a class signature. In contrast to a function signature, it simply means the name of a class, which interfaces it implements, which classes it inherits, and some generic requirements.

public class ArrayList<E> extends AbstractList<E> 
       implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code

As you can see from the above code, ArrayList implements:

Cloneable, Serializable interface, with clone (note the difference between deep copy and shallow copy) and serialization capabilities,

RandomAccess interface, with the ability of RandomAccess, the random here is mainly based on the array based on the array index to obtain the value, later combined with LinkedList analysis is easier to understand.

The List interface, indicating that it is an ordered List (note that the order here refers to the order in which it was stored and retrieved, not the order of the elements themselves), can store repeating elements.

AbstractList implements the List interface, and AbstractList implements some common operations that can be inherited from a specific implementation class to greatly reduce code duplication. Methods can be overridden if necessary.

variable

Private static Final Long serialVersionUID = 8683452581122892189L; Private static final int DEFAULT_CAPACITY = 10; private static final int DEFAULT_CAPACITY = 10; Private static final Object[] EMPTY_ELEMENTDATA = {}; // A constant is essentially an empty array of type Object Private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // Transient Object[] elementData; Private int size; private int size; private int size;Copy the code

EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA are the same except for the name of the variable. However, the comments and subsequent methods show that, in short, when initialization, EMPTY_ELEMENTDATA, Different constructors take different variable names, i.e

List list1 = new ArrayList(); DEFAULTCAPACITY_EMPTY_ELEMENTDATA List list2 = new ArrayList(0); // Use EMPTY_ELEMENTDATACopy the code

Why bother? Are the gods busy? Obviously not. Don’t believe me? Keep reading.

A constructor

Public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 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); }} public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) ! = 0) { if (elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

As shown above, ArrayList has three constructors:

If no size is specified, an empty array is constructed. The default size is 10 only when the first element is added. So it’s not always the case that we construct an array of capacity 10, but it’s only now that we understand why some specifications often suggest that we specify an initial capacity, because it saves one expansion operation. Notice that DEFAULTCAPACITY_EMPTY_ELEMENTDATA is used.

If the value is greater than 0, an array is constructed with the specified value. If the value is equal to 0, an empty array is constructed, but EMPTY_ELEMENTDATA is used.

What’s the difference? The key lies in the operation during capacity expansion. Keep reading.

Remember that an ArrayList expansion can only happen when an element is added.

Commonly used method

There are a lot of common methods in ArrayList, so let’s take a look at the external methods, excluding a bunch of private methods and internal classes:



It seems to be a lot, but here are just a few common ones, and the rest can be looked at by analogy.

add(E e)

The first most common method, add elements

Public Boolean add(E E) {public Boolean add(E E) {ensureCapacityInternal(size + 1); ElementData [size] = e; size++; elementData[size++] = e; return true; }Copy the code

As you can see, when adding elements, the first step is to check whether the array capacity is sufficient. If not, expand the array capacity. The key of add method is to check the capacity

Check capacity: ensureCapacityInternal(int minCapacity)

// Check whether the capacity is sufficient, Private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) {// If the capacity is not specified, If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return math. Max (DEFAULT_CAPACITY, minCapacity); } return minCapacity +1 return minCapacity; } private void ensureExplicitCapacity(int minCapacity) {// Record the number of changes, which is used to quickly fail when the elements are modified. Not here. modCount++; If (minCapacity - elementdata. length > 0) grow(minCapacity); }Copy the code

The key comes, how to expand

Grow (int minCapacity)

Private void grow(int minCapacity) {// oldCapacity = elementData.length; // the newCapacity is 1.5 times the oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); If (newcapacity-mincapacity < 0) newCapacity = minCapacity; if (newcapacity-mincapacity < 0) newCapacity = minCapacity. // The new capacity is greater than the maximum length of the array. The value can be integer. MAX_VALUE or MAX_ARRAY_SIZE. if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); // Copy old array elements to new array elementData = array.copyof (elementData, newCapacity); }Copy the code

The code above has a key method array.copyof (elementData, newCapacity) for copying the elements of a collection, which I won’t go into here.

Back to the original question

When you create an ArrayList,

Initial capacity is not specified, that is

List list1 = new ArrayList(); // Create an empty array. The first time you add elements, expand the array to 10 and add elements.Copy the code

Specifies that the initial capacity is 0, that is

List list2 = new ArrayList(0); // Construct an empty array, but with a different variable name. The first time you add an element, you expand the array to 1 and add elements.Copy the code

Specify an initial capacity of 10, i.e

List list4 = new ArrayList(10); // Create an array with a capacity of 10.Copy the code

Therefore, if we have a rough idea of the number of elements to use, we should specify it in the constructor to reduce the number of expansions and to some extent increase efficiency.

summary

So far, I’ve only scratched the surface of the ArrayList constructors and add methods, but I haven’t gone much further. It’s hard and unnecessary to write every method.

Through the above content, review their reading source process, not only to “understand”, but also to “view its overview”, for some core process, we need to carefully analyze; However, for inexperienced beginners, it is difficult to figure out every detail. Some contents may not be understood at this stage. It is important to grasp the overall structure. If you dive into a detail right from the start, you may get lost in it and never get out.

You’re asking me if I know everything about ArrayList, and I don’t. However, as I write here, MY understanding is much deeper.

In the mind that probably understand is not necessarily really understand, only hold the content to write out for others to understand the state of mind, it is possible to deepen understanding. I don’t know. Do you get it?