JDK version: 1.8.0_271

Basic introduction to

The underlying data structure of an ArrayList is an array:

  1. Index represents the array index, counting from 0, and elementDatda represents the array itself
  2. DEFAULT_CAPACITYsaidThe initial size of the array, which defaults to 10
  3. Size indicates the size of the array. It is of type int and is not volatile. It is not thread safe
  4. ModCount counts the number of times the current array has been modified+ 1

Class notes

  1. If the put null value is allowed, the system automatically expands the capacity
  2. The time complexity of the size, isEmpty, GET, set, add and other methods isO(1)
  3. Is not thread-safe. In multithreaded cases, it is recommended to use the thread-safe class:Collections#synchronizedList
  4. If the array size is changed during an enhanced for loop or iterator iteration, it will fail quickly and throw an exception

The source code parsing

1. Initialization

There are three methods: direct initialization without parameters, specifying size initialization, and specifying initial data initialization.

The source code

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // The container that holds the array. The default is null transient Object[] elementData; 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) { Object[] a = c.toArray(); If ((size = a.length)! If (c.getclass () == arrayList.class) {elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); }} else {// the default empty array elementData = EMPTY_ELEMENTDATA; // The default empty array elementData = EMPTY_ELEMENTDATA; }}Copy the code

The following points can be obtained from the source code:

  1. The default size of the ArrayList is an empty array when initialized by the no-parameter constructor. The array size of 10 is the value of the array that was expanded when the first add was made.
  2. When specifying that the data is initialized, the array is initialized to an empty array even if the data passed in is empty. When the collection type passed in is ArrayList, elementData uses the array generated by toArray directly.

2. Add and expand

Adding an element takes two steps:

  1. Determine whether to expand the capacity
  2. ElementData array assignment, which is non-thread-safe
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public Boolean add(E E) { EnsureCapacityInternal (size + 1); ElementData [size++] = e; return true; }Copy the code

Expansion (ensureCapacityInternal) source

