Common Collection analysis

The Collection Collection

List

ArrayList

attribute

// Default initialization length
private static final int DEFAULT_CAPACITY = 10;
/ / an empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
// Default empty array
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// The built array
transient Object[] elementData;
// Array length
private int size;
AbstractArrayList = AbstractArrayList */
protected transient int modCount = 0;
Copy the code

Initialize the

// 1. Create a default empty array object with no arguments
public ArrayList(a) {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Create an array object of the specified length
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // Create an empty array object with a length of 0
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// 3. The argument is the construction of the collection
public ArrayList(Collection<? extends E> c) {
    // Convert the collection to an array object
    Object[] a = c.toArray();
    if((size = a.length) ! =0) {
        // Sets of type ArrayList are directly converted to the current object
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            // Copies the transformed array and builds the copied values into the current ArrayList objectelementData = Arrays.copyOf(a, size, Object[].class); }}else {
        // replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the code

The add method

// Add a single element
public boolean add(E e) {
    /** * 1. Check the length of the array and modify the value * 2. New elements are added to the array */
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // Add the element to the last available space
    elementData[size++] = e;
    return true;
}
Copy the code

/** * adds the element to the specified index position * 1. Verifies that the subscript meets the current set * 2. */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // Moves the specified index index and subsequent elements backward
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // Assign the index subscript to the array
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code

Check and expand the array before adding:

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// Return the length of the array
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // Check whether the current array is an empty array object
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // Compare the default length with the current minimum length and return the maximum length
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// Make sure the array is long. If there is no available length, expand the array
private void ensureExplicitCapacity(int minCapacity) {
    // The number of changes is increased by 1
    modCount++;
    // overflow-conscious code
    // Compare the required minimum length with the maximum length of the current array to determine whether the array needs to be expanded
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    // The maximum length of the current array
    int oldCapacity = elementData.length;
    // The maximum length of the new array is 0.5 times larger than the current array
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // If the array length exceeds the maximum length that can be created
        // Returns the maximum number of arrays that can be created
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // Copy the data from the old array into the newly created array
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the code

The remove method

// Remove the labeled element in the array
public E remove(int index) {
    // Check whether the current subscript is out of range of the array
    rangeCheck(index);
	// The number of times the array has been modified increases by 1
    modCount++;
    // Retrieves the value to be deleted
    E oldValue = elementData(index);
	// The subscript of the element to be deleted
    int numMoved = size - index - 1;
    if (numMoved > 0)
         // Move the array element after the specified index+1 position to the front of the image
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // Empty the last element of the array to facilitate JVM recycling
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
// Deletes the specified element
public boolean remove(Object o) {
    if (o == null) {
        // If the element is empty, iterate over the number group and delete the empty element
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true; }}else {
        // Iterate through the array to delete the specified element
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
} 
// The logic to remove elements from an array
private void fastRemove(int index) {
    // The number of times the array has been modified increases by 1
    modCount++;
    // The subscript of the element to be deleted
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // Move the array element after the specified index+1 position to the front of the image
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
    // Empty the last element of the array to facilitate JVM recycling
    elementData[--size] = null; // clear to let GC do its work
}
Copy the code

LinkedList

attribute

// List length
transient int size = 0;
/ / the first node
transient Node<E> first;
/ / end nodes
transient Node<E> last;
AbstractArrayList = AbstractArrayList */
protected transient int modCount = 0;
Copy the code

Initialize the

// Create a linked list with no arguments
public LinkedList(a) {}

// A collection object with parameters
public LinkedList(Collection<? extends E> c) {
    this(a); addAll(c); }Copy the code

// addAll method to add collection data to the linked list
// Add one by one
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

/** * add the collection to the list **@paramIndex Position of the node to be inserted *@paramC Set data to be inserted */
public boolean addAll(int index, Collection<? extends E> c) {
    // Check whether the specified node position is in the linked list
    checkPositionIndex(index);
	// The collection to be inserted is converted to an array object
    Object[] a = c.toArray();
    // The length of the array to be inserted
    int numNew = a.length;
    if (numNew == 0)
        return false;
	// Temporary node, the last node before pre, succ current node
    Node<E> pred, succ;
    // Insert node position is the tail node
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // Insert the node into the middle part of the node
        succ = node(index);
        pred = succ.prev;
    }
	
    // iterate over the insert node
    for (Object o : a) {
        @SuppressWarnings("unchecked") 
        E e = (E) o;
        // Create a node
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        // A new node is inserted, and the pointer moves backwards
        pred = newNode;
    }

    // Connect the disconnected list to the inserted node
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
	// Change the length of the list
    size += numNew;
    // Modify the number of set changes
    modCount++;
    return true;
}
Copy the code

The add method

/ / new
public boolean add(E e) {
    linkLast(e);
    return true;
}
// Use the tail insertion method to add
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// Insert nodes at the head of the list
 public void addFirst(E e) {
     linkFirst(e);
 }
// Insert a node with a header
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
Copy the code

The remove method

Empty parameter delete: remove()

Data of the first node of the node to be deleted

// Delete node elements
public E remove(a) {
    return removeFirst();
}

// Delete the first node element
public E removeFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
Copy the code

Remove the first element: removeFirst()

public E removeFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
Copy the code

The first node breaks the chain

// Disconnect the first node from the list
 private E unlinkFirst(Node<E> f) {
     // assert f == first && f ! = null;
     final E element = f.item;
     final Node<E> next = f.next;
     f.item = null;
     f.next = null; // help GC
     first = next;
     if (next == null)
         last = null;
     else
         next.prev = null;
     size--;
     modCount++;
     return element;
 }
Copy the code

Remove (Object o)

// Remove the specified element from the list
public boolean remove(Object o) {
    // Whether the element to be deleted is empty
    if (o == null) {
        // Iterate from the first node
         for(Node<E> x = first; x ! =null; x = x.next) {
             // Check whether the element is to be deleted
             if (x.item == null) {
                 // Delete the link
                 // For details, see the chain breaking operation
                 unlink(x);
                 return true; }}}else {
        // The element to be deleted is not empty
         for(Node<E> x = first; x ! =null; x = x.next) {
             // Check whether the element is to be deleted
             if (o.equals(x.item)) {
                 // Delete the link
                 // For details, see the chain breaking operation
                 unlink(x);
                 return true; }}}return false;
 }
Copy the code

Remove (int index)

 
public E remove(int index) {
    // Verify that the specified location is in the list
    checkElementIndex(index);
     // Delete the link
     // For details, see the chain breaking operation
     return unlink(node(index));
 }
private void checkElementIndex(int index) {
    if(! isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
	// Determine whether the current position is in the first half or the second half
    // Walk through the list to find elements
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        returnx; }}Copy the code

Break the chain operation

// Break the chain to remove elements
// the x node is not empty
E unlink(Node<E> x) {
    // assert x ! = null;
    // Current node value
    final E element = x.item;
    // The next node of the current node
    final Node<E> next = x.next;
    // The last node of the current node
    final Node<E> prev = x.prev;
	// If the last node of the current node is empty, the current node is the first node
    if (prev == null) {
        // Set the next node to the first node
        first = next;
    } else {
        // Set the next pointer to the next node of the current node
        // (graphic: wechat image _20210316145013.png)
        prev.next = next;
        x.prev = null;
    }
	// If the next node of the current node is empty, the current node is the last node
    if (next == null) {
        // Set the last node to the tail node
        last = prev;
    } else {
        // Add the current node's
        // image :(wechat image _2021031614501.png)
        next.prev = prev;
        x.next = null;
    }
 
    x.item = null;
    size--;
    modCount++;
    return element;
}
Copy the code

Remove endpoints: removeLast()

 public E removeLast(a) {
     final Node<E> l = last;
     if (l == null)
         throw new NoSuchElementException();
     return unlinkLast(l);
 }
// The end node breaks the chain
private E unlinkLast(Node<E> l) {
    // assert l == last && l ! = null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
Copy the code

RemoveFirstOccurrence (Object O)

public boolean removeFirstOccurrence(Object o) {
    // Call the delete method
    return remove(o);
}
Copy the code

Map

HashMap

attribute

/ / = = = = = = = = = = = = = = = = = = = = default configuration = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    /* The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /** * maximum length, * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two < = 1 < < 30. * /
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /* The load factor used when none specified in constructor. */
    static final float DEFAULT_LOAD_FACTOR = 0.75 f;

    * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */
    static final int TREEIFY_THRESHOLD = 8;

    /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */
    static final int UNTREEIFY_THRESHOLD = 6;

    /** * The minimum size of the array when the list is converted to a red-black tree * Tree operations will not exist * The smallest table capacity for which bins may be treeified. * (Otherwise The table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */
    static final int MIN_TREEIFY_CAPACITY = 64;

/* ---------------- Fields -------------- */

    /** * array, initialized at first use, Allocated tokens * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */
    transient Node<K,V>[] table;

    /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */
    transient Set<Map.Entry<K,V>> entrySet;

    /** * The number of key-value mappings contained in this map. */
    transient int size;

    /** * The number of times this HashMap has been structurally modified * Structural modifications are those that  change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
    transient int modCount;

    /** * The next size value at which to resize (capacity * load factor). **@serial* /
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    /** * The load factor for The hash table. **@serial* /
    final float loadFactor;

Copy the code

Defined data structures

Node

static class Node<K.V> implements Map.Entry<K.V> {
    // Hash value of the node
    final int hash;
    // The key value in the key-value pair
    final K key;
    // The value of the key-value pair
    V value;
    // Pointer to the next node
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    / /... Contains get, set, hashCode, and toString methods
}
Copy the code

TreeNode

static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    
    / /... Methods in nodes
}

// LinkedHashMap.Entry 
 static class Entry<K.V> extends HashMap.Node<K.V> {
     Entry<K,V> before, after;
     Entry(int hash, K key, V value, Node<K,V> next) {
         super(hash, key, value, next); }}Copy the code

Initialize the

// An empty parameter construct that specifies the default load factor
public HashMap(a) {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// Specify a constructor for the initialization length
public HashMap(int initialCapacity) {
     this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/** * specifies the initialization length and load factor constructor **@paramInitialCapacity Initialization length *@paramLoadFactor loadFactor */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

// The argument is a collection constructor
// Default load factor
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

/** * Implements Map. PutAll and Map constructor@param m the map
 * @paramEvict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). True: uninitialized call */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // Set is empty
        if (table == null) { // pre-size
            // Calculate the required map set length
            // The underlying table of HashMap will be expanded when entry_count>table_size*load_factory is used.
		   // To prevent HashMap from expanding, table_size >= entry_count/load_factor is required.
		   // Size in the formula ((float)s/loadFactor) + 1.0f is computed using float, + 1.0f is computed because ((float)s/loadFactor) is computed using float and is rounded when converted to an integer
            // In order to ensure that the final calculated size is large enough not to trigger expansion, + 1.0f operation is performed
        
            float ft = ((float)s / loadFactor) + 1.0 F;
            // The required length is compared to the maximum length
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                // The perturbation function recalculates the required length
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            // Perform capacity expansion
            resize();
        // Iterate over the collection to be inserted, saving the element to the new collection
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict); }}}Copy the code

Put method

// Save the element
public V put(K key, V value) {
    return putVal(hash(key), key, value, false.true);
}
Copy the code

PutVal method

/ * * * *@paramHash Hash value of the key in the map *@paramKey Indicates the key value * in the key-value pair@paramValue Value * in a key value pair@paramOnlyIfAbsent (True /false) The current value * is not changed when the value is true@paramEvict false: initial call, true: uninitial call */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // the TAB object, the data node in p, the length of n, the subscript in I
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // If the array is empty or its length is 0, the array is initialized
        n = (tab = resize()).length;
    // Check whether the new key has data in the corresponding position
    // Whether a hash collision occurs
    if ((p = tab[i = (n - 1) & hash]) == null)
        // Add the new element to the array
        tab[i] = newNode(hash, key, value, null);
    else {
        // A hash collision occurs
        // p is the original data node
        Node<K,V> e; K k;
        // p.hash == hash The hash value of the original data node is the same as that of the newly stored node
        // (k = p.key) == key The key of the original data node is the same as the key address of the newly stored node
        // (key ! = null && key.equals(k)) The newly stored node is not null and has the same value as the original node
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            // The key of the newly stored node exists in the map
            e = p;
        else if (p instanceof TreeNode)
            // Check whether it is a tree node
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 
            for (int binCount = 0; ; ++binCount) {
                // Find the free location to save the node
                if ((e = p.next) == null) {
                    // Create a node
                    p.next = newNode(hash, key, value, null);
                    // Check whether the list length is 8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // Lists are converted to red-black trees
                        treeifyBin(tab, hash);
                    break;
                }
                // If the key value of the node is the same as that of the current node, the loop is broken
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break;
                // Move the pointer backp = e; }}// Existing nodes in map are not empty
        if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            If onlyIfAbsent is false or the value of an existing node is null, update the value of the current key
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            returnoldValue; }}// Change the number of changes
    ++modCount;
    // Determine whether the current length needs to be expanded
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

Capacity: the resize ()

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // Get the node array length
    int oldCap = (oldTab == null)?0 : oldTab.length;
    // Capacity expansion threshold
    int oldThr = threshold;
    int newCap, newThr = 0;
    // Check whether it is the first initialization
    if (oldCap > 0) {
        // Whether the length of the original node array reaches the maximum length
        if (oldCap >= MAXIMUM_CAPACITY) {
            // If the length is greater than the maximum, no operation is performed
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // Expanded length = original length x 2
        // Verify that the new length reaches the maximum length
        // Whether the original length is greater than or equal to the default initial length (16)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // Threshold after expansion = Original threshold x 2
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // The original array length is 0. If the expansion threshold is greater than 0, the threshold is assigned to the initialization length of the node array
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // Map with no arguments, initialized for the first time
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // If the new threshold is 0, the threshold is recalculated
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // The threshold is reassigned
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // Create a new node array
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if(oldTab ! =null) {
        // Migrate the original array data, traverse the original node array
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if((e = oldTab[j]) ! =null) {
                // Fetch the data from the original array and set the data at the corresponding index position of the original array to NULL
                oldTab[j] = null;
                if (e.next == null)
                    // The current node is a separate node, and the pointer to the next node is null
                    // Recalculate the hash value and store it in the new node array
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // Fetch the tree node
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // The hash value of the node is ampersand to the original length, 0 is the low value, not 0 is the high value
                    // Divide the new array into two parts according to the original length. The greater part is the high part and the less part is the low part
                    // Recalculate the linked list in the original array
                    // Low level list head node, low level list end node
                    Node<K,V> loHead = null, loTail = null;
                    // High list head node, high list tail node
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // Low node data processing
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // High node data processing
                            if (hiTail == null)
                                hiHead = e;
                            elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
                    // Data is migrated to the new node array
                    if(loTail ! =null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if(hiTail ! =null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
// Tree node conversion
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    // Low level node
    TreeNode<K,V> loHead = null, loTail = null;
    // High level node
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    // Walk through the tree node, convert the original tree node structure into a linked list structure
    for(TreeNode<K,V> e = b, next; e ! =null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            elsehiTail.next = e; hiTail = e; ++hc; }}// Low list nodes are converted to tree nodes
    if(loHead ! =null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            // The TreeNode Node list is converted to the Node list
            tab[index] = loHead.untreeify(map);
        else {
            // List tree operation
            tab[index] = loHead;
            if(hiHead ! =null) // (else is already treeified)loHead.treeify(tab); }}if(hiHead ! =null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            // The TreeNode Node list is converted to the Node list
            tab[index + bit] = hiHead.untreeify(map);
        else {
            // List tree operation
            tab[index + bit] = hiHead;
            if(loHead ! =null) hiHead.treeify(tab); }}}Copy the code

New tree node: putTreeVal

/ * * * *@paramMap Collection object *@paramTAB node array object *@paramH Hash value of the key *@paramThe key star of the k key-value pair@paramV key value pair value */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<? > kc =null;
    boolean searched = false;
    // Get the root node of the treeTreeNode<K,V> root = (parent ! =null)? root() :this;
    // Walk through the red black tree
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; 
        K pk;
        // Compares the hash value of the newly stored node with the hash value of the current tree node
        if ((ph = p.hash) > h)
            / / the left subtree
            dir = -1;
        else if (ph < h)
            / / right subtree
            dir = 1;
        else
            // If the newly stored node is the same as the current tree node, return the node
            if((pk = p.key) == k || (k ! =null && k.equals(pk)))
            return p;
        else 
            (kc == null && (kc = comparableClassFor(k)) == null)
            // kc is of type k
            if ((kc == null && (kc = comparableClassFor(k)) == null)
                // Compare the type of pk with the type of k, and then compare k with pk
                ||  (dir = compareComparables(kc, k, pk)) == 0) {
                // The current node is a new node
            if(! searched) { TreeNode<K,V> q, ch; searched =true;
                if(((ch = p.left) ! =null&& (q = ch.find(h, k, kc)) ! =null) || ((ch = p.right) ! =null&& (q = ch.find(h, k, kc)) ! =null))
                    return q;
            }
            // Determine whether the new key is in the left or right subtree
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        // Determine whether to traverse the left or right subtree according to dir
        if ((p = (dir <= 0)? p.left : p.right) ==null) {
            // The current p node is a leaf node
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if(xpn ! =null)
                ((TreeNode<K,V>)xpn).prev = x;
            // Save the new node to TAB and insert the tree node in balance
            moveRootToFront(tab, balanceInsertion(root, x));
            return null; }}}// Get the root node
final TreeNode<K,V> root(a) {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            returnr; r = p; }}// Compare k with x
// If x is null or the type of x is different from that of k, 0 is returned; Otherwise return the value of k compared to x
 static int compareComparables(Class
        kc, Object k, Object x) {
     return (x == null|| x.getClass() ! = kc ?0 : ((Comparable)k).compareTo(x));
 }
Copy the code

Treeization: treeifyBin

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // The node array is null and the node array length is less than 64; Perform capacity expansion.
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // Get node e from node array
    else if ((e = tab[index = (n - 1) & hash]) ! =null) {
        // first node of the hd tree
        TreeNode<K,V> hd = null, tl = null;
        // Loop through the list to convert it to a tree node
        // The hd is not a tree. It is still a linked list, but each node type in the list is TreeNode
        do {
            // Convert list E node to tree P node
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                // Record the first node of the tree
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
         // Move the pointer back
        } while((e = e.next) ! =null);
        // Replace the existing list nodes in the node array with tree nodes
        if((tab[index] = hd) ! =null)
            // Convert to a red black treehd.treeify(tab); }}TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
// Convert to a red-black tree
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            inth = x.hash; Class<? > kc =null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0)? p.left : p.right) ==null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // Insert a new node and rotate it left or right to make sure the tree is red-black
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}
Copy the code

The remove method

Delete by key: remove(Object key)

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null.false.true)) = =null ?
        null : e.value;
}
Copy the code

