ArrayList is the most commonly used collection in our development, but many people do not know its source code, resulting in the interview, the interviewer asked a little in-depth questions, can not answer, today we will explore the source of ArrayList.
1. Introduction
- The underlying ArrayList is an array that allows elements to be null and can be dynamically expanded
- Size, isEmpty, get, set, add and other methods all have O (1) time complexity.
- Not thread-safe, concurrent modification, will throw ConcurrentModificationException
2. The initialization
// Initial capacity
private static final int DEFAULT_CAPACITY = 10;
/ / an empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
// Default empty array
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// An array of elements
transient Object[] elementData;
// Initialize with no arguments, default is empty array
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Initialize with parameters to specify the capacity
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** Remember: when an array is initialized with no arguments, it defaults to an empty array and does not initialize its capacity. The capacity is initialized when the element is first added.
3. Add elements
public boolean add(E e) {
// Make sure the array is full. Size is the number of elements
ensureCapacityInternal(size + 1);
// Assign directly
elementData[size++] = e;
return true;
}
// Make sure the array is full
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// Calculate the minimum capacity required
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// If the array is equal to the empty array, the minimum capacity is 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// If the required minimum capacity is greater than the array length, expand it
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeTake a look at the expansion logic:
// Copy the old data into the new array
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// oldCapacity >> 1 divides oldCapacity by 2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the expanded capacity is smaller than the minimum capacity, the expanded capacity equals the minimum capacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the capacity is greater than Integer's maximum value, Integer's maximum value is used
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Expand and assign to the original array
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeYou can see:
- Capacity expansion is 1.5 times the original capacity expansion, not double capacity expansion
- The maximum capacity is the maximum value of Integer
- When adding an element, the element is not checked. It can be null
Let’s take a look at the logic of copying Arrays. Here are all the methods from the Arrays class:
/ * * *@paramOriginal Original array *@paramNewLength New capacity */
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// Create a new array with the new capacity
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// Copy the elements of the original array to the new array
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
Copy the codeFinally, the System class array copy method is called, which is native method:
/ * * *@paramSRC Original array *@paramSrcPos The starting position of the original array *@paramDest target array *@paramDestPos Start position of the target array *@paramLength Indicates the copied length */
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Copy the code4. Delete an element
public boolean remove(Object o) {
// Determine whether the element to be deleted is null
if (o == null) {
// go through the number group
for (int index = 0; index < size; index++)
// Delete the element at the current position if it is equal to the element at the current position
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
// go through the number group
for (int index = 0; index < size; index++)
// Delete the element at the current position if it is equal to the element at the current position
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
// Remove the element at that position
private void fastRemove(int index) {
modCount++;
// Count the number of elements to move
int numMoved = size - index - 1;
if (numMoved > 0)
// Copy from index+1, that is, the following element is moved one place to the left
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// Assign the last element of the array to null to prevent memory leaks
elementData[--size] = null;
}
Copy the codeYou can see if deleting elements, going through the set of numbers, is equal to the target value. If they are equal, all elements following that position are moved one place to the left, and the last element in the array is assigned null.
5. Delete them in batches
// Batch delete the elements that exist in ArrayList and collection C
public boolean removeAll(Collection
c) {
// Non-null check
Objects.requireNonNull(c);
// Batch delete
return batchRemove(c, false);
}
private boolean batchRemove(Collection<? > c,boolean complement){
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
// Move the elements you want to keep to the left
elementData[w++] = elementData[r];
} finally {
// When an exception occurs, it may not be equal
if(r ! = size) {// 1: There may be an exception in the for loop above
// 2: Other threads may have added elements
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// Assign null to elements that do not need to be retained
if(w ! = size) {for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true; }}return modified;
}
Copy the codeUse removeAll() to remove a batch of elements, which is more efficient than using a single for loop.
5. To summarize
This article analyzes ArrayList initialization, PUT, add, remove, dynamic expansion and other methods of the underlying source, I believe we have a deeper understanding of ArrayList, the next piece of learning LinkedList source.