Advanced core knowledge in Java comprehensive parsing - ArrayList, working principle of nginx reverse proxy

advanced core knowledge java comprehensive

/
private static final Object[] EMPTY_ELEMENTDATA = {};
// Shared empty array instance for default size empty instance .
// We took it from EMPTY_ELEMENTDATA Distinguish from the array , To know how much capacity needs to be increased when the first element is added Less .
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/
*

  • preservation ArrayList Array of data
    /
    transient Object[] elementData; // non-private to simplify nested class access
    /

    ** ArrayList The number of elements contained
    /
    private int size;
    /
    *
  • Constructor with initial capacity parameter .( The user specifies the capacity )
    /
    public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
    // establish initialCapacity Array of sizes
    this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
    // Create an empty array
    this.elementData = EMPTY_ELEMENTDATA;
    } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    }
    }
    /
    *
    Default constructor ,DEFAULTCAPACITY_EMPTY_ELEMENTDATA by 0. Initialize to 10, In other words, the beginning is actually It's an empty array When the first element is added, the array capacity becomes 10
    /
    public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    /
  • Constructs a list of elements that contain a specified collection , In the order in which they are returned by the iterator of the collection .
    */
    public ArrayList(Collection<? extends E> c) {

elementData = c.toArray();
// If the specified number of collection elements is not 0
if ((size = elementData.length) != 0) {
// c.toArray Maybe it's not Object Type array, so add the following statement to judge ,
// We're using what's in the reflection getClass() Method
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// Replace with empty array
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**

  • Amend this ArrayList The capacity of the instance is the current size of the list . Applications can use this to minimize ArrayList Storage of instances .
    /
    public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
    elementData = (size == 0)
    ? EMPTY_ELEMENTDATA
    : Arrays.copyOf(elementData, size);
    }
    }
    // Here is ArrayList Capacity expansion mechanism of
    //ArrayList The capacity expansion mechanism improves performance , If you expand only one at a time ,
    // So frequent inserts lead to frequent copies , Reduce performance , and ArrayList The expansion mechanism avoids this situation .
    /
    *
  • If necessary, , Increase this ArrayList Capacity of the instance , To make sure it can hold at least the number of elements * @param minCapacity Minimum capacity required
    */
    public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    // any size if not default element table
    ? 0
    // larger than default for default empty table. It’s already
    // supposed to be at default size.
    : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
    ensureExplicitCapacity(minCapacity);
    }
    }
    // Get the minimum expansion capacity
    private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // Get the default capacity and larger values of the incoming parameters
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
    }
    // Determine whether capacity expansion is needed
    private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
