​​​​

preface

ArrayList we use almost every day, usually very familiar with, but in the real interview, found that many people are still not clear about the details of the source code, leaving a poor impression on the interviewer, so that the interview is cool. This section takes a look at the source code for ArrayList.

1. Overall architecture

1.1 Source Code Analysis

ArrayList is a set of arrays that support RandomAccess, ordered and repeatable elements, AbstractList, List, RandomAccess, Clone, Serializable interface, etc.

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

1.2 architecture diagram

​

1.3 Detailed Discussion

1.3.1 Implement RandomAccess interface

Public Interface RandomAccess {} public interface RandomAccess {} public interface RandomAccess {} Public interface RandomAccess {} Public interface RandomAccess {}

But then people ask, what is fast random access? What does it do?

By looking at the binarySearch () method in the Collections class, the source code looks like this:

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }
Copy the code

**indexedBinarySerach(list,key) or iteratorBinarySerach(list,key)** determine whether a list implements RandomAccess.

(Instanceof is used to determine whether an object is of a class or interface type.)

1.3.2 Implementing the Cloneable Interface

Cloneable is a tag interface that, like RandomAccess, does not declare any method bodies or constants. In other words, to clone an object, you must implement the Cloneable interface. Indicates that the class can be cloned.

The clone method can be overridden in ArrayList.

public Object clone() { try { ArrayList<? > v = (ArrayList<? >) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); }}Copy the code

From the above code we know two things:

1. At the bottom layer, the copyOf Arrays method, namely System. Arraycopy, is a native method.

2. If the class does not inherit the clone interface, throws an exception, namely CloneNotSupportedException abnormalities.

2. Field attributes

2.1 the source code

​

The overall structure of an ArrayList is relatively simple. It is an array structure. It is relatively simple.

​

2.2 Architecture diagram and description of each element

DEFAULT_CAPACITY: indicates the initial size of the array. The default is 10. Remember this number.

EMPTY_ELEMENTDATA: Represents an empty array. ElementData: Represents an array of type Object.

Size: Indicates the size of the current array. The type is int. Volatile is not used, and is not thread-safe.

3. Source code analysis

3.1 the initialization

We have three initialization methods: no parameters direct initialization, specified size initialization, specified initial data initialization, source code as follows:

3.1.1 Specifying the size for 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

Note: Initialize the collection size to create an ArrayList collection. When it’s greater than zero, given how much it’s going to be, it’s going to be how big the array is going to be; When equal to 0, create an empty array; When less than 0, an exception is thrown.

3.1.2 Direct Initialization without Parameters

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

Note that this no-argument constructor creates an array declared by DEFAULTCAPACITY_EMPTY_ELEMENTDATA, with an initial capacity of 0 instead of 10 as expected.

3.1.3 Array Initialization

