It’s true that ArrayList is the most common data structure used by Java programmers, and it’s used a lot to take arguments and wrap data around them, but we, because it’s so easy to use, don’t seem to care much about the underlying implementation of ArrayList, Today we’ll take a look at the source code for ArrayList and take a look at the underlying principles of ArrayList in a familiar interview format.
Interviewer: What scenarios do you normally use ArrayList for? Why?
Me: We generally use it when accepting data of collection type in development, such as front-end parameters, return values of Dao layer, and carrying data of collection type in business processing. Because it is characterized by order and query speed, so it is used frequently.
- Do you know why its query efficiency is so fast?
Me: Because ArrayList is a dynamic array implementation at its base, we can locate elements using array index subscripts
- Well, tell us about the ArrayList data structure in JDK1.8 and how it adds elements
I: In JDK1.8, ArrayList provides three constructors. The constructor with no arguments points to an empty array by default. The constructor with arguments can set an array of a specified capacity. When you add an element, you check the size of the element array and expand it if it is insufficient. If it is sufficient, you add an element to the end of the array and set size++.
- If I create an ArrayList with a given capacity of 20, will it have a capacity of 20 after initialization?
Me: Well, yes, if the initial capacity is specified when it is constructed then it will have an array length of 20 when it is initialized, except that its size is 0
// With the parameter construction, custom capacity
public ArrayList(int initialCapacity) {
// If the specified capacity is greater than 0, the array is initialized
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// If the specified capacity is 0, the array defaults to an empty array object, otherwise an exception is thrown
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}/** * Constructs an empty list with an initial capacity of ten. */
// An empty array is referenced by default
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeOf course, there is also a parametrized construct:
// Construct the incoming collection
public ArrayList(Collection<? extends E> c) {
// Iterates the collection to an array output
elementData = c.toArray();
// Reference an empty array object if the capacity is empty
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// Array type mismatch occurs in toArray(), when the actual number of elements is greater than the expected number, the iteration produces a new array
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the code- So why don’t you tell me how ArrayList expanded
It first calculates the minimum size of the array and then calls grow(int minCapacity) to expand it
// Calculate the minimum required capacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// If the current array is empty, determine the value of size+1 (minCapacity and default initial capacity 10)
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// This method is called when an element is added to calculate the minimum capacity
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
// The number of changes in the set
modCount++;
// If the current array is not large enough to hold the smallest element, expand it
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeLet’s take a look at the grow(int minCapacity) method, which turns out to be the core of ArrayList expansion
// Capacity expansion mechanism, passing in the minimum capacity currently required
private void grow(int minCapacity) {
// overflow-conscious code
// The length of the array before expansion
int oldCapacity = elementData.length;
// The new array length = the old array length + the old array length /2 = oldCapacity*1.5 (the new array length is 1.5 times the old array length)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the new array length is less than the minimum size, the new array length = the minimum size
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the length of the new array is greater than the int range, the maximum value of int is returned
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// Copy a new array, point to the original array, complete the expansion
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code- It’s not just an ArrayList, it’s any collection, why do you have a modCount in the add or remove method, what is it for
Me: modCount is a variable in ArrayList’s abstract parent, AbstractList, that records the number of times the collection mechanism has been modified. The explanations in the source document is when it is used to set the iteration traversal judge set change state, if found in the process of traversing modCount changed, will be thrown ConcurrentModificationExceptions
- Well, that’s good. So let’s talk a little bit more about deleting elements from an ArrayList
// Remove the element at the specified position
public E remove(int index) {
// Check if index is out of bounds
rangeCheck(index);
// The number of changes to the set
modCount++;
// Get and return old data for this location
E oldValue = elementData(index);
NumMoved >0; numMoved=0; numMoved=0
int numMoved = size - index - 1;
if (numMoved > 0)
// Copy the elements following index to the array object
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Set the end of the array to null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Copy the codeAdd (int,E) copies a new array, so add appends the new array to the index and points to the original array. Remove appends the new array to index and sets the end of the array to NULL.
- Well, do you know why the collection class implements the Serializable interface but redefines the serialization method itself?
I: finished, return to wait for a notice, on the spot get box meal.
Not only is ArrayList a transient keyword for an array of Elements that holds data, but many other collections do the same. Transient variable semantics are ignored for serialization, so why do collection classes do this? There’s a lot of talk online about issues with virtual machine versions and platforms, as well as capacity waste. Because the collection class has expansion mechanism, and after each expansion, the capacity is much larger than before, and under normal circumstances, the capacity is insufficient, which also means that a large amount of memory space is wasted, and the serialization method is to convert program objects into transferable binary files or data, so that the smaller the volume is better.
Note: A clone of an ArrayList is a shallow clone that copies the original array
Instead of nulling the Element array, the clear() method sets each element in the array to null
// Empty the elements. Instead of setting the array to NULL, set each element in the array to NULL
public void clear(a) {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the code