Capacity and expansion mode of ArrayList in Java
- 2021-11-13 01:55:28
- OfStack
View the source code for JDK 1.8 ArrayList
1. The default initial capacity is 10
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
2. Maximum capacity is Integer.MAX_VALUE-8
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Reason: Before referring to others, it needs to be verified:
The array object has 1 additional metadata to represent the size of the array;
The array length size is of int type, with 32 bits and 1 sign bit, so the maximum length is Integer. MAX_VALUE = 2 ^ 31 = 2,147,483,648;
8bytes is used to store size;
3. Expansion method:
(1) First, a desired minimum capacity minCapacity is passed in;
(2) New capacity newCapacity = oldCapacity + (oldCapacity > > 1), that is, the new capacity is equal to 1.5 times of the original capacity;
(3) If minCapacity > newCapacity, newCapacity = minCapacity;
(4) If newCapacity > Maximum capacity MAX_ARRAY_SIZE, newCapacity = hugeCapacity (minCapacity);
(5) Copy original data with new capacity
/**
* 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) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Java ArrayList () Expansion Principle
Usually, ArrayList () is used directly. Today, I will look at the expansion principle of ArrayList ().
First, look at the attributes and construction method of ArrayList, which is more important
Look at the attributes first
// ArrayList Default capacity size
private static final int DEFAULT_CAPACITY = 10;
// 1 Shared empty arrays , Use when the instance is empty
private static final Object[] EMPTY_ELEMENTDATA = {};
// 1 Shared empty arrays , Using the default size Use when an empty instance of
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/*
Storage ArrayList Array buffer of element
Focus 1: ArrayList Is the length of the array buffer
Focus 2: It can also be seen from this element ArrayList() The bottom layer is 1 A Object[]
add No. 1 1 Elements , Any with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA Empty of ArrayList Will be extended to DEFAULT_CAPACITY
*/
transient Object[] elementData;
// ArrayList The size of , What we usually use list.size() This is recorded at the bottom size
private int size;
// ArrayList Maximum
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Look at the constructor again, the constructor with parameters
/*
Parametric constructor , Parameter is capacity size , For example : Initialization 1 Containers are 20 Type is Integer Adj. ArrayList
ArrayList<Integer> list = new ArrayList<>(20);
*/
public ArrayList(int initialCapacity) {
/*
Initialization capacity > 0, elementData To an array of initialized capacity
Initialization capacity = 0, elementData = EMPTY_ELEMENTDATA ( Empty array )
Initialization capacity < 0, Throw an exception directly
*/
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
Constructor with parameter Collection
/*
Will 1 Parameters are Collection Converts the collection of to ArrayList
*/
public ArrayList(Collection<? extends E> c) {
// Collection Convert to an array Object[] Type
elementData = c.toArray();
// Determines whether the current object size is equal to Collection Equal in length and not equal to 0, false Words elementData Is equal to an empty array
if ((size = elementData.length) != 0) {
// c.toArray() May not return correctly 1 A Object[] Array, so use the Arrays.copyOf()
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
Constructor without parameters
/*
Constructors without parameters are just like we usually use 1 Sample , Direct new 1 A ArrayList No parameters need to be passed
Construct method directly sets the elementData Initialized to DEFAULTCAPACITY_EMPTY_ELEMENTDATA ( Empty array )
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Seeing this, we find that we can pass parameters directly to the constructor with parameters, but how does the default constructor initialize the capacity?
The add () method can get the answer directly.
public boolean add(E e) {
// This 1 Line is the key , Look below
ensureCapacityInternal(size + 1);
// Append an element to the end of the collection If the current size = 10 size++ Append to the 11 Bit
elementData[size++] = e;
return true;
}
ensureCapacityInternal () method call
private void ensureCapacityInternal(int minCapacity) {
/*
calculateCapacity() Method , Returns when it is first initialized 10, Other conditions return to the current size + 1
ensureExplicitCapacity() Method , Call expansion
*/
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
/*
Using the parameterless constructor to create ArrayList Collection of , At this time 1 It must be equal
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
/*
Returns the maximum value by comparing two numbers , At this time Math.max(10, 1);
Default capacity , It comes from this
*/
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// If it is not equal, only the current size + 1
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// Increment , Record modification / Number of updates
modCount++;
// Initialization : 10 - 0 > 0
// Others : size + 1 > 0
if (minCapacity - elementData.length > 0)
// Expansion operation
grow(minCapacity);
}
private void grow(int minCapacity) {
// Old length , When initialized 0,
int oldCapacity = elementData.length;
// New length at this time 0 + (0 >> 1), newCapacity = 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
// Initialize the scene : 0 - 10 < 0 ? true newCapacity = 10
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// Initialize the scene : 10 - 2147483639 > 0 Return false
if (newCapacity - MAX_ARRAY_SIZE > 0)
// Very long to execute this method , Must be greater than MAX_ARRAY_SIZE 1 Not at all
newCapacity = hugeCapacity(minCapacity);
// Copy the elements in the original array , And expansion
elementData = Arrays.copyOf(elementData, newCapacity);
}
Look at the initialization scene, and look at other scenes below, which is quite simple
private void ensureCapacityInternal(int minCapacity) {
/*
calculateCapacity() Method , Normal expansion return size + 1, For example 10 + 1, Because the default length is 10 When you add data again, you will start to expand
ensureExplicitCapacity() Method , Call expansion
*/
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
/*
elementData Not equal to an empty array
Returns the current size + 1, I.e. 10 + 1 Return 11
*/
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// Increment , Record modification / Number of updates
modCount++;
// Others : 11 - 10 > 0 true, Triggered expansion , If the current table below is 5 Words 5 + 1 =6, 6 < 10 Yes , There will be no expansion at this time
if (minCapacity - elementData.length > 0)
// Expansion operation
grow(minCapacity);
}
private void grow(int minCapacity) {
// Old length 10
int oldCapacity = elementData.length;
// New length at this time 10 + (10 >> 1), newCapacity = 15
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 15 - 11 < 0 ? false
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 15 - 2147483639 > 0 Return false
if (newCapacity - MAX_ARRAY_SIZE > 0)
// Very long to execute this method , Must be greater than MAX_ARRAY_SIZE 1 Not at all
newCapacity = hugeCapacity(minCapacity);
// Copy the elements in the original array , And expansion newCapacity = 15
elementData = Arrays.copyOf(elementData, newCapacity);
}
Conclusion
1. The key to triggering expansion is
Whether the current size + 1 is larger than the current capacity, if it is larger than the capacity, it proves that the set is not enough and needs to be expanded. If it is small and the current capacity, it proves that the collection still has capacity and does not need to be expanded!
2. The size of each expansion is
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
0
Namely: 1.5 times the current capacity!