public ArrayList(Collection<? Extends E> c) {//elementData is a container that holds arrays. By default, null elementData = c.toarray (); // If ((size = elementData.length)! If (elementData.getClass()! = 0) {// If the collection element type is not Object, we will say Object if (elementData.getClass()! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else {// Given a set (c) with no value, default empty array this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

3.2 Implementation of addition and Capacity expansion

3.2.1 Add elements directly to the end of the array

If you add an element directly to the end of an array, you need to check whether the current array length is available and whether it needs to be expanded before performing the assignment.

Note: This assignment is only one line, and it is not thread safe, not considering concurrent scenarios.

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

3.2.2 Adding elements to the specified position

If an element is added to a specified location, the first step is to determine whether the current index index is valid. The second step is the same as above to determine whether the current array length is available and whether it needs to be expanded. The third step is to copy the array using the native method System.

Note: Assignment is also thread-unsafe, without considering concurrent scenarios.

Public void add(int index, E element) {rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }Copy the code

3.2.3 capacity

Let’s look at the source code of EnrecapityInternal:

Private void ensureCapacityInternal(int minCapacity) { If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = math. Max (DEFAULT_CAPACITY, minCapacity); } // Ensure sufficient capacity ensureExplicitCapacity(minCapacity); }Copy the code

Private void ensureExplicitCapacity(int minCapacity) {// record array is modified modCount++; If (minCapacity - elementdata. length > 0) grow(minCapacity); }Copy the code

Private void grow(int minCapacity) {int oldCapacity = elementdata.length; private void grow(int minCapacity) {oldCapacity = elementdata.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newcapacity-mincapacity < 0) newCapacity = minCapacity; if (newcapacity-mincapacity < 0) newCapacity = minCapacity; // If the expanded value is greater than the maximum number of arrays the JVM can allocate, If (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); }Copy the code

The notes should be more detailed. Four points to note are :(note 😝)

• The capacity expansion rule is not double, but half of the original capacity + half of the original capacity, that is, the capacity after expansion is 1.5 times of the original capacity;

• The maximum value of the array in the ArrayList is integer. MAX_VALUE, beyond which OutOfMemoryError is thrown.

• Nulls can be added to collections because arrays can have null values.

• assignment is very simple, just add elements to the array: elementData [size++] = e. It is through this method of assignment that threads are not safe.

3.2.4 Nature of expansion

Arrays. CopyOf (elementData, newCapacity); , the essence of this line of code is to describe the copy between arrays. Expansion will first create a new array that meets our expected capacity, and then copy the data of the old array. We copy the data through the System.

/** * @param srcPos starts from the array * @param dest target array * @param destPos starts from the index position of the target array * @param length The length of the copy * this method returns no value, Public static native void arrayCopy (Object SRC, int srcPos, Object dest, int destPos, int length); public static native void arrayCopy (Object SRC, int srcPos, Object dest, int destPos, int length);Copy the code

A look at the source code shows that this method is declared native, which means it is not written in Java. Java can use JNI to call methods written in other languages (mostly C/C++). In this article, we will briefly analyze the implementation of the System.arrayCopy () method by looking at the source code in the OpenJDK.

In short, System. arrayCopy implements assignment via c/ C ++ Pointers.

If you open openJDK \hotspot\ SRC \share\vm\prims\jvm. CPP, you can see a method called JVM_ArrayCopy, but this method does not actually copy the code, but simply checks the source and destination arrays are not empty, and rules out some exceptions

/* Java.lang.System arrayCopy method */ JVM_ENTRY(void, JVM_ArrayCopy(JNIEnv *env, jclass ignored, jobject SRC, jint src_pos, jobject dst, jint dst_pos, jint length)) JVMWrapper("JVM_ArrayCopy"); / / Check if we have a null Pointers/Check/source arrays and purpose is not null if (SRC = = null | | DST = = null) { THROW(vmSymbols::java_lang_NullPointerException()); } arrayOop s = arrayOop(JNIHandles::resolve_non_null(src)); arrayOop d = arrayOop(JNIHandles::resolve_non_null(dst)); assert(s->is_oop(), "JVM_ArrayCopy: src not an oop"); assert(d->is_oop(), "JVM_ArrayCopy: dst not an oop"); Klass ()->copy_array(s, src_pos, d, dst_pos, length, thread); JVM_ENDCopy the code

2, openJDK \hotspot\ SRC \share\vm\oops\ objarrayklass. CPP file copy_array method

Void ObjArrayKlass::copy_array(arrayOop s, int src_pos, arrayOop d, Int dst_pos, int length, TRAPS) {// Check that s is an array assert(s->is_objArray(), "must be obj array"); // If the destination array is not an array object, ArrayStoreException is thrown. d->is_objArray()) { THROW(vmSymbols::java_lang_ArrayStoreException()); } / / Check is all offsets and lengths are non negative / / testing non-negative if (src_pos < 0 subscript parameter | | dst_pos < 0 | | length < 0) { THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException()); } // Check if the ranges are valid if ((((unsigned int) length + (unsigned int) src_pos) > (unsigned int) s->length()) || (((unsigned int) length + (unsigned int) dst_pos) > (unsigned int) d->length()) ) { THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException()); } // Special case. Boundary cases must be checked first // This allows the following call: copy_array(s, s.length(), d.length(), 0). // This is correct, since the position is supposed to be an 'in between point', i.e., s.length(), // points to the right of the last element. //length==0; } //UseCompressedOops is just to distinguish between narrowOop and OOP, // narrowOop* const SRC = if (UseCompressedOops) {narrowOop* const SRC = objArrayOop(s)->obj_at_addr<narrowOop>(src_pos); narrowOop* const dst = objArrayOop(d)->obj_at_addr<narrowOop>(dst_pos); do_copy<narrowOop>(s, src, d, dst, length, CHECK); } else { oop* const src = objArrayOop(s)->obj_at_addr<oop>(src_pos); oop* const dst = objArrayOop(d)->obj_at_addr<oop>(dst_pos); do_copy<oop> (s, src, d, dst, length, CHECK); } // Either oop or narrowOop depending on UseCompressedOops. Template <class T> void ObjArrayKlass::do_copy(arrayOop s, T* src, arrayOop d, T* dst, int length, TRAPS) { BarrierSet* bs = Universe::heap()->barrier_set(); // For performance reasons, we assume we are that the write barrier we // are using has optimized modes for arrays of references. At least one // of  the asserts below will fail if this is not the case. assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt"); assert(bs->has_write_ref_array_pre_opt(), "For pre-barrier as well."); if (s == d) { // since source and destination are equal we do not need conversion checks. assert(length > 0, "sanity check"); bs->write_ref_array_pre(dst, length); // Copy:: conjoinT_oOPs_atomic (SRC, DST, length); } else { // We have to make sure all elements conform to the destination array Klass* bound = ObjArrayKlass::cast(d->klass())->element_klass(); Klass* stype = ObjArrayKlass::cast(s->klass())->element_klass(); if (stype == bound || stype->is_subtype_of(bound)) { // elements are guaranteed to be subtypes, Bs ->write_ref_array_pre(DST, length); Copy::conjoint_oops_atomic(src, dst, length); } else { // slow case: need individual subtype checks // note: don't use obj_at_put below because it includes a redundant store check T* from = src; T* end = from + length; for (T* p = dst; from < end; from++, p++) { // XXX this is going to be slow. T element = *from; // even slower now bool element_is_null = oopDesc::is_null(element); oop new_val = element_is_null ? oop(NULL) : oopDesc::decode_heap_oop_not_null(element); if (element_is_null || (new_val->klass())->is_subtype_of(bound)) { bs->write_ref_field_pre(p, new_val); *p = element; } else { // We must do a barrier to cover the partial copy. const size_t pd = pointer_delta(p, dst, (size_t)heapOopSize); // pointer delta is scaled to number of elements (length field in // objArrayOop) which we assume is 32 bit. assert(pd == (size_t)(int)pd, "length field overflow"); bs->write_ref_array((HeapWord*)dst, pd); THROW(vmSymbols::java_lang_ArrayStoreException()); return; } } } } bs->write_ref_array((HeapWord*)dst, length); }Copy the code

Find the conjoint_oops_atomic function in openJDK \hotspot\ SRC \share\vm\utilities\copy. HPP and the narrowOop overloaded function which is not listed here

 // oops,                  conjoint, atomic on each oop
 static void conjoint_oops_atomic(oop* from, oop* to, size_t count) {
   assert_params_ok(from, to, LogBytesPerHeapOop);
   pd_conjoint_oops_atomic(from, to, count);
 }
Copy the code

Is_subtype_of in openJDK \hotspot\ SRC \share\vm\oops\klass. HPP

Bool is_subtype_of(Klass* k) const {juint off = k->super_check_offset(); Klass* sup = *(Klass**)( (address)this + off ); const juint secondary_offset = in_bytes(secondary_super_cache_offset()); if (sup == k) { return true; } else if (off ! = secondary_offset) { return false; } else { return search_secondary_supers(k); }}Copy the code

Openjdk \hotspot\ SRC \ os_CPU \windows_x86\vm\ copy_windows_x86.inline-. HPP is the pd_conjoinT_oOPs_atomic function

static void pd_conjoint_oops_atomic(oop* from, oop* to, size_t count) { // Do better than this: inline memmove body NEEDS CLEANUP if (from > to) { while (count-- > 0) { // Copy forwards *to++ = *from++; } } else { from += count - 1; to += count - 1; while (count-- > 0) { // Copy backwards *to-- = *from--; }}}Copy the code

3.3 delete

ArrayList can delete elements in many ways, such as by array subscript delete, delete by value or batch delete, etc., principle and idea are similar, we select by value subscript way to carry out the source code:

Public E remove(int index) {// Check whether the subscript is valid rangeCheck(index); modCount++; E oldValue = elementData(index); // numMoved specifies how many elements to move to the front of the index after the index is removed. // numMoved Int numMoved = size-index - 1; // Assign if (numMoved > 0) system. arrayCopy (elementData, index+1, elementData, index, numMoved); ElementData [--size] = null; // return oldValue; }Copy the code

It is important to note that when an element is deleted, we always move the elements behind the array forward to maintain the array structure.

3.4 to modify

Replace the element at the specified index index with element by calling set(int index, E Element). And returns the elements of the original array.

Public E set(int index, E element) {// Check whether the index is valid. E oldValue = elementData(index); // Replace the element cited with element elementData[index] = element; // Return oldValue; }Copy the code

3.5 the iterator

ArrayList implements the java.util.Iterator interface, mainly including whether there is the next element hasNext, return the next element next, delete remove, and determine the version number checkForComodification method.

3.5.1 Is there a next element hasNext

Public Boolean hasNext() {public Boolean hasNext() {size indicates the actual size of the next element. = size(); }Copy the code

3.5.2 Return the next element next

As you can see from the source code, the next method does two things. The first is to check whether the iteration can continue, and the second is to find the values of the iteration and prepare for the next iteration.

Public E next () {/ / iteration process, determine the version number have been modified, has been modified, throw ConcurrentModificationException abnormal checkForComodification (); Int I = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); Cursor = I + 1; cursor = I + 1; Return (E) elementData[lastRet = I]; }Copy the code

3.5.3 remove remove

Public void remove() {if (lastRet < 0) throw new IllegalStateException(); if (lastRet < 0) throw new IllegalStateException(); / / iteration process, determine the version number have been modified, has been modified, throw ConcurrentModificationException abnormal checkForComodification (); try { ArrayList.this.remove(lastRet); cursor = lastRet; LastRet = -1; lastRet = -1; ExpectedModCount = expectedModCount = expectedModCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}Copy the code

3.5.4 Checking the version number checkForComodification

final void checkForComodification() { if (modCount ! = expectedModCount) throw new ConcurrentModificationException(); }Copy the code

conclusion

This article starts from the overall architecture of ArrayList, from initialization, addition, expansion, deletion, iteration, modification and other core source code implementation, we found that ArrayList is actually encapsulated around the underlying array structure, if the JDK to modify the underlying code, we do not need to make any modifications, so that users do not feel.