A, HashTable

Hash table, which is simpler than hashMap structure, does not involve red black tree, directly use a linked list to resolve hash conflicts.

If we look at its fields, it’s similar to a hashMap in that it uses a table to hold elements

private transient Entry<? ,? >[] table; private transient int count; private int threshold; privatefloat loadFactor;
private transient int modCount = 0;
Copy the code

It has no constant fields, and the default values are directly reflected in the constructor. Let’s look at the no-parameter constructor:

public Hashtable() {this (11, 0.75 f); }Copy the code

1. The get () method

Get value based on key

public synchronized V get(Object key) { Entry<? ,? > tab[] = table; // Compute the subscript inthash = key.hashCode();
    int index = (hash& 0x7FFFFFFF) % tab.length; E =e.nextfor(Entry<? ,? > e = tab[index] ; e ! = null ; e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {
            return(V)e.value; }}return null;
}
Copy the code

2. The put () method

Like the get() method, the table is iterated over and addEntry() is called to add.

public synchronized V put(K key, V value) {
    if(value == null) { throw new NullPointerException(); } Entry<? ,? > tab[] = table; inthash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; // If it already exists, override and return the old valuefor(; entry ! = null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            returnold; }} // Add addEntry(hash, key, value, index);
    return null;
}
Copy the code

addEntry()

private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<? ,? > tab[] = table;if(count >= threshold) {// If the size exceeds the threshold, expand the table. // Rehash the tableif the threshold is exceeded
        rehash(a); tab = table;hash = key.hashCode();
        index = (hash& 0x7FFFFFFF) % tab.length; } // Add @suppressWarnings ("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}
Copy the code

Notice the trick here, just put the new node in the head, so there’s no problem whether there’s a node behind it or not

protected Entry(int hash, K key, V value, Entry<K,V> next) {
    this.hash = hash;
    this.key =  key;
    this.value = value;
    this.next = next;
}
Copy the code

Second, a HashMap

1. Introduction to constant fields

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; Static final int MAXIMUM_CAPACITY = 1 << 30; Maximum capacity value static finalfloatDEFAULT_LOAD_FACTOR = 0.75 f; Static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; static final int UNTREEIFY_THRESHOLD = 6; Static final int MIN_TREEIFY_CAPACITY = 64; static final int MIN_TREEIFY_CAPACITY = 64; // Specifies the minimum capacity of the table when data in the bucket is stored in a red-black treeCopy the code

Fields:

transient Node<K,V>[] table; // Storage trunk, node array TRANSIENT Set< map. Entry<K,V>> entrySet; transient int size; // Transient int modCount; //The next size value atwhichto resize (capacity * load factor). int threshold; // The size of the next expansion, finalfloatloadFactor; // Load factorCopy the code

2. Constructor

2.1 Commonly used no-parameter constructions:

The default constructor assigns a value directly to the load factor, no other operations, and all other fields are default.

// Constructs an empty <tt>HashMap</tt> with the default initial 
// capacity (16) and the default load factor (0.75).
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the code

2.2 Constructor with initializing container size and load factor:

First determine the correctness of the passed argument and then assign the value.

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);
}
Copy the code

2.3 Construction method with set:

Pass in a Map collection and initialize it by calling the PUT method.

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
Copy the code

As you can see from the above code, the table is not initialized in the constructor; the actual table initialization is done on the PUT operation.

3. Add

3.1 the put ()

Is an entry method that actually calls putVal(), which computes the value of the key using the hash() method

public V put(K key, V value) {
    return putVal(hash(key), key, value, false.true); } // XOR operation to ensure that storage locations as evenly distributed as possible. static final inthash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

