I. Background (Russell’s Paradox)

One day, the barber in the village hung up a sign saying, “I cut the hair of everyone in the village who doesn’t cut his own hair, and I only cut theirs.” Someone asked the barber, “Who will cut your own hair?”

Russell: British philosopher and mathematician who, in 1902, shook the foundations of mathematics. Set Theory: the cornerstone of modern mathematics, mathematician Cantor, a German, was of Jewish descent. At first, he studied trigonometric functions, and gradually explored and proposed set theory, which aroused huge controversies, including his teacher, who gradually became depressed and went insane, and died in a mental hospital in loneliness.

A biography of John Nash, the author of the game theory of a Beautiful Mind, who fought against schizophrenia all his life and won the Nobel Prize in Economics.

Two, gather these things (three chunks)

List Has sequential repeatable ArrayList Set No sequential non-repeatable HashSet Map Key-value pair HashMap

Third, ArrayList

If you store all members, what do you use? 100-1000-10000 (Container: dynamic, quick query)

1) Overview (60 points)

List Array: int[] arr = new int[3] Initialization requires a defined length, and the length cannot be changed dynamic arrays: ArrayList solves the problem of fixed array length, and introduces new problems. If the capacity is insufficient, expand the capacity. Expansion algorithm?

Array features: memory space is continuous storage, random access efficiency is very high. Encapsulation as an ArrayList reduces the efficiency of additions and deletions. Expansion may be required. When deleting, you may need to move it

Interview questions:

How to expand an ArrayList? B If 1W pieces of data need to be added, how to improve efficiency? (80 marks) C Is it thread safe? How to be thread safe? D What is fail_fast? (100

2) Source code analysis (version 1.8)

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

I inherit AbstractList and implement List, need to provide the most basic add, delete, change and check function ii implement RandomAccess, support RandomAccess/fast access, and the same access mode as array iii implement Cloneable, Can be cloned iv implements Serializable and can be serialized. If custom serialization is required, writeObject and readObject methods need to be implemented

B constructor (Alt +7 for a list of methods)

I No arguments // Array of objects that store all data

    Object[] elementData
    public ArrayList(a) {
        // On initialization, assign an empty array {}
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
Copy the code

Ii has parameters of type int // passed to initialize the capacity

   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 code

Int size; int size; // Support for converting other collections to arrayList

 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if((size = elementData.length) ! =0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // Check whether the array is of type object[]
            if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA; }}Copy the code
C Add elements
// Assign and add size+1
public boolean add(E e) {
    // Verify that the capacity is sufficient
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // Calculate the capacity first and then confirm the exact capacity
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// Default initialization capacity
int DEFAULT_CAPACITY = 10;
// At least 1 capacity is required for an empty array
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // Returns the maximum of the default capacity (10) and minimum capacity (1)
        // For the first expansion, expand the capacity to at least 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// Record the number of changes
int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // Core operations for capacity expansion
        grow(minCapacity);
}

// elementData is {} minCapacity is 10
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // ">> 1" right shift ==/2
    // The new capacity is one and a half times the old capacity.
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)
        // Min checks the current assignment to 10
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // Check the maximum value
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // Create a new array and copy the old array
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

Capacity expansion algorithm: I The minimum capacity expansion range is 10. The default capacity expansion range of II is 1.5 times that of the old capacity

Performance verification: If the data volume is large and the data is added one by one, how many times should the capacity be expanded? What are 1K, 1W, 10W, 100W respectively? 12, 18, 23, 29 Good algorithms can reduce the number of capacity increases

3) Delete elements

Two methods are supported: index and object itself

// Take index deletion as an example
public E remove(int index) {
    // Range check
    rangeCheck(index);
    
    // Number of changes +1
    modCount++;
    E oldValue = elementData(index);
    
    // Count the number of elements to move
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // Move elements by copying them
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);

    // set the last element to empty size-1
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
Copy the code

4) Iterate over elements

Can’t remove elements in the foreach loop, modify the abnormal ConcurrentModificationException will quote synchronization

Thread insecurity is essentially a matter of quick warning and quick handling of possible failures.

5) Thread safety

The Vector class is thread-safe, outdated, and very inefficient with a bunch of locks

CopyOnWriteArrayList works with a concurrent package: Adds and deletes operations through new copies, and then changes array references. (Reduced efficiency)