From: juejin. Cn/post / 684490…

First, ArrayList

concept

Concept: An ArrayList is a dynamic array whose capacity can grow dynamically. But it’s not like an array, and we’ll look at the comparison below. It inherits AbstractList and implements List, RandomAccess, Cloneable, java.io.Serializable.

The RandomAccess interface, when implemented by List, provides List with RandomAccess, that is, the ability to get element objects by subscript.

With Cloneable implemented, java.io.Serializable means it can be cloned and serialized.

The main thing is to look at the part where I circle

The data structure of ArrayList

When analyzing a class, data structure is often the soul of it. To understand the underlying data structure is to understand the implementation of the class, and the specific implementation details will be analyzed in detail.

The data structure of ArrayList is:

Note: The underlying data structure is an array, array element type for Object type, that is, can store all types of data. All of our operations on instances of the ArrayList class are array-based at the bottom.

ArrayList source code analysis

Inheritance structure and hierarchy

Let’s look at the inheritance structure of ArrayList:

- ArrayList extends AbstractList - AbstractList extends AbstractCollection copies codeCopy the code

All classes inherit from Object, so ArrayList’s inheritance structure looks like the one shown above

Ask why AbstractList should be inherited first and AbstractList should be implemented first. Instead of having ArrayList implement List directly?

This is the idea that an interface is full of abstract methods, and an abstract class can have abstract methods and concrete implementation methods. It’s this idea that AbstractList can be used to implement some general methods in an interface, and concrete classes like ArrayList inherit this class. Get some common methods, and then in their own implementation of some unique methods, so that the code is more concise, on the inheritance structure of the bottom class of the common method are extracted, first implemented together, reduce repeated code. So when you see a class with an abstract class on top of it, that’s what it does

RandomAccess this interface

I click into the source code to find it is an empty interface, why is an empty interface

RandomAccess interface is a Marker interface

The ArrayList collection implements this interface to support fast random access

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            returnCollections.iteratorBinarySearch(list, key); } Duplicate codeCopy the code

Looking at the source code, we can see that lists that implement the RandomAccess interface are iterated through using a generic for loop, while those that don’t implement the interface use iterators. Arraylists are faster for iterators than for iterators, linkedLists are faster for iterators than for iterators, so when we’re working on a project, we should take into account that different subclasses of lists can iterate differently to improve performance! How to determine whether the subclass of List received is ArrayList or LinkedList? Then you need to use instanceof to determine if the List subclass implements RandomAccess!

Conclusion: The RandomAccess interface is a skeleton that can be used to better determine whether a collection is an ArrayList or a LinkedList, so that it can better choose a better traversal method and improve performance

Properties in the ArrayList class

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Java.io.Serializable {// Version number private static Final Long serialVersionUID = 8683452581122892189L; Private static final int DEFAULT_CAPACITY = 10; Private static Final Object[] EMPTY_ELEMENTDATA = {}; Private static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; [] elementData; [] elementData; [] elementData; // Actual element size, default is 0 private int size; Private static final Int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; private static final int MAX_ARRAY_SIZE = integer. MAX_VALUE - 8; } Duplicate codeCopy the code

A constructor

No arguments structure

public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } Duplicate codeCopy the code

The size of the ArrayList is empty, but the length of elementData is 1. The first time you add it, the capacity becomes the initial capacity size 10 (default no-parameter construction is 10)

Int parameter construction

   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); }} Copy the codeCopy the code

It’s a little bit easier to check if it’s greater than 0, and if it’s greater than 0 it creates an array of the size that’s passed in, and if it’s 0 it’s empty

Collection parameter constructor