// call grow Methods to expand capacity , Calling this method means that the expansion has started
grow(minCapacity);
}
/**

  • Maximum array size to allocate
    /
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /
    *
  • ArrayList The core method of capacity expansion .
    */
    private void grow(int minCapacity) {

// oldCapacity Old capacity ,newCapacity New capacity
int oldCapacity = elementData.length;
// take oldCapacity Moves to the right one , The effect is equivalent to oldCapacity /2,
// We know that bit operations are much faster than division operations , The result of the whole expression is to replace the new capacity with the old one 1.5 times ,
int newCapacity = oldCapacity + (oldCapacity >> 1);
// Then check whether the new capacity is greater than the minimum required capacity , If it is still less than the minimum required capacity , Then take the minimum required capacity as New capacity of array ,
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// Check again if the new capacity exceeds ArrayList The maximum capacity defined ,
// If it's over , Call hugeCapacity() To compare minCapacity and MAX_ARRAY_SIZE,
// If minCapacity Greater than MAX_ARRAY_SIZE, The new capacity is Interger.MAX_VALUE, otherwise , new The capacity size is MAX_ARRAY_SIZE.
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);
}
// Compare minCapacity and MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
Returns a list of elements in this .
/
public int size() {
return size;
}
/

  • If this list does not contain elements , Then return to true .
    /
    public boolean isEmpty() {
    // Be careful = and == The difference between
    return size == 0;
    }
    /
    *
  • If this list contains the specified element , Then return to true .
    /
    public boolean contains(Object o) {
    //indexOf() Method : Returns the index of the first occurrence of a specified element in this list , If this list does not contain this element , be by -1
    return indexOf(o) >= 0;
    }
    /
    *
    Returns the index of the first occurrence of a specified element in this list , If this list does not contain this element , Then for -1
    /
    public int indexOf(Object o) {
    if (o == null) {
    for (int i = 0; i < size; i++)
    if (elementData[i]==null)
    return i;
    } else {
    for (int i = 0; i < size; i++)
    //equals() Methods to compare
    if (o.equals(elementData[i]))
    return i;
    }
    return -1;
    }
    /
  • Returns the index of the last occurrence of the specified element in this list , If this list does not contain elements , Then return to -1.
    /
    public int lastIndexOf(Object o) {
    if (o == null) {
    for (int i = size-1; i >= 0; i–)
    if (elementData[i]==null)
    return i;
    } else {
    for (int i = size-1; i >= 0; i–)
    if (o.equals(elementData[i]))
    return i;
    }
    return -1;
    }
    /
    *
  • Back here ArrayList Shallow copy of instance . ( The element itself is not copied .)
    /
    public Object clone() {
    try {
    ArrayList<?> v = (ArrayList<?>) super.clone();
    //Arrays.copyOf The function is to copy the array , Return the copied array . The parameters are the copied array and the copied array The length of
    v.elementData = Arrays.copyOf(elementData, size);
    v.modCount = 0;
    return v;
    } catch (CloneNotSupportedException e) {
    // It shouldn't have happened , Because we can clone
    throw new InternalError(e);
    }
    }
    /
    *
    * In the right order ( From the first to the last element ) Returns an array containing all elements in this list .
    * The returned array will be “ Safe ”, Because the list does not retain references to it . ( let me put it another way , This method must assign a new Array ).
    therefore , The caller is free to modify the returned array . This method acts as array based and set based API The bridge between .
    /
    public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
    }
    /
  • Returns an array containing all the elements in this list in the correct order ( From the first to the last element );
    * The runtime type of the specified array . If the list fits the specified array , Then return to .
    * otherwise , A new array will be assigned to the runtime type of the specified array and the size of this list .
    * If the list applies to the specified array , Other space ( That is, there are more lists in the array than in this element ), The number immediately after the end of the set The elements in the group are set to null .
    *( This determines the length of the list only if the caller knows that the list does not contain any empty elements .)
    */
    @SuppressWarnings(“unchecked”)
    public T[] toArray(T[] a) {
    if (a.length < size)
    // Create an array of runtime types , however ArrayList Contents of array
    return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // call System Provided arraycopy() Method to copy between arrays
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
    a[size] = null;
    return a;
    }
    // Positional Access Operations

@SuppressWarnings(“unchecked”)
E elementData(int index) {
return (E) elementData[index];
}
/**

  • Returns the element at the specified position in this list .
    /
    public E get(int index) {
    rangeCheck(index);
    return elementData(index);
    }
    /
    *
  • Replace the element at the specified position in this list with the specified element .
    */
    public E set(int index, E element) {
    // Yes index Do a boundary check
    rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
// Return the original element in this position
return oldValue;
}

/**

  • Appends the specified element to the end of this list .
    */
    public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    // See here ArrayList The essence of adding elements is to assign values to arrays
    elementData[size++] = e;
    return true;
    }