Remove (Object key, Object value)

public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true.true) != null;
}
Copy the code

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // Node array exists, corresponding key is not null
    if((tab = table) ! =null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! =null) {
        Node<K,V> node = null, e; K k; V v;
        // Obtain information about the node to be deleted
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            node = p;
        else if((e = p.next) ! =null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while((e = e.next) ! =null); }}// Delete the node
        if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            returnnode; }}return null;
}
Copy the code

RemoveTreeNode method

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        return;
    int index = (n - 1) & hash;
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if(succ ! =null)
        succ.prev = pred;
    if (first == null)
        return;
    if(root.parent ! =null)
        root = root.root();
    // The root is null
    // movable is true and (root right node is empty or left node is empty or left node is left node is empty)
    if (root == null
        || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) {
        // Remove the tree operation
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if(pl ! =null&& pr ! =null) {
        TreeNode<K,V> s = pr, sl;
        while((sl = s.left) ! =null) // find successor
            s = sl;
        boolean c = s.red; 
        s.red = p.red; 
        p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if((p.parent = sp) ! =null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if((s.right = pr) ! =null)
                pr.parent = s;
        }
        p.left = null;
        if((p.right = sr) ! =null)
            sr.parent = p;
        if((s.left = pl) ! =null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        if(sr ! =null)
            replacement = sr;
        else
            replacement = p;
    }
    else if(pl ! =null)
        replacement = pl;
    else if(pr ! =null)
        replacement = pr;
    else
        replacement = p;
    if(replacement ! = p) { TreeNode<K,V> pp = replacement.parent = p.parent;if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }

    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if(pp ! =null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null; }}if (movable)
        moveRootToFront(tab, r);
}
Copy the code

