Original address: xeblog.cn/articles/19

This article focuses on the implementation of ArrayList in JDK8.

ArrayList profile

An ArrayList is an array queue that maintains a Java array internally, and it is dynamic and grows automatically. It inherits AbstractList and implements List, RandomAccess, Cloneable, Serializable and other interfaces.

Pros and cons of ArrayList

advantages

  • Support random access, because its internal is an array, random access to the element is equal to access through the array subscript, random access to the element efficiency is high.
  • The elements are ordered (in the order they were added).
  • Support for automatic expansion (both advantages and disadvantages).

disadvantages

  • Threads are not safe.
  • Automatic expansion is inefficient. Each expansion requires adding all elements to the new array.
  • Add and delete operations require moving elements in an array.

Question: Why ArrayList implements a List interface from AbstractList?

  • I can’t tell the truth of this answer, but it can be aired out.stackoverflowThe answer was yesJosh Bloch(Java Collections framework author) design error, the author thought such design was valuable, but later discovered that it was not.

    Stackoverflow.com/questions/2…

  • It is convenient to use the Java reflection mechanism to get all interfaces implemented by methods, because if not explicitly implementedListInterface, reflection to obtain the interface also need to obtain the parent class, and then through the parent class to obtain the interface.
  • Convenience can be seen at a glanceArrayListTo achieve theListInterface (perfunctory.gif).
  • The other…

Partial fields of ArrayList

/** * The default capacity is 10 */
private static final int DEFAULT_CAPACITY = 10;

/** * empty array */
private static final Object[] EMPTY_ELEMENTDATA = {};

/** * for an empty array of default size. Distinguish this from EMPTY_ELEMENTDATA so you know how much to inflate when you add the first element. * The default array to initialize an ArrayList with a no-argument construct */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * An array that stores the elements of ArrayList. When adding the first element, if elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * then the array is the default length of 10 */
transient Object[] elementData;

/** * The number of elements in ArrayList */
private int size;
Copy the code

Constructor of ArrayList

With aintThe constructor for the type parameter, passed inArrayListThe initial length of

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

The no-argument construction of JDK8

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

A no-argument construct for JDK7

public ArrayList(a) {
	this(10);
}
Copy the code

In JDK8, the default no-argument constructor is used to initialize the ArrayList. The actual size of the ArrayList is 0 until the add() method is executed, and the default length is 10 until the first element is added.

Passing in the constructor of a collection object, constructs a class containing the collection elementsArrayList

public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	if((size = elementData.length) ! =0) {
			// c.toArray might (incorrectly) not return Object[] (see 6260652)
			if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
			// replace with empty array.
			this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

How does ArrayList grow dynamically?

Let’s start with the add(E, E) method

public boolean add(E e) {
	// Determine if the array will grow when this element is added
	ensureCapacityInternal(size + 1);
	// Add elements
	elementData[size++] = e;
	return true;
}
Copy the code
/** * This method is used to determine if the array capacity is exceeded when the element is added
private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// If the array is instantiated using the default constructor, elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA returns true
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
			If minCapacity is greater than 10, the value of minCapacity is returned
			return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
	/ / fail - fast mechanism, concurrent modification will throw new exception: a ConcurrentModificationException ()
	modCount++;

	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
			// The length of the new element exceeds the current array length, so we call the increase array length method
			grow(minCapacity);
}
Copy the code

Look at the grow(int minCapacity) method to see how an ArrayList automatically grows its capacity

// The maximum array size allocated
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	// The increased capacity is equal to 1.5 times the old capacity
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
			newCapacity = minCapacity;
	 // MAX_ARRAY_SIZE is the maximum value of int minus 8
	if (newCapacity - MAX_ARRAY_SIZE > 0);
			newCapacity = hugeCapacity(minCapacity);
	// The array.copyof () method is used to copy the elements of the original array into the new array, whose length is newCapacity
	elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

HugeCapacity (int minCapacity) methods are listed here

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

Int newCapacity = (oldCapacity * 3)/2 + 1; The increased capacity is equal to 1.5 times the old capacity plus 1. In JDK8, bit operation is used to increase the old capacity by 1.5 times.

Manually adjust the capacity of the ArrayList

Before adding a large number of elements, you can manually increase the capacity of the ArrayList by calling the ensureCapacity(int minCapacity) method to reduce the amount of incremental reallocation

public void ensureCapacity(int minCapacity) {
	intminExpand = (elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// any size if not default element table
			? 0
			// larger than default for default empty table. It's already
			// supposed to be at default size.
			: DEFAULT_CAPACITY;

	if(minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}Copy the code

The trimToSize() method adjusts the capacity of the ArrayList to the size of the actual elements

public void trimToSize(a) {
	modCount++;
	if (size < elementData.length) {
			elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code

The mechanism of fail – fast

Because the ArrayList is not thread safe, so if in the process of using the iterator has modified the ArrayList other threads, so will be thrown throw new ConcurrentModificationException () abnormalities, This is the fail-fast mechanism. The fail-fast mechanism is determined by the modCount field, which is a field of the parent class AbstractList. The modCount field automatically increals every time an ArrayList is modified. The iterator initializes and assigns the value of modCount to the expectedModCount field of the iterator. Iterator internals for ArrayList (part)

public Iterator<E> iterator(a) {
	return new Itr();
}
		
private class Itr implements Iterator<E> {
	int cursor;       // index of next element to return
	int lastRet = -1; // index of last element returned; -1 if no such
	int expectedModCount = modCount;

	Itr() {}

	public boolean hasNext(a) {
		returncursor ! = size; }@SuppressWarnings("unchecked")
	public E next(a) {
		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;
		return (E) elementData[lastRet = i];
	}

	public void remove(a) {
		if (lastRet < 0)
				throw new IllegalStateException();
		checkForComodification();

		try {
				ArrayList.this.remove(lastRet);
				cursor = lastRet;
				lastRet = -1;
				expectedModCount = modCount;
		} catch (IndexOutOfBoundsException ex) {
				throw newConcurrentModificationException(); }}}Copy the code

When executing the next() and remove() methods, the checkForComodification() method will be called to determine whether expectedModCount is still equal to modCount. If it is not, it means that other threads have modified the ArrayList. At this time will throw an exception throw new ConcurrentModificationException ().

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

To be supplemented…