/**

  • Inserts the specified element at the specified position in this list .
    * First call rangeCheckForAdd Yes index Do a boundary check ; And then call ensureCapacityInternal Fang The law guarantees capacity Large enough ;
    * From index All members after the start move one position back ; take element Insert index Location ; Last size Add 1.
    */
    public void add(int index, E element) {
    rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy() This method of copying between arrays must take a look , Here's how it works arraycopy() Method and reality Now the array copies itself
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

/**

  • Delete the element at the specified position in the list . Move any subsequent elements to the left ( Subtract an element from its index ).

《 A big factory Java Analysis of interview questions + Back end development learning notes + The latest architecture explanation video + Practical project source code handout 》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 Full content open source sharing

/
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[–size] = null; // clear to let GC do its work
// Elements removed from the list
return oldValue;
}

/**

  • Removes the first occurrence of the specified element from the list ( If there is ). If the list does not contain the element , Then it will not change .
    * return true, If this list contains the specified element
    */
    public boolean remove(Object o) {
    if (o == null) {
    for (int index = 0; index < size; index++)
    if (elementData[index] == null) {
    fastRemove(index);
    return true;
    }
    } else {
    for (int index = 0; index < size; index++)
    if (o.equals(elementData[index])) {
    fastRemove(index);
    return true;
    }
    }
    return false;
    }

/*

  • Private remove method that skips bounds checking and does not
  • return the value removed.
    */
    private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
    numMoved);
    elementData[–size] = null;
    // clear to let GC do its work
    }

/**

  • Remove all elements from the list .
    */
    public void clear() {
    modCount++;

// Set the values of all elements in the array to null
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

/**

  • According to the specified set Iterator The order returned appends all elements in the specified collection to the end of this list .
    */
    public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew); // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
    }

/**

  • Inserts all elements in the specified collection into this list , Start at the designated location .
    */
    public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

/**

  • Remove all indexes from this list as fromIndex ( contain ) and toIndex Between the elements .
    * Move any subsequent elements to the left ( Reduce its index ).
    */
    protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
    numMoved);
    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
    elementData[i] = null;
    }
    size = newSize;
    }

/**

  • Check that the given index is in range .
    /
    private void rangeCheck(int index) {
    if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    /
    *
  • add and addAll The use of rangeCheck A version of
    */
    private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

/**

  • return IndexOutOfBoundsException Details
    */
    private String outOfBoundsMsg(int index) {
    return "Index: “+index+”, Size: "+size;
    }

/**

  • Removes all elements contained in the specified collection from this list .
    */
    public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull;
    // If this list is modified, return to true
    return batchRemove(c, false);
    }

/**

  • Keep only the elements contained in the specified collection in this list .
    * let me put it another way , Remove all elements from this list that are not included in the specified collection .
    */
    public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull;
    return batchRemove(c, true);
    }

/**

  • Start at the specified position in the list , Returns the elements in the list ( In the right order ) List iterator for .
    * The specified index indicates that the first element returned by the initial call is next . Initial call previous Will return the specified index minus 1 Of Elements .
    * The list iterator returned is fail-fast .
    */
    public ListIterator listIterator(int index) {
    if (index < 0 || index > size)
    throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
    }

/**
* Returns the list iterator in the list ( In proper order ).
* The list iterator returned is fail-fast .
*/
public ListIterator listIterator() {
return new ListItr(0);
}

/**
* Returns the iterators of the elements in the list in the correct order .
* The iterator returned is fail-fast .
*/
public Iterator iterator() {
return new Itr();
}

3、 ... and 、 ArrayList Source code analysis

1. System.arraycopy() and Arrays.copyOf() Method

Through the above source code, we find that these two methods of array replication are widely used, and many places are particularly clever . For example, below add(int index, E element) The method is skillfully used arraycopy() Method to make the array copy by itself index All members after the start move one position back :

/**

  • Inserts the specified element at the specified position in this list .
  • * First call rangeCheckForAdd Yes index Do a boundary check ; And then call ensureCapacityInternal The method guarantees capacity Large enough ;
    * From index All members after the start move one position back ; take element Insert index Location ; Last size Add 1.
    */
    public void add(int index, E element) {
    rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy() Method to implement the array to copy itself
//elementData: Source array ;index: The starting position in the source array ;elementData: Target array ;index + 1: Starting position in the target array ; size - index: The number of array elements to copy ;
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}

And so on toArray() The method used copyOf() Method

/**
* In the right order ( From the first to the last element ) Returns an array containing all elements in this list .
* The returned array will be “ Safe ”, Because the list does not retain references to it . ( let me put it another way , This method must assign a new Array ).

copyright:author[m0_ sixty-four million three hundred and eighty-four thousand t],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/01/202201261457007994.html