This article analyzes the source code of ArrayList. Let me talk about arrays before analyzing them. Arrays may be one of the first data structures we came into contact with. They divide a continuous address space in memory to store elements. Since it directly operates memory, the performance of arrays is better than that of collection classes, which is a major advantage of using arrays. But we know that the array has a fatal flaw, that is, the array size must be specified during initialization, and the size of the array cannot be changed in subsequent operations. In actual situations, we encounter more things that we don’t know how many elements to be stored at the beginning, but instead hope that the container can automatically expand its own capacity so that it can store more elements. ArrayList can meet such needs very well, and it can automatically expand the size to adapt to the continuous increase of storage elements. Its underlying layer is implemented based on arrays, so it has some features of arrays, such as finding modifications are fast and insertion and deletion are slow. In this article, we will go deep into the source code to see how it encapsulates arrays. First look at its member variables and the three main constructors.
//Default initialization capacity private static final int DEFAULT_CAPACITY = 10;//Empty object array private static final Object[] EMPTY_ELEMENTDATA = {};//Object array private transient Object[] elementData;//Number of collection elements private int size;//Constructor method for passing in initial capacity public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } // Create a new Object type array of the specified capacity this.elementData = new Object[initialCapacity];}//Constructor without parameters public ArrayList() { super(); //Pass an empty array instance to elementData this.elementData = EMPTY_ELEMENTDATA;}//Constructor method to pass into external collection public ArrayList(Collection<? extends E> c) { //Hold the reference element of the internal array passed into collection elementData = c.toArray(); //Update the number of elements of the collection size = elementData.length; //Judge the array type of reference and convert the reference to an Object array reference if (elementData.getClass() != Object[].class) { elementData = Arrays.copyOf(elementData, size, Object[].class); }}You can see that the internal storage structure of ArrayList is an array of Object type, so it can store elements of any type. When constructing an ArrayList, if the initial size is passed in, it will create a new Object array of specified capacity. If the initial size is not set, it will not allocate memory space but use an empty object array, and then allocate memory when the element is actually to be placed. Let’s take a look at its methods of adding, deleting, modifying and searching.
//Increase (add) public boolean add(E e) { //Check whether the array needs to be expanded before adding, the minimum array length is size+1 ensureCapacityInternal(size + 1); //Add element to the end of the array elementData[size++] = e; return true;}//Increase (insert) public void add(int index, E element) { //Insert position range check rangeCheckForAdd(index); //Check whether the capacity needs to be expanded ensureCapacityInternal(size + 1); //Move the element behind the insertion position System.arraycopy(elementData, index, elementData, index + 1, size - index); //Assign a new value elementData[index] = element; size++;}//Delete public E remove(int index) { //Index cannot be greater than size rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) { //Move the element behind index forward by one System.arraycopy(elementData, index+1, elementData, index, numMoved); } //Empty reference elementData[--size] = null; return oldValue;}//Change public E set(int index, E element) { //index cannot be greater than size rangeCheck(index); E oldValue = elementData(index); //Replace with a new element elementData[index] = element; return oldValue;}//Check public E get(int index) { //index cannot be greater than size rangeCheck(index); //Return the specified position element return elementData(index);} Each time an element is added to the collection, it will first check whether the capacity is sufficient, otherwise the capacity will be expanded. The details of capacity expansion will be discussed below. Let’s first look at the specific points to pay attention to when adding, deleting, modifying and checking.
Add (add): Just add this element to the end. Quick operation.
Add (insert): The operation is slower because the element behind the insertion position needs to be moved and the copying of the array is involved.
Delete: Since the elements behind the deletion position need to be moved forward, the array copy will also be designed, so the operation is slow.
Change: directly modify the elements at the specified location, without involving element movement or array copying, and the operation is fast.
Check: Directly return the array element of the specified subscript, and the operation is fast.
From the source code, it can be seen that since searching and modification are directly positioned to the array subscript, it does not involve element movement and array copying, so it is faster. However, because the elements need to be moved, it involves array copying, so the operation is slower. In addition, each addition operation may also perform array expansion, which will also affect performance. Let’s take a look at how ArrayList dynamically expands its capacity.
private void ensureCapacityInternal(int minCapacity) { //If the array is still empty at this time if (elementData == EMPTY_ELEMENTDATA) { //Compare with the default capacity, take the larger value minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //If the array has been initialized, perform this step ensureExplicitCapacity(minCapacity);} private void ensureExplicitCapacity(int minCapacity) { modCount++; //If the minimum capacity is greater than the array length, amplify the array if (minCapacity - elementData.length > 0) { grow(minCapacity); }}//Maximum capacity of the collection private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//Increase the array length private void grow(int minCapacity) { //Get the original capacity of the array int oldCapacity = elementData.length; //Capacity of the new array, add half on the original basis int newCapacity = oldCapacity + (oldCapacity >> 1); //Check whether the new capacity is less than the minimum capacity if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } //Check whether the new capacity exceeds the maximum array capacity if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } //Copy the original array to the new array elementData = Arrays.copyOf(elementData, newCapacity);} Before adding elements, ensureCapacityInternal will be called for collection capacity check. Inside this method, it will check whether the internal array of the current collection is still an empty array. If it is, create a new Object array with the default size of 10. If not, it proves that the current collection has been initialized. Then call ensureExplicitCapacity method to check whether the capacity of the current array meets the minimum required capacity. If it is not satisfied, call the grow method to expand. In the grow method, you can see that each expansion is to increase half of the original array length. Expansion is actually to create a new array with larger capacity, copy all the elements of the original array to the new array, and then discard the original array and use the new array. So far, we have analyzed the more commonly used methods in ArrayList, and some of the key points worth noting:
1. The underlying implementation of ArrayList is based on arrays, so the search and modification of specified subscripts are faster, but the deletion and insertion operations are slower.
2. When constructing an ArrayList, try to specify the capacity as much as possible to reduce the array copy operations caused by expansion. If you do not know the size, you can assign the default capacity to 10.
3. Before adding elements, check whether capacity expansion is required. Each capacity expansion is half of the original capacity.
4. Every time the subscript operation is operated, a security check will be performed. If the array is out of bounds, an exception will be immediately thrown.
5. All methods of ArrayList are not synchronized, so it is not thread safe.
6. The above analysis is based on JDK1.7, and other versions will have some differences, so it cannot be generalized.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.