Disturbance function: tableSizeFor

// Compute a value greater than the current value to the lowest power of 2
// graphic: perturbation function.png
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code

LinkedHashMap

attribute

// Two-way list header
transient LinkedHashMap.Entry<K,V> head;

// The end of the bidirectional list
transient LinkedHashMap.Entry<K,V> tail;

// The hash map of this link is iteratively sorted:
// true for access order,
// false is used for insertion order.
final boolean accessOrder;
Copy the code

Defined data structures

Entry

// A custom structure type that inherits the Node type in HashM
static class Entry<K.V> extends HashMap.Node<K.V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next); }}Copy the code

Initialize the

// No arguments
public LinkedHashMap(a) {
    super(a); accessOrder =false;
}
// Initialize the length
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
// Initialize the length and load factor
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
// Initialize the length, load factor, and type of iteration sort
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
// The parameter is the initialization method of the collection
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(a); accessOrder =false;
    putMapEntries(m, false);
}
Copy the code

Put method and remove method

The same as the put and remove (Object key) methods of HashMap

// Inherit the HashMap put method and remove (Object key) method,
// Override the newNode method,
// the newTreeNode method
// afterNodeAccess,
// afterNodeInsertion method
// visting deremoval,
/ / replacementTreeNode method
Copy the code

NewNode and newTreeNode

