ArrayList profile
At the bottom of an ArrayList is an array queue, the equivalent of a dynamic array. Compared to arrays in Java, its size can grow dynamically. An application can use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements. This reduces the amount of incremental redistribution.
ArrayList inherits AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable interfaces.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable{}
Copy the codeRandomAccessIs a flag interface (empty interface) that indicates that the List collection that implements this interface is supportedFast random access. inArrayListIn, we can get the element object quickly by the ordinal of the element, which is fast random access. (The reason: the bottom layer uses an Object[] array to store data.)ArrayListTo achieve theCloneableinterface, that is, the function is overriddenclone()Can be cloned.ArrayListTo achieve thejava.io.SerializableInterface, that meansArrayListSerialization is supported and can be transmitted by serialization.
ArrayList core source code interpretation
JDK1.8 version
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 */
private static final int DEFAULT_CAPACITY = 10;
/** * empty array (for empty instances). * /
private static final Object[] EMPTY_ELEMENTDATA = {};
// A shared empty array instance for default size empty instances.
// We separate it from the EMPTY_ELEMENTDATA array to see how much capacity needs to be increased when the first element is added.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * Hold ArrayList data array */
transient Object[] elementData; // non-private to simplify nested class access
/** * ArrayList contains the number of elements */
private int size;
/** * A constructor with an initial capacity argument (the user can specify the initial size of the collection when creating an ArrayList object) */
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// If the parameter passed is greater than 0, create an array of initialCapacity size
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// If the argument passed is equal to 0, create an empty array
this.elementData = EMPTY_ELEMENTDATA;
} else {
// Otherwise, an exception is thrown
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}/** * Default no parameter constructor *DEFAULTCAPACITY_EMPTY_ELEMENTDATA is 0. I'm going to initialize it to 10, which means I'm going to start with an empty array and then when I add the first element the array becomes 10 */
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/** * Constructs a list of the elements of the specified collection, in the order they are returned by the collection's iterator. * /
public ArrayList(Collection<? extends E> c) {
// Convert 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 (c. toarray may return an array that is not Object)
if(elementData.getClass() ! = Object[].class)// Assign the contents of the elementData array that was not of type Object to the new elementData array of type Object
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// In other cases, use empty arrays instead
this.elementData = EMPTY_ELEMENTDATA; }}/** * Change the capacity of this ArrayList instance to the current size of the list. Applications can use this action to minimize the storage of an ArrayList instance. * /
public void trimToSize(a) {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}// The following is the capacity expansion mechanism of ArrayList
//ArrayList's scaling mechanism improves performance.
// Then frequent inserts will result in frequent copying, which degrades performance, and ArrayList's capacity expansion mechanism avoids this.
/** * If necessary, increase the capacity of this ArrayList instance to ensure that it can hold at least the number of elements *@paramMinCapacity Minimum capacity required */
public void ensureCapacity(int minCapacity) {
// If true,minExpand is 0, if false,minExpand is 10
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 the minimum capacity is greater than the existing maximum capacity
if(minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}// Get the minimum expansion capacity
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Get the maximum value between Default capacity and incoming parameter
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// Determine 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
grow(minCapacity);
}
/** * The maximum array size to allocate */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * ArrayList core method of expansion. * /
private void grow(int minCapacity) {
// oldCapacity indicates the oldCapacity and newCapacity indicates the newCapacity
int oldCapacity = elementData.length;
// Move oldCapacity one bit to the right, which is equivalent to oldCapacity /2,
// We know that bitwise operations are much faster than divisible operations. The result of the whole expression is to update the new capacity to 1.5 times 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 smaller than the minimum required capacity, consider the minimum required capacity as the new capacity of the array.
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// Check if the new capacity exceeds the maximum capacity defined by ArrayList,
// Call hugeCapacity() to compare minCapacity with MAX_ARRAY_SIZE,
// If minCapacity is greater than MAX_ARRAY_SIZE, the new capacity is interger.max_value; otherwise, the new capacity 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 with 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(a) {
return size;
}
/** * Returns true if this list contains no elements. * /
public boolean isEmpty(a) {
// Note the difference between = and ==
return size == 0;
}
/** * Returns true if this list contains the specified element. * /
public boolean contains(Object o) {
//indexOf() method: returns the indexOf the first occurrence of the specified element in the list, or -1 if the list does not contain the element
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 the 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()
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 contains no elements. . * /
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(a) {
try{ ArrayList<? > v = (ArrayList<? >)super.clone();
//Arrays. CopyOf implements array copying and returns the copied array. The arguments are the array to be copied and the length to be copied
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// This shouldn't happen, because we can clone
throw newInternalError(e); }}/** * returns an array containing all the elements in this list in the correct order (from first to last). * The returned array will be "safe" because the list does not retain a reference to it. In other words, the method must allocate a new array. * Therefore, the caller is free to modify the returned array. This approach acts as a bridge between array-based and collection-based apis. * /
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/** * Returns an array containing all elements of this list (from the first to the last) in the correct order; * The runtime type of the returned array is the runtime type of the specified array. Returns the list if it fits the specified array. * 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, the remaining space (that is, the array has more lists than this element) is set to NULL for the elements in the array immediately after the end of the collection. * (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 run-time type, but ArrayList the contents of the 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 position in this list. * /
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/** * replaces the element at the specified position in this list with the specified element. * /
public E set(int index, E element) {
// Perform a bounds check on index
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
// Return the element in the original position
return oldValue;
}
/** * appends the specified element to the end of the list. * /
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
// You can see that adding elements to an ArrayList is essentially an assignment to an array
elementData[size++] = e;
return true;
}
/** * Inserts the specified element at the specified position in this list. * Call rangeCheckForAdd to check the bounds of the index; Then call the ensureCapacityInternal method to ensure that capacity is large enough; * Move all members from index back one place; Insert element into index; And then finally size plus 1. * /
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
Arraycopy () arrayCopy () arrayCopy () arrayCopy () arrayCopy (
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/** * Removes the element at the specified position in the list. Move any subsequent element to the left (subtracting an 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
// The element removed from the list
return oldValue;
}
/** * Removes the first occurrence (if present) of the specified element from the list. If the list does not contain the element, it does 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(a) {
modCount++;
// Set all elements of the array to null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/** * appends all elements of the specified collection to the end of this list in the order returned by the specified collection's Iterator. * /
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;
returnnumNew ! =0;
}
/** * inserts all elements from 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;
returnnumNew ! =0;
}
/** * Remove all elements with indexes between fromIndex (inclusive) and toIndex from this list. * Move any subsequent elements to the left (reduce their 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));
}
/** * A version of rangeCheck used by add and addAll */
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/ * * * * / return IndexOutOfBoundsException details information
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);
}
/** * Only the elements in this list that are contained in the specified collection are retained. * 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 list iterators for the elements in the list, in correct order, starting at the specified position in the list. * The specified index indicates that the first element returned by the initial call will be next. The initial call to previous returns the element of 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(a) {
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(a) {
return new Itr();
}
Copy the codeArrayList Capacity expansion mechanism analysis
The constructor
There are three ways to initialize an ArrayList. The constructor is as follows:
/** * Default initial capacity */
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * The default constructor constructs an empty list with an initial capacity of 10 (no arguments) */
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/** * a constructor that takes an initial capacity argument. (User specified capacity) */
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {// Initial capacity is greater than 0
// Create an array of initialCapacity size
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// Initial capacity equals 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); }}Throws NullPointerException if the specified collection is null. /** * Constructs a list of specified collection elements that return sequentially using the iterators of the collection. * /
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
// Default initial capacity
private static final int DEFAULT_CAPACITY = 10;
// Empty arrays (for empty instances).
private static final Object[] EMPTY_ELEMENTDATA = {};
// A shared empty array instance for default size empty instances.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// Hold an array of ArrayList data
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList contains the number of elements
private int size;
// The default constructor constructs an empty list with an initial capacity of 10 (no arguments)
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeWhen you create an ArrayList with the no-argument constructor, you actually initialize an assignment to an empty array.
So when do you actually allocate capacity? The answer is when you add the first element
add()
/** * appends the specified element to the end of the list. * /
public boolean add(E e) {
// Call the ensureCapacityInternal method before adding elements
ensureCapacityInternal(size + 1); // Increments modCount!!
// You can see that adding elements to an ArrayList is essentially an assignment to an array
elementData[size++] = e;
return true;
}
Copy the codeAdd () appends the specified element to the end, and we can see that this method first calls ensureCapacityInternal(size + 1); The size + 1 = 0 + 1 = 1.
ensureCapacityInternal()
The result of this method is to obtain the minimum expansion capacityminCapacity
// Get the minimum expanded capacity minCapacity
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the codeEnsureExplicitCapacity (calculateCapacity(elementData, minCapacity)) is called in this method;
calculateCapacity()
Let’s start with the calculateCapacity method, which counts capacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
Copy the codeElementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA This. So the condition is true.
return Math.max(DEFAULT_CAPACITY, minCapacity); Compare the two values for the maximum value. The value of DEFAULT_CAPACITY is 10, and minCapacity is the transmitted value. The first value is size+1=0+1=1. So the maximum is 10. Back to 10.
ensureExplicitCapacity()
At this point, we’ll look at the ensureExplicitCapacity method called in the add method, which determines whether the capacity needs to be expanded
// Determine 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
grow(minCapacity);
}
Copy the codeMincapacity-elementdata. length >0. If mincapacity-elementData. length >0, then the length of the data is still 0.
- When we add the first element to the ArrayList, elementData.length is 0 (because it’s still an empty list), because it’s executed
ensureCapacityInternal()Method, so minCapacity is now 10. At this point,minCapacity - elementData.length > 0True, so it’s going to entergrow(minCapacity)Methods. - When the second element is added, minCapacity is 2, and e lementData.length is increased to 10 after the first element is added. At this point,
minCapacity - elementData.length > 0Not true, so will not enter (execute)grow(minCapacity)Methods. - When elements 3, 4, and 10 are added, the grow method is still not executed, and the array size is 10.
Until the 11th element is added, minCapacity(11) is larger than elementData.length (10). Enter the grow method to expand capacity.
When we add the first element, and the 11th element, we are able to expand.
grow()
The maximum array size to allocate
When the first element is added:
-
int oldCapacity = elementData.length;oldCapacity=0; -
int newCapacity = oldCapacity + (oldCapacity >> 1);newCapacity = 0 + 0/2 = 0;**newCapacity represents the size of the new array. >>1 to the right is equal to dividing by 2, plus half the size of the original array. For example, 10+10/2 = 15, 33+33/2=49. If you have an odd number you lose the decimal.
-
If newcapacity-mincapacity <0, newCapacity = minCapacity; if newcapacity-mincapacity <0, newCapacity = minCapacity; if newcapacity-mincapacity <0, newCapacity = minCapacity; In this case, newCapacity is 10
-
NewCapacity – MAX_ARRAY_SIZE > 0 Private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE – 8; This number, 2.1 billion, is smaller than him. Do not meet.
-
elementData = Arrays.copyOf(elementData, newCapacity); Copy copies the original array with newCapacity (10). At this point, our ArrayList finally has capacity. The default is 10
At this point you can finally go back to the add method and execute the code elementData[size++] = e; ElemetnData has a length of 10 and size is 0. Add element elementData[0] and size+1=1. Returns true.
When the 11th element is added:
int oldCapacity = elementData.length;For tenint newCapacity = oldCapacity + (oldCapacity >> 1);10 + 10/2 = 15- All discrepant
elementData = Arrays.copyOf(elementData, newCapacity);Copy the original array and expand it to 15.
/** * The maximum array size to allocate */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** * ArrayList core method of expansion. * /
private void grow(int minCapacity) {
// oldCapacity indicates the oldCapacity and newCapacity indicates the newCapacity
int oldCapacity = elementData.length;
// Move oldCapacity one bit to the right, which is equivalent to oldCapacity /2,
// We know that bitwise operations are much faster than divisible operations. The result of the whole expression is to update the new capacity to 1.5 times 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 smaller than the minimum required capacity, consider the minimum required capacity as the new capacity of the array.
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the new capacity is larger than MAX_ARRAY_SIZE, enter the 'hugeCapacity()' method to compare minCapacity with MAX_ARRAY_SIZE,
// If minCapacity is greater than the maximum capacity, the new capacity is' integer. MAX_VALUE '; otherwise, the new capacity is MAX_ARRAY_SIZE (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);
}
Copy the codehugeCapacity()
Grow (); If the new capacity is greater than MAX_ARRAY_SIZE, enter the hugeCapacity() method to compare minCapacity with MAX_ARRAY_SIZE. If minCapacity is greater than the maximum capacity, The new capacity is integer. MAX_VALUE; otherwise, the new capacity is MAX_ARRAY_SIZE (integer.max_value – 8).
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// Compare minCapacity with MAX_ARRAY_SIZE
// If minCapacity is large, use integer. MAX_VALUE as the size of the new array
// If MAX_ARRAY_SIZE is large, use 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;
}
Copy the codeSystem. Arraycopy (), and Arrays. CopyOf ()
If you read the source code, you’ll see that ArrayList calls both methods a lot. For example, we used this method in the capacity expansion operations and add(int index, E element), toArray() and so on!
Looking at the source code of both, you can see that copyOf() actually calls the System.arrayCopy () method inside
Arraycopy () takes the target array, copies the original array into your own defined array or the original array, and can choose the starting point and the length of the copy and where to put it in the new array. CopyOf () automatically creates a new array internally and returns the array.
conclusion
When we use the default constructor to instantiate an ArrayList, the array size is increased to 10 after some judgment.
ArrayList instantiated with the default constructor triggers expansion only on the first and 11th addition of elements. That is, the first time, and add when the array capacity is exceeded.
Initialization specifies that the ArrayList created by the instantiation will be expanded only when the array capacity is added. Expand to about 1.5 times (odd and even)
ensureCapacitymethods
There’s a method called ensureCapacity in the source code for ArrayList that I don’t know if you’ve noticed, but it’s not called from the inside of ArrayList, so it’s obviously provided for the user to call, so what does this method do?
/** If necessary, increase the capacity of this ArrayList instance to ensure that it can hold at least the number of elements specified by the minimum Capacity parameter. * *@paramMinCapacity Minimum capacity required */
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 codeIt is best used before adding a large number of elementsensureCapacityMethod to reduce the number of incremental reallocations
Let’s actually test the effect of this method with 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("Before using the Recapacity method:"+(endTime - startTime)); }}Copy the codeRunning results:
Before using the Recapacity method: 2158Copy the codepublic 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("Using the Enrecapacity method:"+(endTime1 - startTime1)); }}Copy the codeRunning results:
Before using the Recapacity method: 1773Copy the codeFrom the results of the run, 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 reallocations.
details
JDK7
Create an array with initial capacity of 10
JDK1.8:ArrayList creates an array of size 0 to start with, and then creates an array of size 10 to start with when the first element is added
What’s the difference between Arraylist and Vector?
www.kylin.show/60919.html
ArrayList是ListThe main implementation class for the underlying useObject[ ]Storage, suitable for frequent search work, thread is not safe;Vector是ListThe old implementation class, used at the bottomObject[ ]Storage, thread-safe. (Low-level synchronized method)
Is Arraylist different from LinkedList?
- Whether to ensure thread safety:
ArrayList和LinkedListThey’re not synchronized, which means they’re not thread-safe; - Underlying data structure:
ArraylistThe bottom layer usesObjectAn array of;LinkedListThe bottom layer usesTwo-way linked listData structures (previously circular lists in JDK1.6, circular lists are removed in JDK1.7. Note the difference between a bidirectional list and a bidirectional cyclic list, as described below!) - Whether insert and delete are affected by element position: ①
ArrayListArray storage is used, so the time complexity of inserting and deleting elements is affected by the location of the elements.For example: executeadd(E e)When it comes to methods,ArrayListThe specified element is appended to the end of the list by default, in which case the time is O(1). But if you want to insert and delete elements at position I (add(int index, E element)The time is O(n-i). Because all the (n-i) elements after the ith and ith elements in the set are moved backwards/forwards by one bit. 2.LinkedListUse linked list storage, so foradd(E e)The time complexity of the method is not affected by the position of the element, approximately O(1), if it is to be at the specified positioniInsert and delete elements ((add(int index, E element)) time complexity is approximatelyo(n))Because you need to move to the specified position before you insert. - Whether fast random access is supported:
LinkedListDoes not support efficient random element access, whileArrayListSupport. Fast random access is the quick retrieval of an element object by its ordinal number (corresponding toget(int index)Methods). - Memory space usage:
ArrayListThe space waste is mainly reflected in the space reserved at the end of the list, whileLinkedListThe space cost is reflected in its each element needs to consume ratioArrayListMore space (because direct successors and direct precursors and data are stored).