The specific putVal() method is long

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; N indicates the length of the tableif((TAB = table) = = null | | (n = TAB. Length) = = 0) / / container initialization n = (TAB = the resize ()). The length; // Use the resize() method to get the allocated space.if ((p = tab[i = (n - 1) & hashTAB [I] = newNode(TAB [I] = newNode())hash, key, value, null); // Encapsulate value into a new nodeelse{// Resolve the conflict Node<K,V> e; K k; // Note that p is assigned to the secondifInside, it represents the node where the conflicting location resides. If the new incoming node and the current nodehashIf it is the same as key, proceed nextif (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p;else ifE = ((TreeNode<K,V>)p).puttreeval (this, TAB,hash, key, value);
        else{// List based insertsfor (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))break; p = e; }} // Update the currently passed value to the current node. Returns the previous oldValueif(e ! = null) { // existing mappingfor key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e);returnoldValue; } } ++modCount; // Change times +1,if(++size > threshold) // Space size. If the space exceeds the threshold, expand resize(). afterNodeInsertion(evict);return null;
}
Copy the code

The key method involved: the resize() method, which returns the newly allocated space.

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; Int oldCap = (oldTab == null)? 0 : oldTab.length; Int oldThr = threshold; Int newCap, newThr = 0;if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            returnoldTab; } // Double the capacityelse if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed inThreshold, the constructor specifies the threshold newCap = oldThr;else{// Initialize oldCap=0,oldThr=0 newCap = DEFAULT_INITIAL_CAPACITY; // Default size, 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // Default calculation method, 16*0.75,12}if(newThr == 0) {// Initialization thresholdfloat ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // Assign the newly calculated value to @suppressWarnings ({"rawtypes"."unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // Reallocate space. table = newTab; // Space assignment after expansion (at this point, space is still empty)if(oldTab ! = null) {// If the old space is not empty, then element transfer is requiredfor(int j = 0; j < oldCap; ++j) {Node<K,V> e;if((e = oldTab[j]) ! OldTab [j] = null;if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            elsehiTail.next = e; hiTail = e; }}while((e = next) ! = null);if(loTail ! = null) { loTail.next = null; newTab[j] = loHead; }if(hiTail ! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } }return newTab;
}
Copy the code

4. The Node structure

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; / / nodehashFinal value K key; // Save the key value V value; Node<K,V> next; // Next node.... }Copy the code

Note the difference between a hashMap, which is bidirectional, and a LinkedList, which is unidirectional.

5. The get () operation

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value; // The code content is here}Copy the code

Call the getNode() method to compute the hash(key) value and obtain the node using the hash

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if((tab = table) ! = null && (n = tab.length) > 0 &&(first = tab[(n - 1) &hash])! = null) {// First check arrayhashLocation gets the first Nodeif (first.hash == hash&&((k = first.key) == key || (key ! = null && key.equals(k))))returnfirst; // If the first node is not, then the next node may be in the form of a linked list, or may be a red black treeif((e = first.next) ! = null) {if(First instanceof TreeNode) // If it is a red-black tree, get it by getTreeNode()return ((TreeNode<K,V>)first).getTreeNode(hash, key); // In the form of a linked list.do {
                if (e.hash == hash&&((k = e.key) == key || (key ! = null && key.equals(k))))return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
Copy the code

The acquisition of linked list form is relatively simple, red black tree acquisition, we put in the following red black tree for separate introduction.

Three, TreeMap

TreeMap differs from the previous two maps in that instead of using a hash table, it works directly with a red-black tree, whose fields hold only the root node

private final Comparator<? super K> comparator; Private TRANSIENT Entry<K,V> root; // Root node private TRANSIENT int size = 0; private transient int modCount = 0;Copy the code

1.get()

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}
Copy the code

getEntry()

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if(comparator ! = null)return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while(p ! = null) { int cmp = k.compareTo(p.key); // Left and right splitif (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
Copy the code

**2.put() ** Involves red-black tree operations, so the code is longer

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
 
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if(cpr ! = null) {do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while(t ! = null); }else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        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); } Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
Copy the code

3.remove()

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        returnnull; V oldValue = p.value; deleteEntry(p); // The actual methodreturn oldValue;
}
Copy the code

Conclusion:

A HashMap behaves more like a combination of TreeMap and HashTable.

The last

Thank you for reading here, after reading what do not understand, you can ask me in the comments section, if you think the article is helpful to you, remember to give me a thumbs up, every day we will share Java related technical articles or industry information, welcome to pay attention to and forward the article!