// Create a node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
// newTreeNode in putTreeVal
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
     TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
     linkNodeLast(p);
     return p;
 }

// Save the new node to the bidirectional linked list
 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
     LinkedHashMap.Entry<K,V> last = tail;
     tail = p;
     if (last == null)
         head = p;
     else{ p.before = last; last.after = p; }}Copy the code

afterNodeAccess

// Move the current node to the end of the list
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if(accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after =null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if(a ! =null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else{ p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the code

afterNodeInsertion

// Delete the header
// This should be an extended operation
 void afterNodeInsertion(boolean evict) { // possibly remove eldest
     LinkedHashMap.Entry<K,V> first;
     // Evict is false when initialized; True is called when new
     // Determine whether to remove the header
     if(evict && (first = head) ! =null && removeEldestEntry(first)) {
         K key = first.key;
         // Delete a node
         removeNode(hash(key), key, null.false.true); }}protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
Copy the code

afterNodeRemoval

// Delete a node from the bidirectional list
// Delete the deleted nodes in the extra maintained linked list
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
Copy the code

replacementTreeNode

// Replace with a tree node
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}
// Replace SRC with DST
private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) {
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}
Copy the code

traverse

LinkedHashMap maintains an additional two-way linked list to retrieve stored element data in an orderly fashion as it traverses.

Set

HashSet

attribute

// Set set holds the structural type of data
private transient HashMap<E,Object> map;
// The value of key-value in the map object
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

Copy the code

Initialize the

// No arguments
public HashSet(a) {
    map = new HashMap<>();
}
// Specify the initialization length
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
// Specify the initialization length and load factor
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
// specify the initialization length and loadFactor and Boolean values to distinguish the HashSet(int initialCapacity, float loadFactor) constructor
// (This package private constructor is only used by LinkedHashSet.)
// The sequence method creates a LinkedHashMap object to ensure orderliness
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
// The argument is a collection constructor
public HashSet(Collection<? extends E> c) {
    // Determine the maximum length of initialization according to the length of the collection
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1.16));
    // Save the collection to map
    addAll(c);
}

Copy the code

The add method

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
Copy the code

The remove method

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
Copy the code

LinkedHashSet

Initialize the

Int initialCapacity (int initialCapacity, float loadFactor, Boolean dummy);
// Create a LinkedHashMap object to ensure orderliness
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f.true);
}

public LinkedHashSet(a) {
    super(16..75f.true);
}


public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f.true);
    addAll(c);
}
Copy the code