Interpretation of the core source code of ArrayList
Feel easy to use little partner, please give me a praise Oh, thank you very much!!!
Most of the content comes from the Internet, and individuals have added additional content to facilitate understanding and memory
1. Basic information of ArrayList
The underlying array of ArrayList is array queue, which is applicable to dynamic array. Compared with arrays in java, the capacity can grow dynamically. Before adding a large number of elements, you can use the ensureCapacity operation to increase the capacity of ArrayList instances, which can reduce the number of incremental redistribution.
ArrayList inherits from AbstractList and implements list, randomaccess, Cloneable, Java io. Serializable these interfaces.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
- RandomAccess is a flag interface, which indicates that the List collection implementing this interface supports fast random access. In ArrayList, we can quickly obtain the element object through the element serial number, which is fast random access.
- ArrayList implements the clonable interface, that is, it overrides the function clone(), which can be cloned. clone().
- ArrayList implements Java io. Serializable interface, which means that ArrayList supports serialization and can transfer objects through serialization.
1.1. What is the difference between ArrayList and Vector?
-
ArrayList is the main implementation class of List. The underlying layer uses Object [] storage, which is suitable for frequent search work, and the thread is unsafe;
-
Vector is an ancient implementation class of List. The underlying layer uses Object [] storage, which is thread safe.
Reasons for thread safety
————>Method is decorated with the synthesized keyword
1.2. What is the difference between ArrayList and LinkedList?
-
Whether thread safety is guaranteed: ArrayList and LinkedList are not synchronized, that is, thread safety is not guaranteed;
-
Underlying data structure: Arraylist uses an Object array at the bottom; The underlying layer of the LinkedList uses a two-way linked list data structure (before JDK1.6, it was a circular linked list, and JDK1.7 cancels the cycle. Note the differences between the two-way linked list and the two-way circular linked list, which are introduced below!)
-
Whether insertion and deletion are affected by element position:
① ArrayList uses array storage, so the time complexity of inserting and deleting elements is affected by the position of elements. For example, when the add (E) method is executed, ArrayList will append the specified element to the end of the list by default. In this case, the time complexity is O(1). However, if you want to insert and delete elements at the specified position I, the time complexity of (add(int index, E element)) is O(n-i). Because when performing the above operations, the (n-i) elements after the I and I elements in the set must perform the operation of moving backward / forward by one bit.
② LinkedList is stored in a linked list, so for the insertion of add (E, e) method, the time complexity of deleting elements is not affected by the element position, which is approximately O(1). If you want to insert and delete elements at the specified position i ((add(int index, E element)) time complexity is approximately o(n)), because you need to move to the specified position before inserting.
-
Whether it supports fast random access: LinkedList does not support efficient random element access, while ArrayList does. Fast random access is to quickly obtain the element object (corresponding to the get(int index) method) through the element serial number.
-
Memory space occupation: the space waste of ArrayList is mainly reflected in that a certain capacity space is reserved at the end of the list, while the space cost of LinkedList is reflected in that each element needs to consume more space than ArrayList (because it needs to store direct successors, direct precursors and data).
Bidirectional linked list
Double linked list is a kind of linked list, which is composed of nodes. There are two pointers in each data node, pointing to the direct successor and direct precursor respectively.
O (1) is a constant
O (n^x) x is related to the number of times of algorithm n
2. Interpretation of ArrayList core source code
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity size
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Empty array (for empty instances).
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
//Shared empty array instance for empty instances of default size.
//We took it from empty_ Element data array to know how much capacity needs to be increased when the first element is added.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* An array that holds ArrayList data
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList Number of elements contained
*/
private int size;
/**
* Constructor with initial capacity parameter (the user can specify the initial size of the collection when creating the ArrayList object)
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//If the passed in parameter is greater than 0, create an array of initialCapacity size
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//If the passed in parameter is equal to 0, an empty array is created
this.elementData = EMPTY_ELEMENTDATA;
} else {
//In other cases, throw an exception
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*Default parameterless constructor
*DEFAULTCAPACITY_EMPTY_ELEMENTDATA Is 0 Initialize to 10, that is, the initial is actually an empty array. When the first element is added, the capacity of the array becomes 10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
*/
public ArrayList(Collection<? extends E> c) {
//Converts the specified collection to an array
elementData = c.toArray();
//If the length of the elementData array is not 0
if ((size = elementData.length) != 0) {
// If elementData is not Object type data (c.toArray may not return an array of Object type, so the following statement is added for judgment)
if (elementData.getClass() != Object[].class)
//Assign the contents of the original elementData array that is not of Object type to the elementData array of new Object type
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// In other cases, use an empty array instead
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* Modify the capacity of this ArrayList instance to be the current size of the list. Applications can use this operation to minimize the storage of ArrayList instances.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//The following is the capacity expansion mechanism of ArrayList
//The capacity expansion mechanism of ArrayList improves the performance. If only one is expanded at a time,
//Then frequent inserts will lead to frequent copies and reduce performance, which is avoided by the capacity expansion mechanism of ArrayList.
/**
* If necessary, increase the capacity of this ArrayList instance to ensure that it can accommodate at least the number of elements
* @param minCapacity Minimum capacity required
*/
public void ensureCapacity(int minCapacity) {
//If true, the value of minExpand is 0. If false, the value of minExpand is 10
int minExpand = (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 the minimum capacity is greater than the existing maximum capacity
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
//1. Get the minimum expansion capacity
//2. Capacity expansion through minimum capacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Gets the maximum value between the default capacity and the incoming parameter
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//Judge whether capacity expansion is required
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//Call the grow method to expand the capacity. Calling this method means that the capacity expansion has started
grow(minCapacity);
}
/**
* Maximum array size to allocate
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList The core method of capacity expansion.
*/
private void grow(int minCapacity) {
// oldCapacity is the old capacity and newCapacity is the new capacity
int oldCapacity = elementData.length;
//Move oldCapacity one bit to the right, which is equivalent to oldCapacity /2,
//We know that bit operation is much faster than division operation. The result of whole sentence operation is to update the new capacity to 1.5 times of the old capacity,
int newCapacity = oldCapacity + (oldCapacity >> 1);
//Then check whether the new capacity is greater than the minimum required capacity. If it is still less than the minimum required capacity, take the minimum required capacity as the new capacity of the array,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//Then check whether the new capacity exceeds the maximum capacity defined by ArrayList,
//If it exceeds, call hugeCapacity() to compare minCapacity with MAX_ARRAY_SIZE，
//If minCapacity is greater than MAX_ARRAY_SIZE, then the new capacity is interger MAX_ Value, otherwise, the new capacity size is MAX_ARRAY_SIZE.
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
//Compare minCapacity and MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
*Returns the number of elements in this list.
*/
public int size() {
return size;
}
/**
* Returns true if the list does not contain elements.
*/
public boolean isEmpty() {
//Note the difference between = and = =
return size == 0;
}
/**
* Returns true if the list contains the specified element.
*/
public boolean contains(Object o) {
//indexOf() method: returns the index of the first occurrence of the specified element in the list. If the list does not contain this element, it is - 1
return indexOf(o) >= 0;
}
/**
*Returns the index of the first occurrence of the specified element in this list, or - 1 if the list does not contain this element
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
//equals() method comparison
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element in this list, or - 1 if the list does not contain an element
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns a shallow copy of this ArrayList instance. (the element itself is not copied.)
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
//Arrays.copyOf function is to copy the array and return the copied array. Parameters are the copied array and the copied length
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// This should not happen because we can clone
throw new InternalError(e);
}
}
/**
*Returns an array containing all the elements in this list in the correct order (from the first to the last element).
*The returned array will be "safe" because the list does not retain a reference to it. In other words, this method must allocate a new array.
*Therefore, the caller is free to modify the returned array. This method acts as a bridge between array based and collection based API s.
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* Return an array containing all the elements in this list in the correct order (from the first to the last element);
*The runtime type of the returned array is the runtime type of the specified array. If the list fits the specified array, it is returned.
*Otherwise, a new array is allocated for the runtime type of the specified array and the size of this list.
*If the list applies to the specified array and the remaining space (i.e. the number of lists in the array is more than this element), the element in the array immediately after the end of the collection is set to null.
*(This determines the length of the list only if the caller knows that the list does not contain any empty elements.)
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Create an array of runtime type, but the contents of ArrayList array
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//Call the arraycopy() method provided by System to copy arrays
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified location in this list.
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* Replaces the element at the specified location in this list with the specified element.
*/
public E set(int index, E element) {
//Perform boundary check on index
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
//Returns the original element at this location
return oldValue;
}
/**
* Appends the specified element to the end of this list.
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//Here, we can see that adding elements to ArrayList is equivalent to assigning values to arrays
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified location in this list.
*First, call rangeCheckForAdd to check the limit of index; Then the ensureCapacityInternal method is called to ensure that capacity is large enough.
*Then move all members after the index back to one position; Insert the element into the index position; Finally, add 1.
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy() is a method to copy arrays. We must take a look. Next, we use the arraycopy() method to copy arrays
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* Delete the element at the specified position in the list. Move any subsequent elements to the left (subtract one element from its index).
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
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
//Elements removed from the list
return oldValue;
}
/**
* Removes the first occurrence (if any) of the specified element from the list. If the list does not contain this element, it will not change.
*Returns true if the list contains the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
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
}
/**
* Removes all elements from the list.
*/
public void clear() {
modCount++;
// Set the values of all elements in the array to null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* Appends all elements in the specified collection to the end of this list in the order returned by the Iterator of the specified collection.
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all elements in the specified collection into this list, starting at the specified location.
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* Remove all elements with indexes between fromIndex and toIndex from this list.
*Move any subsequent element to the left (reduce its index).
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* Checks whether the given index is in range.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* add And addAll use a version of rangeCheck
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Return IndexOutOfBoundsException details
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* Removes all elements contained in the specified collection from this list.
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//Returns true if the list is modified
return batchRemove(c, false);
}
/**
* Keep only the elements in this list that are included in the specified collection.
*In other words, remove all elements from this list that are not included in the specified collection.
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* Returns the list iterator of the elements in the list (in the correct order) starting at the specified position in the list.
*The specified index indicates that the first element returned by the initial call is next. The initial call to previous returns the element with the specified index minus 1.
*The list iterator returned is fail fast.
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
*Returns the list iterators in the list in the appropriate order.
*The list iterator returned is fail fast.
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
*Returns iterators for the elements in the list in the correct order.
*The iterator returned is fail fast.
*/
public Iterator<E> iterator() {
return new Itr();
}
3. Analysis of ArrayList capacity expansion mechanism
3.1. Let's start with the constructor of ArrayList
(JDK8) ArrayList can be initialized in three ways. The source code of the construction method is as follows:
/**
* Default initial capacity size
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*The default constructor uses the initial capacity of 10 to construct an empty list (no parameter construction)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructor with initial capacity parameter. (user specified capacity)
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//Initial capacity greater than 0
//Create an array of initialCapacity sizes
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//Initial capacity equal to 0
//Create an empty array
this.elementData = EMPTY_ELEMENTDATA;
} else {//If the initial capacity is less than 0, an exception is thrown
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
*Constructs a list containing the specified collection elements, which are returned sequentially using the iterator of the collection
*throws NullPointerException if the specified collection is null.
*/
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;
}
}
Careful students will find that when creating an ArrayList with a parameterless construction method, an empty array is actually initialized and assigned. When you really add elements to the array, you can really allocate capacity. That is, when the first element is added to the array, the capacity of the array is expanded to 10. We will talk about this when we analyze the capacity expansion of ArrayList!
3.2. Analyze the capacity expansion mechanism of ArrayList step by step
Here, take the ArrayList created by the parameterless constructor as an example
3.2.1. Let's first look at the add method
/**
* Appends the specified element to the end of this list.
*/
public boolean add(E e) {
//Call the ensureCapacityInternal method before adding an element
ensureCapacityInternal(size + 1); // Increments modCount!!
//Here, we can see that adding elements to ArrayList is equivalent to assigning values to arrays
elementData[size++] = e;
return true;
}
3.2.2. Let's look at the ensureCapacityInternal() method
(JDK7) you can see that the add method first calls ensureCapacityInternal(size + 1)
//Get the minimum expansion capacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Gets the default capacity and the larger value of the passed in parameter
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
When you want to add into the first element, minCapacity is 1, in math After comparison with max() method, minCapacity is 10.
3.2.3. ensureExplicitCapacity() method
If you call the ensureCapacityInternal() method, you will enter (execute) this method. Let's study the source code of this method!
//Judge whether capacity expansion is required
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//Call the grow method to expand the capacity. Calling this method means that the capacity expansion has started
grow(minCapacity);
}
Let's analyze it carefully:
- When we want to add the first element to ArrayList, elementdata The length is 0 (because it is still an empty list). Because the ensureCapacityInternal() method is executed, the minCapacity is 10 at this time. At this point, minCapacity - elementdata If length > 0 is set, it will enter the growth (minCapacity) method.
- When the second element is added, minCapacity is 2, and E lementdata Length (capacity) is expanded to 10 after adding the first element. At this point, minCapacity - elementdata Length > 0 does not hold, so it will not enter (execute) the growth (minCapacity) method. minCapacity here is variable, that is, the input parameter of the add function, that is, size+1
- When adding elements 3, 4... To 10, the grow method will not be executed, and the array capacity is 10.
Until the 11th element is added, minCapacity(11) is better than elementdata The length (10) should be larger. Enter the grow th method for capacity expansion.
3.2.4. grow() method
/**
* Maximum array size to allocate
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList The core method of capacity expansion.
*/
private void grow(int minCapacity) {
// oldCapacity is the old capacity and newCapacity is the new capacity
int oldCapacity = elementData.length;
//Move oldCapacity one bit to the right, which is equivalent to oldCapacity /2,
//We know that bit operation is much faster than division operation. The result of whole sentence operation is to update the new capacity to 1.5 times of the old capacity,
int newCapacity = oldCapacity + (oldCapacity >> 1);
//Then check whether the new capacity is greater than the minimum required capacity. If it is still less than the minimum required capacity, take the minimum required capacity as the new capacity of the array,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the new capacity is greater than MAX_ARRAY_SIZE, enter (execute) ` hugeCapacity() 'method to compare minCapacity and MAX_ARRAY_SIZE，
//If minCapacity is greater than the maximum capacity, the new capacity is ` integer MAX_ Value `, otherwise, the new capacity size is MAX_ARRAY_SIZE is ` integer MAX_ VALUE - 8`.
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Int newcapacity = oldCapacity + (oldCapacity > > 1), so the capacity of ArrayList will become about 1.5 times of the original after each expansion (the even number of oldCapacity is 1.5 times, otherwise it is about 1.5 times)! Parity is different, for example: 10 + 10 / 2 = 15, 33 + 33 / 2 = 49. If it is an odd number, the decimal will be lost
"> >" (shift operator): > > 1 shifting right by one bit is equivalent to dividing by 2, and shifting right by n bits is equivalent to dividing by 2 to the nth power. Here, oldCapacity is obviously shifted by 1 bit to the right, so it is equivalent to oldCapacity /2. For the binary operation of big data, the operation of displacement operator is much faster than those of ordinary operators, because the program only moves once and does not calculate, which improves the efficiency and saves resources
Let's explore the growth () method through an example:
- When the first element is added, the oldCapacity is 0. After comparison, the first if is determined to be true. newCapacity = minCapacity(10). However, the second if judgment will not hold, that is, newCapacity is not better than max_ ARRAY_ If the size is large, the hugeCapacity method will not be entered. The capacity of the array is 10, return true in the add method, and the size is increased to 1.
- When the 11th element of add enters the grow th method, newCapacity is 15, which is larger than minCapacity (11). The first if judgment is not tenable. If the new capacity is not greater than the maximum size of the array, it will not enter the hugeCapacity method. The array capacity is expanded to 15, return true in the add method, and the size is increased to 11.
- And so on······
Here is an important but easily overlooked knowledge:
- The length attribute in java is for arrays. For example, if you declare an array, the length attribute is used to know the length of the array
- The length() method in java is for strings. If you want to see the length of this string, use the length() method
- The size() method in java is for generic collections. If you want to see how many elements there are in this generic, call this method to check!
3.2.5. hugeCapacity() method. Lifting large capacity method
From the source code of the grow() method above, we know that if the new capacity is greater than MAX_ARRAY_SIZE, enter (execute) the hugeCapacity() method to compare minCapacity and MAX_ARRAY_SIZE. If minCapacity is greater than the maximum capacity, the new capacity is integer MAX_ Value, otherwise, the new capacity size is MAX_ARRAY_SIZE is integer MAX_ VALUE - 8.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//For minCapacity and MAX_ARRAY_SIZE for comparison
//If minCapacity is large, integer MAX_ Value as the size of the new array
//If Max_ ARRAY_ If size is large, set MAX_ARRAY_SIZE as the size of the new array
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
3.3. System.arraycopy() and arrays Copyof() method
After reading the source code, we will find that there are a lot of calls to these two methods in ArrayList. For example, this method is used in the capacity expansion operation, add(int index, E element), toArray() and other methods mentioned above!
3.3.1. System.arraycopy() method
Source code:
// We found that arraycopy is a native method. Next, let's explain the specific meaning of each parameter
/**
* Copy array
* @param src Source array
* @param srcPos Start position in source array
* @param dest target array
* @param destPos Start position in destination array
* @param length The number of array elements to copy
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Scenario:
/**
* Inserts the specified element at the specified location in this list.
*First, call rangeCheckForAdd to check the limit of index; Then the ensureCapacityInternal method is called to ensure that capacity is large enough.
*Then move all members after the index back to one position; Insert the element into the index position; Finally, add 1.
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//The arraycopy() method copies the array itself
//elementData: source array; Index: the starting position in the source array; elementData: target array; index + 1: the starting position in the target array; size - index: the number of array elements to copy;
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
Let's write a simple method to test the following:
public class ArraycopyTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[10];
a[0] = 0;
a[1] = 1;
a[2] = 2;
a[3] = 3;
System.arraycopy(a, 2, a, 3, 3);
a[2]=99;
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
result:
0 1 99 2 3 0 0 0 0 0
3.3.2. Arrays.copyOf() method
Source code:
public static int[] copyOf(int[] original, int newLength) {
// Request a new array
int[] copy = new int[newLength];
// Call system Arraycopy, copy the data in the source array and return a new array
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
Scenario:
/**
Return an array containing all the elements in this list in the correct order (from the first to the last element); The runtime type of the returned array is the runtime type of the specified array.
*/
public Object[] toArray() {
//elementData: array to copy; size: length to copy
return Arrays.copyOf(elementData, size);
}
Personally, I think using arrays The copyof() method is mainly used to expand the capacity of the original array. The test code is as follows:
public class ArrayscopyOfTest {
public static void main(String[] args) {
int[] a = new int[3];
a[0] = 0;
a[1] = 1;
a[2] = 2;
int[] b = Arrays.copyOf(a, 10);
System.out.println("b.length"+b.length);
}
}
result:
10
3.3.3. The connection and difference between the two
Contact:
Looking at the source code of both, we can find that copyOf() actually calls system Arraycopy() method
difference:
You can copy the length of the original array and the position of the target array into the original array, and you can choose to copy it into the original array
copyOf() means that the system automatically creates an array internally and returns the array. copyOf() actually calls system Arraycopy() method
3.4. ensureCapacity method
There is an ensureCapacity method in the source code of ArrayList. I don't know if you have noticed. This method has not been called inside ArrayList, so it is obviously provided for users to call. What is the function of this method?
3.4. ensureCapacity method
There is an ensureCapacity method in the source code of ArrayList. I don't know if you have noticed. This method has not been called inside ArrayList, so it is obviously provided for users to call. What is the function of this method?
/**
If necessary, increase the capacity of this ArrayList instance to ensure that it can accommodate at least the number of elements specified by the minimum capacity parameter.
*
* @param minCapacity Minimum capacity required
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (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);
}
}
It is best to use the ensureCapacity method before add ing a large number of elements to reduce the number of incremental reassignments
We actually test the effect of this method through the following code:
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("use ensureCapacity Before method:"+(endTime - startTime));
}
}
Operation results:
use ensureCapacity Before method: 2158
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("use ensureCapacity After method:"+(endTime1 - startTime1));
}
}
Operation results:
use ensureCapacity Method: 1773
Through the running results, we can see that it is best to use the ensureCapacity method before adding a large number of elements to the ArrayList to reduce the number of incremental reassignments.
ayList list = new ArrayList();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("before using the ensureCapacity method:" + (endTime - startTime));
}
}
Operation results: ```text use ensureCapacity Before method: 2158
public class EnsureCapacityTest {
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("use ensureCapacity After method:"+(endTime1 - startTime1));
}
}
Operation results:
use ensureCapacity Method: 1773
Through the running results, we can see that it is best to use the ensureCapacity method before adding a large number of elements to the ArrayList to reduce the number of incremental reassignments.
Feel easy to use little partner, please give me a praise Oh, thank you very much!!!