Java ArrayList expansion problems detailed examples
- 2021-01-18 06:23:56
- OfStack
This paper mainly studies the Java ArrayList expansion problems in detail, the specific introduction is as follows.
The first thing we need to know is that ArrayList is actually an array of type Object, and the size of ArrayList is actually the size of this array of type Object.
transient Object[] elementData;
1. Capacity allocation of ArrayList at creation time
There are three scenarios for creating an ArrayList
1. Default size creation (default is 0)
ArrayList al = new ArrayList();
After creation, al has a capacity of 0. You can see this from the following code.
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2, Specify size creation
ArrayList al = new ArrayList(5);
Create an ArrayList object (size 5), which is an array of Object (length 5).
transient Object[] elementData;
private static final Object[] 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);
}
}
3, Specify the creation of a collection of elements
ArrayList al = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
The ES36en object is created and initialized with 1 ES37en as [1,2,3,4,5]. We create an Object array of length 5. The contents of the array are [1,2,3,4,5]. You can see this from the following code.
private int size;
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
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;
}
}
2. Capacity expansion of ArrayList when inserting elements
ArrayList<Integer> collection = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5));
Integer[] moreInts = { 6, 7, 8, 9, 10 };
collection.addAll(Arrays.asList(moreInts));
The above process is as follows:
Create (ArrayList = 5) create (ArrayList = 5) create (ArrayList = 5) create (ArrayList = 5) -- The initial capacity is 5
2, Add collection {6, 7, 8, 9, 10} to ArrayList object. At this point, we need to expand the ArrayList object capacity.
View the source code:
public Boolean addAll(Collection<? extends E> c) {
// Get the insert array
Object[] a = c.toArray();
// Gets the inserted content length
int numNew = a.length;
ensureCapacityInternal(size + numNew);
// Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
private void ensureCapacityInternal(int minCapacity) {
// if ArrayList The contents are empty
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// Into the 1 Step to calculate the expanded size minCapacity
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// ArrayList Original size of
int oldCapacity = elementData.length;
// Calculates the expanded size based on the original size, which is the size of the element 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// The expanded length is the same as the previous calculation minCapacity Compare, take the larger one as the expanded length
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the expanded length is greater than the maximum length
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// expand
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// minCapacity Less than 0 , indicating overflow, otherwise the maximum integer is taken as the final expansion length
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
The above process can be summarized as follows:
ArrayList + size of set to be inserted numNew = minimum length of minCapacity
2, If the original size of ArrayList is 0, that is, ArrayList is empty, then the expanded minimum length of ArrayList = Math.max(10, minCapacity), that is, the expanded minimum length of minCapacity is not just the original length of size plus the inserted length of numNew.
3. The minimum extended length minCapacity obtained above is not the final expanded length, and it needs to be calculated in one step further.
(1) The original size of ArrayList is oldCapacity
newCapacity = oldCapacity*1.5; newCapacity = oldCapacity*1.5;
(3) Compare the expanded minimum length minCapacity calculated above with the expanded size newCapacity obtained here, and take the larger one as the final expanded size.
conclusion
The above is all the content of this article on ArrayList expansion problems in detail, I hope to help you. Interested friends can continue to refer to the site of other related topics, if there are shortcomings, welcome to leave a message to point out. Thank you for your support!