private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) {// If the size is not specified during the initialize, If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return math. Max (DEFAULT_CAPACITY, minCapacity); } // Otherwise return the minimum capacity required to store the current element return minCapacity; } private void explicitcapacity (int minCapacity) {// array change token +1 modCount++; If (minCapacity - elementData.length > 0) grow(minCapacity); if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // Int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); int newCapacity = oldCapacity + (oldCapacity >> 1); If (newcapacity-mincapacity < 0) newCapacity = minCapacity; // If (newCapacity - minCapacity < 0) newCapacity = minCapacity; // If (newCapacity - minCapacity < 0) newCapacity = minCapacity; // If the size of the new array exceeds the maximum, The value of MAX_ARRAY_SIZE is the maximum value represented by Integer. -8 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); ElementData = arrays.copyof (elementData, newCapacity); } private static int hugeCapacity(int minCapacity) {// Overflow if (minCapacity < 0) // overflow throw new OutOfMemoryError(); Return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }Copy the code

Java source has some points to pay attention to:

  1. Initialize a collection with an unspecified size. The first capacity expansion is 10
  2. When you add an element, modCount does it whether or not the array is expanded+ 1
  3. The maximum size of an array is integer.max_value, beyond which the JVM allocates no memory for the array
  4. When you add an element, there is no strict validation of the value, so ArrayList can be addednullValue.

What to learn from the source code:

  1. Code writing is elegant, a method does only one thing, easy to understand
  2. To be boundary conscious, the array index must not exceed the Integer maximum and must not be less than 0

3. The nature of expansion

Array expansion in ArrayList is done by calling the copyOf method of Arrays. Create a new array with the desired size, and then copy the elements from the old array. Copy is done by calling the system.arrayCopy method, which is a native modified method

/** * @param SRC * @param srcPos * @param dest * @param destPos * @param destPos * @param SRC * @param srcPos * @param dest * @param destPos * @param destPos * @param length * @param length * This method does not return a 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

4, delete,

In the source code about the deletion method:

  • public boolean remove(Object o): Deletes the first matching element
  • public E remove(int index): deletes the element at the specified location and returns the element
  • private void fastRemove(int index): Private method, byremove(Object o)The method call
  • public boolean removeAll(Collection<? > c): Removes all elements contained in the specified collection from this list.
  • public void clear(): Clear the collection
*/ public E remove(int index) {// check if the array is out of line, Index is larger than the size would throw IndexOutOfBoundsException abnormal rangeCheck (index); modCount++; / / when the index is less than 0, the values here can throw ArrayIndexOutOfBoundsException abnormal 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; } /** * Remove the first occurrence of the specified element from the set if it exists, and leave it unchanged if it does not exist. Return false */ public Boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; If (elementData[index] == null) {fastRemove(index); return true; } } else { for (int index = 0; index < size; If (o.data (elementData[index])) {fastRemove(index); return true; } } return false; } private void fastRemove(int index) {// record array structure change modCount++; Int numMoved = size - index -1; 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 }Copy the code

Some points can be seen from the source code:

  1. Null is not verified when adding, and null can be deleted when deleting
  2. Delete all elements usingclear()methods
  3. If index is negative, an exception will be thrown when the array is valued. Less than 0 and greater than size throw different exceptions.
  4. The equals method is used to determine the equality of elements without null. The deletion of elements of a custom type should be mindful of the implementation of equals.

5. Unidirectional iterators

Implement the java.util.Iterator interface class with a few parameters defined in the Iterator:

int cursor; // The position of the next element in the iteration, starting at 0 by default. int lastRet = -1; // The index position of the value returned on the last iteration; The default value is -1. int expectedModCount = modCount; // expectedModCount indicates the expected version number during the iteration; ModCount indicates the actual version number of the array.Copy the code

There are three common iterator methods:

  • hasNextThere are no values to iterate over
  • nextIf there is a value to iterate over, what is the value of the iteration
  • removeDeletes the value of the current iteration

HasNext source

Public Boolean hasNext() {return cursor! Public Boolean hasNext() {return cursor! = size; }Copy the code

Next to the source code

@suppresswarnings ("unchecked") public E next() {// Check whether the version number is the same as expected, and throw an exception if it is modified checkForComodification(); Int I = cursor; If (I >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); // Next iteration, element position cursor = I + 1; return (E) elementData[lastRet = i]; } final void checkForComodification() {if (modCount! = expectedModCount) throw new ConcurrentModificationException(); }Copy the code

In the source code, Next does two things. First, it determines whether the iteration can continue, and second, it finds the values to iterate on and prepares for the next iteration.

An interesting point here is that after determining whether the version number and I have exceeded the number of elements, another judgment is made that it is a concurrent change. Create a local variable that points to the array elementData of the ArrayList. At this point elementData if you change the address has no impact on the value. And then we’re going to see if I is larger than the length of the array, just to make sure that the code is working properly and we can value it, but if you have multiple threads, it’s not necessarily the right value.

Remove the source code

public void remove() { if (lastRet < 0) throw new IllegalStateException(); // Check whether the array has been modified checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; LastRet = -1; lastRet = -1; // Delete the element and modify the modCount, you need to copy the expectedModCount = modCount to the expectedModCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}Copy the code

Here are two things to note:

  • lastRet = -1Is used to prevent deduplication
  • When the element is successfully deleted, the modCount of the array will change, and you need to synchronize the value of expectedModCount.

Bidirectional iterators

In addition to the implementation of the Java.util.Iterator interface class, ArrayList also has a bidirectional Iterator implementation, which inherits the Iterator interface class and implements the java.util.ListIterator interface. Therefore, several reverse iteration methods are added:

  • hasPreviousThere are no previous values to iterate over, the implementation code is similarhasNext
  • nextIndexThe position of the next iteration in a forward iteration
  • previousIndexIn reverse iteration, the position of the next iteration
  • previousIn reverse iteration, the value of the next iteration is implemented similarlynext
  • set(E e)Modifies the element at the current iteration location
  • add(E e)Adds an element at the current iteration location

A bidirectional iterator can be obtained directly by calling listIterator(), which starts at 0 by default. The other is to specify the starting position of the iterator by calling the listIterator(int index) method

public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } public void set(E E) {if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} public void add(E E) {checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}Copy the code

Thread safe

ArrayList is thread-unsafe because the ArrayList’s own elementData, size, and modConut are not locked for various operations.

Other problems

1. Why do we introduce modCount?

The modCount variable is introduced to determine whether a concurrent operation changes the data when traversing the collection. It is used in the fast failure principle.

2. Why add 10 when adding data, but not when initializing?

To save space, sometimes it’s initialized and then it’s assigned to a different list

3. Why is elementData transient modified?

Because not all elements in elementData have data, some elements in elementData are empty due to capacity issues, which is not necessary to serialize. The serialization and deserialization of the ArrayList depend on the writeObject and readObject methods. You can avoid serializing empty elements.

4,new ArrayList(0) 和 new ArrayList(1)The implementation of the

NewCapacity = oldCapacity + (oldCapacity >> 1) newCapacity = oldCapacity + (oldCapacity >> 1); NewCapacity = size + 1 based on the number of actual elements. New ArrayList(0) has a capacity of 1 after the first element is added.

In the same way, when new ArrayList(1) adds two elements, it expands the new capacity to 1, which does not meet the minimum capacity requirement. In this case, it expands the capacity to the minimum capacity requirement.

5, ArrayList contains integer elements. If you call remove, do you want to remove the elements?

When an element is added to a collection as a number, the added element is automatically boxed to an Integer type. When we delete an element, if we pass the argument directly, it will be treated as an index.

ArrayList list = new ArrayList(0); list.add(1); list.add(3); list.remove(3); // Output: class java.lang.integer System.out.println(list.get(0).getClass()); / / throw an exception: IndexOutOfBoundsException list. Remove (3); List.remove (new Integer(3));Copy the code

6, Java fast failure and security failure

Fail fast (fail — fast)

When using iterators iterate over a collection object, if the traversal process to modify the contents of the collection objects (add, delete, modify), will throw ConcurrentModificationException

Principle: The iterator accesses the contents of the collection directly during traversal, and determines whether modCount and expectedmodCount are equal during traversal. The iteration is only done if the two are equal. If the contents of the collection change while it is being traversed, it will change the modCount value, which will cause the two to be unequal, and an exception will be thrown to terminate the traversal

Note: As you can see from the source code, a lot of judgment has been made, but thread safety is not guaranteed. If the modCount value is changed just after the determination, and the length of elementData meets the criteria, the iteration will work fine. Therefore, programming that operates concurrently cannot rely on whether or not this exception is thrown; this exception is recommended only for detecting concurrent modification bugs.

Scenario: The collection classes under the java.util package are fast failing and cannot be modified concurrently in multiple threads (being modified during iteration).

Fail-safe: Yuanmaa

The collection container with the security failure mechanism does not access the contents of the collection directly during the traversal, but copies the original contents of the collection first and traverses the copied collection.

So in the process of traversing the changes to the original collection and cannot be detected by the iterator, so will not trigger a ConcurrentModificationException.

Scenario: Containers under the java.util.concurrent package are all security failures and can be used and modified concurrently with multiple threads.

7. Why is ArrayList expanding 1.5 times?

A value between 1 and 2 is recommended.

Assuming the expansion parameter is x, when x >= 2, the new size of each expansion must be just larger than the sum of the previously allocated


c ⋅ ( 1 + x + x 2 + … + x n – 2 ) Or less c ⋅ x n C ⋅ (+ x / + x ^ 2 +… + x ^ {n – 2}) or less c ⋅ x ^ n

In other words, none of the previous memory space can be reused.

IF x = 2: caps: 1 2 4 August 16 and 32-1 12, 1234, 12345678, 123456789012345, 12345678901234567890123456789012 IF x = 1.5: caps: 1, 2, 3, 4, 6, 9, 13, 19 and 12, 123, 1234, 123456-1 123456789 1234567890123 1234567890123456789 1234567890123456789012345678Copy the code

As you can see, k = 1.5 can reuse the previous memory space after several expansions.