Analysis and relationship of list map set underlying principle

ArrayList LinkedList Vector

The bottom layer of ArrayList is arrays, which provide the function of dynamic size arrays on the basis of arrays, and expand the call System.arrayCopy function.
synchronized is added to Vector method
LinkedList linked list
Lookup: ArrayList is fast, directly subscribed, and LinkedList requires pointer movement
Insert Node: ArrayList needs to be copied, linkedList can modify the pointing.

hashMap LinkedhashMap treeMap underlying structure

Description: Based on jdk1.8 analysis
Class relationships are as follows

HashMap
The bottom layer is array, each array is linked list, the essence is array + linked list
What are the array elements? How to implement linked list?
Node nodes are as follows:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;//
        V value;
        Node<K,V> next;//Link List Realization by next Pointing
 .......

Look at the put method

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Get the corresponding array node below
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // key already exists and is the head of the list of arrays
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                // The tail has not been traversed, indicating that key does not exist at present.
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key already exists
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}


Explain the meaning of transient s:
TransiNode < K, V >[] table; //transient means not participating in serialization operations

1 How to place the corresponding key in the corresponding array?
Actually, the length of the current array is redundant, but in a different way, as follows:
hash & (length-1);
It does not take the length of the hash table and uses bit operations to get the index, which is why it suddenly doubts ~ (PS: the old-fashioned surplus at that time)

The initial capacity and expansion of HashMap are done in the order of 2. If length-1 is converted into binary, all bits must be 1. For example, the third power of 2 is 8, and the binary representation of length-1 is 111. The principle of bitwise and calculation is that two bits are "1" at the same time, and the result is "1", otherwise it is "0". So the H & (length-1) operation is numerically equivalent to taking a module for length, that is, h%length.

What is the resize condition? What did you do? Do you resize or insert the new key first?
capicity capacity, that is, node array size
fractor Load Factor, you can specify the default 0.75
threshold =factor*capacity
Number of node s actually stored in size

insert first and resize later

When size > threshold, resize is needed to expand
resize will reposition all nodes

3 innsert is inserted into the tail or the head?
p.next = newNode(hash, key, value, null);
Tail, you need to first traverse whether it exists, if it does not exist, then insert the tail directly, without needing the pointer to move to the head.

 
public HashMap(int initialCapacity,, float loadFactor)
Initial Capacity: Declares the initial capacity, determines the size of the array, and jointly determines threshold with the load factor
Load Factor: Load factor, default 0.75, and capacity together determine capicity

linkedhashmap

To put and traverse elements in the same order
LinkedHashMap can be thought of as HashMap+LinkedList, which uses both HashMap to manipulate data structures and LinkedList to maintain the sequence of inserted elements.
entry
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry < K, V > before, after; // Compared with HashMap.
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
}
LinkedhashMap's underlying or array + linked list?
Yes, inherit HashMap, so what's the difference in implementation?
For example, LinkedHashmap does not override the put method, but overrides the newNode method, as follows:

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;
}

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;
    }
}


Treemap
What is the underlying structure?
Because the bottom of TreeMap uses a "red-black tree" to save Entry in the collection. So TreeMap adds elements and extracts elements with lower performance than HashMap. When TreeMap adds elements, you need to find the insertion location of the new Entry through a loop, because it consumes performance. When extracting elements, it also requires loops to find the right Entry, which is as performance-intensive as Entry. But that doesn't mean that TreeMap is worse than HashMap. All Entries in TreeMap always keep in order by key according to the specified sorting rules.

Note: A red-black tree is a self-balanced binary search tree, in which the comparison value of each node must be greater than or equal to all nodes in its left subtree, and less than or equal to all nodes in its right subtree. This ensures that the mangrove tree can quickly find a given value in the tree when it operates.

Now let's look at the put(K key,V value) method of TreeMap, which puts Entry into the Entry chain of TreeMap and maintains the ordered state of the Entry chain. The source code is listed below:

