Java collection 1 – ArrayList

Java collection 1 – ArrayList

See article: Illustrated collection 1: ArrayList

The data structures used by an ArrayList are arrays, which hold elements.

features
Whether to access null values	can
Whether the element can be repeated	can
Whether to order	The orderly
Thread safe or not	unsafe

Next, analyze it directly from the source code (JDK1.8).

Cloning, random access, serialization

Let’s look at the definition of ArrayList:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the code

• It implements the RandomAccess interface, which is a flag interface indicating that RandomAccess operations can be performed on the collection.
• A Clonable interface was implemented, and Object’s Clone method was overridden (if the interface was implemented but the method was not overridden, calling the Clone method directly would be punishedCloneNotSupportedExceptionException), indicating that the collection can be copied, cloned.
• The Serializable interface is implemented, and the readObject and writeObject methods are overridden, indicating that it can be serialized.

An array of entities

    /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */
    transient Object[] elementData; // non-private to simplify nested class access
Copy the code

ElementData is an entity that holds elements in the ArrayList, and the member variable is modified transient to indicate that the variable is ignored during serialization (the member is not serialized). The reason for this modification can be found in the writeObject and readObject methods.

Clone method

    /**
     * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    public Object clone(a) {
        try{ ArrayList<? > v = (ArrayList<? >)super.clone(); / / 1
            v.elementData = Arrays.copyOf(elementData, size); / / 2
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw newInternalError(e); }}Copy the code

Note: Returns a shallow copy of the current object. The elements of the collection themselves will not be copied.

The ** array. copyOf method copies only the references from the array entities to the array ** of the new collection.

WriteObject method

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

This method is used to determine which members of the object need to be serialized when serializing an ArrayList to a file, see // Write out all elements in the proper Order. The next for loop of the comment, which means to write all elements (e.g. files) to the correct location, corresponds to the readObject (deserialization from files).

The array of elements in the ArrayList is not always fully used. For example, the array size is 10, but there are only four elements, and the remaining six elements are null. The for loop in the writeObject method only serializes the actual four elements (size). Instead, if the writeObject method is not overridden and elementData does not use the transient modifier, the default serialization method will be used. The six null elements will also be serialized, taking up some device resources. Thus resulting in waste.

ReadObject methods

/** * Reconstitute the ArrayList instance from a stream (that is, * deserialize it). */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the code

// Read in all elements in the proper order The next for loop for the comment, corresponding to writeObject, only needs to deserialize the size element.

The add method

Two parameters of the add method is used for the specified subscript insert a new element, before you insert the check target subscript bounds (cross will receive IndexOutOfBoundsException) abnormal, determine capacity, after the last insert element specifies the subscript.

Initial array size and expansion strategy

Three initialization methods

1. ArrayList(int initialCapacity): array entities of the initial specified length:elementData = new Object[initalCaacity];
2. ArrayList(): array entities of initial default length:this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;It’s an array of length 0.
3. ArrayList(Collection<? extends E> c)Initialize the ArrayList with the given collection

capacity

There are three main methods for expanding array entities:

1. ensureCapacityInternal: Determines the capacity to be expanded.
2. ensureExplicitCapacity: Determines the capacity expansion operation
3. grow: Perform capacity expansion

EnsureCapacityInternal method

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
Copy the code

The default value of the minCapactiy parameter is size+1. If elementData is an empty array (created using the Arraylist no-argument constructor and called for the first time), then determine that the required capacity is DEFAULT_CAPACITY, whose value is 10.

EnsureExplicitCapacity method

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
Copy the code

ModCount is used to record The Times of modifying the list structure. Structural modification refers to changing the size of the list. Modifying the list structure while traversing the collection may cause errors in traversing results. So by the value to indicate (resistance) in traversed to modify behavior (in the way of throw ConcurrentModificationException).

Call the grow method to perform capacity expansion. This part of the code virtual machine requests memory from the operating system. If insufficient memory is allocated, an OutOfMemoryError may be raised.

Grow method (Expansion strategy)

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

The grow method allows an ArrayList to dynamically expand the size of a collection by expanding the size of an array.

Capacity Expansion policy:

1. oldCapacity + (oldCapacity >> 1)The key sentence determines the new array capacity: 3/2 of the current capacity, which increases the current size by half.
2. If the new capacity calculated based on the rule is still smaller than the specified capacity, expand the capacity based on the specified capacity.
3. If the capacity calculated in these two steps is greater thanMAX_ARRAY_SIZE(the value isInteger.MAX_VALUE - 8), executehugeCapacityMethod, which indicates that the array size threshold is near, most likely raising an OutOfMemoryError.

Finally, once the new capacity is determined, you simply create a new array of the new size and copy the elements from the original array into the new array.

The get method

/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc} * /
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

Copy the code

The get method is used to get the element with the specified subscript from the collection. You just need to get the element with the index from the array entity. Before doing this, you need to check whether the array index is out of bounds.

---