preface

In Java, the frequency of collection is still very high, the common questions that lead to the interview, most of the Internet has a variety of big names to explain the blog, this article is based on the online materials, do a small summary.

The basic, commonly used Collection implementation class is shown in purple. Let’s start with the Collection top-level interface

The Collection interface

int size(a); // Get the collection length

boolean isEmpty(a); // Check whether the set is empty

boolean contains(Object o);  // Check whether the set contains this element

Iterator<E> iterator(a);  / / the iterator

Object[] toArray();  // Turn a collection into an array

<T> T[] toArray(T[] a);  // Return the elements of the collection as an array of the specified element type

boolean add(E e); // Add an element to the collection

boolean remove(Object o); // Remove the appropriate elements from the collection

boolean containsAll(Collection
        c);  // Check whether the set contains all the elements of the other set

boolean addAll(Collection<? extends E> c); // Adds elements from another collection to the current collection

boolean removeAll(Collection
        c); // Remove an element contained in another collection

boolean retainAll(Collection
        c); // Keep the elements contained in another set

void clear(a); // Remove all elements from the collection

boolean equals(Object o); // Compare whether the collection points to the same address

int hashCode(a); // Return the hash value of the current collection
Copy the code

The Collection interface has some methods to implement, and inheriting the List from the Collection is List interface also has some methods defined by the interface. This defines the methods to be implemented, such as a template, or if you want to inherit the Collection interface, and display the methods in the custom interface, so that you can understand and see them more clearly.

Such as

Define an interface

public interface aList<E> extends Collection<E> {}/ / the List interface
public interface List<E> extends Collection<E> {
// The List interface is written as such
    int size(a);
}
Copy the code

In defining an implementation class

public class tList<E> implements aList<E> {
    @Override
    public int size(a) {
        return 0;
    }
    // Omit many ways to achieve...
}
Copy the code

test

public static void main(String[] args) {
    aList<Integer> a = new tList<Integer>();
    System.out.println(a.size());
}

// Result: 0
Copy the code

This explains why the methods defined in the Collection interface need to be implemented, and why the List subclass needs to be written in order to determine what classes need to be implemented in the current interface, instead of clicking on the superclass to see what methods are defined in the superclass interface.

ArrayList Collection description

I said ArrayList is the List interface implementation class so that we can use polymorphic form to create a collection

List<Integer> list = new ArrayList<>();
// Create a collection, form polymorphic, superclass = new subclass implementation ();
Copy the code

What is polymorphism: compile look left, run look right.

attribute

// Default initial capacity
private static final int DEFAULT_CAPACITY = 10;

// The array is empty by default
private static final Object[] EMPTY_ELEMENTDATA = {};  // Assign elementData as an empty array
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // To determine the initial capacity expansion conditions

// Store the data in the final place
transient Object[] elementData; 

// Data size
private int size;
Copy the code

The constructor

// ArrayList source construct
public ArrayList(int initialCapacity) {  // Create a collection with the default initial specified size
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}public ArrayList(a) { // Create a default collection
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) { // In simple terms, initialize data from a set to the current set
  elementData = c.toArray();
  if((size = elementData.length) ! =0) {
    // c.toArray might (incorrectly) not return 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 code

From a class attribute and constructor, you can see that the collection is internally implemented by an array and that DEFAULT_CAPACITY is also found to be the initial capacity of the collection 10

A brief description of CRUD for collections

increase

public boolean add(E e) {
    // Verify whether capacity expansion is required
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // Add the value to the corresponding subscript
    elementData[size++] = e;
    return true;
}
Copy the code

delete

public E remove(int index) {
    // Check whether the subscript is out of bounds
    rangeCheck(index);
    
    / / the operands
    modCount++;
    // Obtain the data with the corresponding subscript
    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

    return oldValue;
}
Copy the code

change

public E set(int index, E element) {
    // Check whether the subscript is out of bounds
    rangeCheck(index);
    // Get the value of the corresponding subscript
    E oldValue = elementData(index);
    // Reassign the value
    elementData[index] = element;
    // Return the previous element
    return oldValue;
}
Copy the code

check

public E get(int index) {
     // Check whether the subscript is out of bounds
    rangeCheck(index);
    // Get the value of the corresponding subscript
    return elementData(index);
}
Copy the code

CURD summary

This is not really the main thing about the ArrayList collection, it’s the simple thing to go to the source and see what’s in the source code, it’s the scaling mechanism.

ArrayList Collection expansion mechanism

The DEFAULT_CAPACITY attribute has a value of 10. Let’s see what it does

public boolean add(E e) {
    // Verify whether capacity expansion is required
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // Add the value to the corresponding subscript
    elementData[size++] = e;
    return true;
}
Copy the code

It starts at ensureCapacityInternal(size + 1), where size is all variables, it’s the size of the tag ArrayList (the number of elements it contains), and no element at this point is ensureCapacityInternal(0 + 1).

//1, enter this method
private void ensureCapacityInternal(int minCapacity) {
  //2, first call calculateCapacity(elementData, minCapacity). This method checks the first addition of data and returns the default container size (which is 10).
  // calculateCapacity(elementData, minCapacity) did the operation.
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//3, array capacity calculation
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // This is true when the data is first added
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    // Then this is true. The method is to take the maximum value between the two parameters 1 and 2
    // DEFAULT_CAPACITY: the default value is 10
    // minCapacity: 1 is added for the first time
    // So 10 and 1, 10 big, finally 10 back out
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

//5. Ensure explicit capacity
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

   // 6.
  // Add data for the first time 10-0 > 0: the first time is valid
  // Add data from 2 to 10 > 0 in the second time: the second time can be invalid
  if (minCapacity - elementData.length > 0)
    //7, execute the following method to actually expand the ArrayList container and determine the size of the first expansion
    grow(minCapacity);/ / capacity
}
Copy the code

The illustration

Turns () method

//minCapacity Minimum capacity required
private void grow(int minCapacity) {
  // overflow-conscious code
  // Get the current array container size
  int oldCapacity = elementData.length;
  / / expansion. New capacity = current capacity +(current capacity /2), increase current capacity by half (increase current capacity by 1.5 times)
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // Check if the capacity is still smaller than the minimum capacity
  if (newCapacity - minCapacity < 0)
    // Assign the minimum required capacity to newCapacity
    newCapacity = minCapacity;
  // If the expanded capacity is greater than the threshold, the system allocates large capacity
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    // All hugeCapacity(minCapacity) does is throw an overflow exception when minCapacity is less than 0
    // Or return a larger capacity and assign a value to the new capacity
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  // Copy the array and change the size of the array.
  //copyof(original array, new array length)
  elementData = Arrays.copyOf(elementData, newCapacity);
}
// Perform large capacity allocation
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow // If minCapacity<0, throw an overflow exception
    throw new OutOfMemoryError();
  // If the desired capacity is greater than MAX_ARRAY_SIZE, allocate Integer.MAX_VALUE; otherwise, allocate MAX_ARRAY_SIZE
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}
Copy the code

figure

Private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;Copy the code

I will help you translate, ha ha ha.

Overall flow chart

summary

• The underlying structure of ArrayList is an array structure, and the specific implementation of automatically expanding the size of the element space determines the expansion each time data is added. The key method is the gorw() method
• The default capacity is 10, and the default expansion factor is :(the current capacity is increased by 1.5 times)
• An ArrayList can hold null values, non-thread-safe collections, and duplicate elements

Questions can be discussed together, learn with an open mind, and then summarize the implementation principles of some other implementation classes

Throw in chicken soup