public V put(K key, V value) {
      //Define a t to hold the root element
        Entry<K,V> t = root;
        //If t==null, it means an empty list.
        if (t == null) {
        //If the root node is null, the incoming key-value pair is constructed as the root node (the root node has no parent, so the incoming parent node is null).
            root = new Entry<K,V>(key, value, null);
            //Set the size of the set to 1
            size = 1;
            //Modify this time + 1
            modCount++;
            return null;
        }
        // Record comparison results
        int cmp;
        Entry<K,V> parent;
        // Processing of split comparator and comparable interface
        Comparator<? super K> cpr = comparator;
        // Comparator processing, i.e. using customized sorting
        if (cpr != null) {
            // do while implements locating the insertion location of the incoming key pair for root node movement
            do {
                //Entry referenced by t after parent's last loop
                // Records will be mixed with new key-value pairs to be nodes (that is, the parent of the new node)
                parent = t;
                // Use a comparator to compare the size of the key values of parent and insert key-value pairs
                cmp = cpr.compare(key, t.key);
                // Inserted key s are smaller
                if (cmp < 0)
                    t = t.left;
                // The key inserted is larger
                else if (cmp > 0)
                    t = t.right;
                // The key value is equal, replacing and returning the value of the t node (end of put method)
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // Processing without comparator
        else {
            // key throws a NullPointerException exception for null
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            // Similar to do while in if, but in a different way
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // The following operation occurs only if the same key node is not found
        // Create a new node based on the incoming key pair and the "parent node" found
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        // According to the last judgment, confirm whether the new node is the left child or the child of the "parent node"
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // Adjust the tree with new nodes
        fixAfterInsertion(e);
        // Record size and modCount
        size++;
        modCount++;
        // Because the new node is inserted, null is returned
        return null;
    }


Two do in the above program. while is the key algorithm to realize "sorted binary tree". Whenever a program wants to add a new node, it always compares from the root node of the tree, that is, the root node is the current node.

If the new node is larger than the current node and the right sub-node of the current node exists, the right sub-node is used as the current node. And continue the cycle
If the new node is smaller than the current node and the left sub-node of the current node exists, the left sub-node is used as the current node. And continue the cycle
If the new node equals the current node, the new node covers the current node and ends the cycle.
When TreeMap extracts value according to key, the corresponding method of TreeMap is as follows:

public V get(Object key) {
     //Remove Entry according to key
     Entry<K,V> p = getEntry(key);
     //Remove the value contained in Entry
     return (p==null ? null : p.value);
 }


Now we can see that the get(Object key) method is essentially implemented by the getEntry() method. Now let's look at the source code for getEntry(Object key):

final Entry<K,V> getEntry(Object key) {
    // If there is a comparator, return the result of getEntry UsingComparator (Object key)
    if (comparator != null)
        return getEntryUsingComparator(key);
    // The key found is null, and the NullPointerException is thrown
    if (key == null)
        throw new NullPointerException();
    // Instead of a comparator, a comparable interface is implemented
    //Mandatory conversion of key to Comparable interface
    Comparable<? super K> k = (Comparable<? super K>) key;
    // Get the root node
    Entry<K,V> p = root;
    // Traversing the tree from the root node to find the node
    while (p != null) {
        // Compare the key with the key of the current node
        int cmp = k.compareTo(p.key);
        // Key is less than the key of the current node
        if (cmp < 0)
            // p "move" to the left node
            p = p.left;
        // Key is larger than the key of the current node
        else if (cmp > 0)
        // p "move" to the right node
    p = p.right;
        // If the key value is equal, the current node is the node to be looked for.
        else
            // Returns the node found
            return p;
        }
    // If not found, return null
    return null;
}


The getEntry(Object obj) method also makes full use of the sorted binary tree to search for the target Entry. The program still starts from the root node of the binary number. If the searched node is larger than the current node, the program searches for the "right subtree" and the "left subtree" if it is less than. If equal, the specified node is found.

We observed that when the TreeMap adopted custom sorting. In the way of customized sorting, TreeMap uses getEntry UsingComparator (key) method to obtain Entry according to key.

final Entry<K,V> getEntryUsingComparator(Object key) {
    K k = (K) key;
    // Getting Comparator
Comparator<? super K> cpr = comparator;
// In fact, in the get(Object key) that calls this method, we have already judged the case where the comparator is null. Here is the defensive judgement.
if (cpr != null) {
    // Get the root node
        Entry<K,V> p = root;
        // Ergodic tree
        while (p != null) {
            // Get the comparison result of key and the key of the current node
            int cmp = cpr.compare(k, p.key);
            // Find a smaller key value
            if (cmp < 0)
                // p "Move" to the left child
                p = p.left;
            // The key value of the lookup is larger
            else if (cmp > 0)
                // p "Move" to the right node
                p = p.right;
            // The key value is equal
            else
                // Returns the node found
                return p;
        }
}
// The node corresponding to the key value was not found, and null was returned.
    return null;
}


In fact, getEntry() and getEntryUsingComparator() have almost the same idea of implementation. The former is only valid for acquiring natural sort TreeMap, while the latter is valid for customized sort TreeMap.

From the above source code, it is not difficult to see that the implementation of TreeMap tool class is actually very simple. In other words, TreeMap is essentially a "red-black tree" and each Entry is a node.

Set 
The bottom layer of HashSet is Hashmap, value is fixed PRESENT, which is a new Object()
The advantage of TreeSet over HashSet is orderliness.
How does treeset achieve orderliness? The bottom layer of treeset is treemap.
Elements in TreeSet must implement the Comparable interface and override the compareTo() method, which is the method by which TreeSet determines whether elements are duplicated and the order of elements is determined.
For classes defined in Java class library, TreeSet can store them directly, such as String, Integer and so on, because these classes have implemented Comparable interface.
(2) For a custom class, if it is not properly handled, only one instance of that type of object can be stored in TreeSet, otherwise it is impossible to judge whether it is duplicated or not.

LinkedHashSet underlying implementation of LinkedHashMap


Can the set series be modified? How do I remove value?

Tags: less Java

Posted on Tue, 10 Sep 2019 03:54:30 -0700 by XeroXer