public ArrayList(Collection<? Extends E> c) {extends E> c) {// Specifies the list of elements of the collection in the order they are returned by the iterator of the collection. Copy the elements of the collection into elementData. 2. Update the size value. elementData = c.toArray();if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturn 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 codeCopy the code

Put the elements of the collection back into the new collection, and then update the actual size

The specific methods

The add method

  /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})*/ public Boolean add(E E) {// ensureCapacityInternal(size + 1); // Increments modCount!! // add elements to the end of the array elementData[size++] = e;return true; } Duplicate codeCopy the code

The first step is to expand and the second step is to add an element to the tail and we’ll go down

EnsureCapacityInternal (XXX); Method for determining internal capacity

private void ensureCapacityInternal(int minCapacity) {
        if(elementData == EMPTY_ELEMENTDATA) {// minCapacity=size+1; So we changed minCapacity to 10, which is the default size, but we haven't really initialized the size of elementData yet. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); EnsureExplicitCapacity (minCapacity); } Duplicate codeCopy the code

EnsureExplicitCapacity (XXX);

private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code //minCapacity If minCapacity is larger than the actual length of elementData, then the length of elementData array is insufficient, so increase the length of elementData. MinCapacity =size+1 when elementData is initialized as an empty array; minCapacity=size+1 when elementData is initialized as an empty array. So minCapacity=1, in the previous method (ensureCapacityInternal) it would have found an empty array, and it would have given &emsp; &emsp; Set minCapacity to 10. At this point, you have not changed the size of elementData. &emsp; MinCapacity =size+1; elementData is not an empty array. MinCapacity represents the actual amount of data added to elementData. Use it to determine whether the length of elementData is sufficient. If the length is insufficient, you must expand the capacity or the added element will overflow. * /if(minCapacity -elementdata.length > 0) //arrayList can automatically expand the size of the key method grow(minCapacity); } Duplicate codeCopy the code

grow(xxx); The method at the heart of arrayList is the real secret to expanding the size of arrays.

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // add the elementData size to oldCapacity int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity is 1.5 times oldCapacityif(newCapacity -mincapacity < 0) {length=0, oldCapacity=0, newCapacity=0; This is where you actually initialize the size of elementData, which is 10. The work ahead is all preparatory work. newCapacity = minCapacity;if(newCapacity -max_array_size > 0)// If newCapacity exceeds the maximum capacity limit, call hugeCapacity, NewCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } Duplicate codeCopy the code

HugeCapacity ();

// This is the method used above, very simple, is to assign the maximum value. private static int hugeCapacity(int minCapacity) {if(minCapacity < 0) // overflow throw new OutOfMemoryError(); // If minCapacity is greater than MAX_ARRAY_SIZE, integer. MAX_VALUE is returned; otherwise, MAX_ARRAY_SIZE is returned. Because maxCapacity is three times of minCapacity, the expansion may be too large, so we can use minCapacity to judge. // integer. MAX_VALUE:2147483647 MAX_ARRAY_SIZE: 2147483639 It still exceeds this limit and it's going to overflow. Arraylist provides two layers of protection.return(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } Duplicate codeCopy the code

Summarize the expansion process

  • 1. Determine whether the capacity needs to be expanded. If yes, calculate the minimum capacity to be expanded
  • 2. If capacity expansion is required, run grow(int minCapacity). MinCapacity is the minimum required capacity
  • 3. Capacity expansion for the first time is 1.5 times the original capacity
  • 4 If the capacity is still smaller than minCapacity after the first expansion, expand the capacity to minCapacity
  • 5. Finally, if minCapacity is greater than the maximum capacity, expand the capacity to the maximum capacity

The add (int, E) method

Public void add(int index, E element) {// Insert the array position check rangeCheckForAdd(index); EnsureCapacityInternal (size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); ElementData [index] = element; // insert the element size++ at the desired position; // The array must be inserted between 0 and the last element, otherwise an error is reported // Because the array is contiguous space, Private void rangeCheckForAdd(int index) {if(index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } Duplicate codeCopy the code

And that’s not too hard to do because we already implemented arrays

The get method

Public E get(int index) {// Check rangeCheck(index); // Returns result data if it passes the check, otherwise throws an exception.returnelementData(index); } private void rangeCheck(int index) {private void rangeCheck(int index) {if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    
        @SuppressWarnings("unchecked")
    E elementData(int index) {
        return(E) elementData[index]; } Duplicate codeCopy the code

Check the array out of bounds, and then you just go to the array and get the data and return it

set(int index, E element)

// Replaces the index element public Eset(int index, E element) {// Index out of bounds check rangeCheck(index); E oldValue = elementData(index); elementData[index] = element;returnoldValue; } Duplicate codeCopy the code

This is the element that replaces the specified position

Remove (int) : Removes an element from a specified position

Public E remove(int index) {// Check rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index - 1; int numMoved = size-index - 1;if(numMoved > 0) add(int, E) System. Arraycopy (elementData, index+1, elementData, index, numMoved); ElementData [--size] = null; elementData[--size] = null; // clear tolet GC doIts work // Returns the value of the deleted elementreturnoldValue; } Duplicate codeCopy the code

remove(Object o)

Public Boolean remove(Object o) {// If the deleted element is null, the loop finds the first NULL and deletes itif (o == null) {
            for (int index = 0; index < size; index++)
                if(elementData[index] == null) {// Delete fastRemove(index);return true; }}else{// Otherwise find the element equal to o in the array and return the subscript to delete itfor (int index = 0; index < size; index++)
                if(O.quals (elementData[index])) {// Delete fastRemove(index);return true; }}return false; } private void fastRemove(int index) { modCount++; Int numMoved = size-index - 1; int numMoved = size-index - 1;ifArraycopy (elementData, index+1, elementData, index, numMoved); // Decrement the element size by 1 and set the last one to null. elementData[--size] = null; // clear tolet GC doIts work} copies the codeCopy the code

conclusion

Pros and cons of ArrayList

  • The underlying implementation of ArrayList is an array, a random-access mode, and it implements the RandomAccess interface, so lookups, or get, are very fast
  • Arraylists are very convenient for adding elements sequentially, just adding one element to the array
  • When deleting an element, element replication is involved, and if there are many elements to copy, it can be costly in performance
  • When inserting elements, element copying is involved, and if there are many elements to copy, it can be performance costly

Why is the elementData of an ArrayList decorated with transient

  • Note: ArrayList implements the Serializable interface, which means that ArrayList can be serialized. Using transient to describe elementData means I don’t want the elementData array to be serialized
  • When serializing an ArrayList, the elementData in the ArrayList may not be full. For example, elementData is 10 in size, but I only use three of them. Is it necessary to serialize the entire elementData? This is obviously not necessary, so the writeObject method is overridden in ArrayList.
 private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if(modCount ! = expectedModCount) { throw new ConcurrentModificationException(); }} Copy the codeCopy the code
  • Advantages: This method not only improves the serialization efficiency, but also reduces meaningless serialization. It also reduces the serialized file size.

Release notes

  • The source code here is JDK8 version, different versions may vary, but the basic principle is the same.

At the end

ArrayList so much, all he could to the blog, look for the source code, I appreciate this source code is not very difficult, it is based on array because blogger is also a development of the new I am also learning to write I have a goal is a week Two to three articles Hope to be able to insist on a year Hope to your bosses more ideas, let me learn more, Progress together.