JAVA Collections: HashMap Deep Parsing (Version comparison)

Today first for the JAVA collection series of source code to open a head, also try to use a different way, different Angle to read the source code, to learn some ideas in the source code. HashMap as one of the most commonly used collections; Before JDK1.7, there was a lot of debate about the efficiency of queries with large amounts of data, and about thread safety. This article takes a look at two different versions of the JDK1.7 and 1.8 source code to explore how HashMap is optimized and how thread-safety issues arise.

jdk1.7

The main differences between HashMaps in 1.7 and 1.6 are:

Joined the JDK. Map. Althashing. The threshold of the JDK parameter is used to control whether new hash algorithm used in expansion of type String.
Move table initialization from the 1.6 constructor to the PUT method.
The tranfer method in 1.6 nulls the nodes of the old table (there are multithreading problems), which was removed in 1.7.

define

public class HashMap<K.V> extends AbstractMap<K.V>
        implements Map<K.V>, Cloneable.Serializable
Copy the code

HashMap extends from AbstractMap and implements Map, Cloneable, and Serializable. Since the Serializable interface is implemented, that is, Serializable, as you can see in the introduction of member variables below, table[] uses the transient modifier, which is available to most classes in the collection framework. After referring to relevant information and combining the explanations of various gods on the Internet, here is a summary:

Reduce unnecessary null serialization

The amount of data stored in tables and elementData is usually smaller than the length of the array (expansion mechanism), and this becomes more obvious when more data is stored (more data, with higher probability of collisions, and also with expansion). If the default serialization is used, places where there is no data will be stored, resulting in a lot of unnecessary waste.
Compatibility of different VMS

Since different virtual machines may produce different Code values for the same hashCode, if the default serialization is used, the element position will remain the same after deserialization, but since the hashCode value is different, the index of the bucket will be different, which is obviously not desirable

The serialization of the HashMap does not use the default serialization method, but uses a custom serialization method by overwriting the writeObject method.

Member variables

Default initial capacity is 16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
Copy the code

The maximum capacity

static final int MAXIMUM_CAPACITY = 1 << 30;
Copy the code

Default load factor

static final float DEFAULT_LOAD_FACTOR = 0.75 f;
Copy the code

Empty table instance

static finalEntry<? ,? >[] EMPTY_TABLE = {};Copy the code

Table, an array of entries

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Copy the code

Size: indicates the total number of key-values in the map

 transient int size;
Copy the code

Threshold: When the total number of key-values in the map reaches this threshold, the capacity is expanded

int threshold;
Copy the code

The load factor

final float loadFactor;
Copy the code

Number of times modified (fial-Fast mechanism)

transient int modCount;
Copy the code

Alternative hashing (a new hash algorithm of String is used) default threshold

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
Copy the code

Controls whether to rehash. Default is 0, as explained later

transient int hashSeed = 0;
Copy the code

Inner class, initialized after VM starts

jdk.map.althashing.threshold
Copy the code

The JDK argument, which defaults to -1. If set to 1, the new hash algorithm of type String is enforced

private static class Holder {

        /**
         * Table capacity above which to switch to use alternative hashing.
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD;

        static {
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold")); int threshold; try { threshold = (null ! = altThreshold) ? Integer.parseInt(altThreshold) : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; //disable alternative hashing if- 1if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }

                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); } ALTERNATIVE_HASHING_THRESHOLD = threshold; }}Copy the code

The internal structure

Entry, 4 attributes (key, value, next node, Hash value)

static class Entry<K.V> implements Map.Entry<K.V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /** * Creates new entry. */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey(a) {
            return key;
        }

        public final V getValue(a) {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if(! (oinstanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if(k1 == k2 || (k1 ! =null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if(v1 == v2 || (v1 ! =null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode(a) {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString(a) {
            return getKey() + "=" + getValue();
        }

        /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */
        void recordAccess(HashMap<K,V> m) {}/** * This method is invoked whenever the entry is * removed from the table. */
        void recordRemoval(HashMap<K,V> m) {}}Copy the code

The constructor

No parameter constructor, default initial capacity 16, load factor 0.75

public HashMap(a) {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
Copy the code

A parameter constructor with a default load factor of 0.75

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the code

Two-parameter constructor that sets the capacity and load factor

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;
    threshold = initialCapacity;
    init();
}
Copy the code

Init method, template method, if you have a subclass that needs to be extended you can do it yourself

void init() {}Copy the code

The main method

The hash method

final int hash(Object k) {
    int h = hashSeed;
    // The default is 0, if not 0 and the key is String, the new hash algorithm will be used (avoid touching
    // Optimization of collision?)
    if (0! = h && kinstanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // Move the high value to the low value so that changes in the high value affect the hash result
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
Copy the code

The hash value is used to determine the position in the table, and the multiple of length 2 is used to expand the HashMap based on the multiple of 2. As can be seen from the above, the indexFor method is implemented with a calculated code value and the array length -1 bit operation. Length minus one is all one when converted to binary (length 16, len-1=15, binary = 1111), so the advantage of this setting is that each bit of the calculated code will affect the determination of the index position, the purpose of which is to better hash the data into different buckets.

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}
Copy the code

Put method

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {  
    // If the table is not initialized, initialize the table with the capacity threshold
        inflateTable(threshold);
    }
    if (key == null)   
    PutForNullKey is called if the key value is null, so hashMap can insert key and value null values
        return putForNullKey(value);
    // Computes the hash value of the key
    int hash = hash(key); 
    // Calculates the hash position of the table, that is, the table subscript
    int i = indexFor(hash, table.length); 
    for(Entry<K,V> e = table[i]; e ! =null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        // If hash values are equal and (key values are equal or key's equals method is equal),
        // return the old value
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            returnoldValue; }}// Change the word count to +1
    modCount++; 
    // If no key is found, insert key
    addEntry(hash, key, value, i);  
    return null;
}
Copy the code

RoundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
Copy the code

Gets the smallest multiple of 2 greater than or equal to the given value

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1)? Integer.highestOneBit((number -1) < <1) : 1;
}
Copy the code

HighestOneBit: Returns the largest multiple of 2 less than the given value

public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1); // Override the highest 1 bit to the second, so that the first two bits are 1
    i |= (i >>  2); // The first four digits are all 1
    i |= (i >>  4); / /...
    i |= (i >>  8); / /...
    i |= (i >> 16); // The highest and lowest bits are both 1
    return i - (i >>> 1);   // Returns the highest bit of 1 and all other bits of 0
}
Copy the code

The initHashSeedAsNeeded method controls whether to rehash the transfer expansion

final boolean initHashSeedAsNeeded(int capacity) {
        //hashSeed defaults to 0, currentAltHashing is false
        booleancurrentAltHashing = hashSeed ! =0;
        / / with reference to the above the Holder class static block, JDK. Map. Althashing. Threshold default - 1, Holder. ALTERNATIVE_HASHING_THRESHOLD for Integer. MAX_VALUE, If the JDK map. Althashing. Threshold set the other negative, can change the Holder. The ALTERNATIVE_HASHING_THRESHOLD values, if not more than an Integer. MAX_VALUE, UseAltHashing as true
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {    // Change the value of hashSeed to make hashSeed! =0, String will use the new hash algorithm for rehash
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }
Copy the code

HashMap puts key-value pairs with null keys into table[0]

private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e ! =null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0.null, value, 0);
        return null;
    }
Copy the code

Insert a new key-value pair

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null! = table[bucketIndex])) { resize(2 * table.length);   // If the number of key-value pairs reaches the threshold, expand the capacity
            hash = (null! = key) ? hash(key) :0;   // The hash value of null is 0
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
Copy the code

Insert a new Entry into the head of the table[bucketIndex]

An explanation of the head insertion method: By default, data inserted after the insertion will be queried more frequently.

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
Copy the code

The get method

public V get(Object key) {
    if (key == null)
        return getForNullKey(); // If the key is null, go directly to table[0]
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}
Copy the code

private V getForNullKey(a) {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e ! =null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
Copy the code

The getEntry method is relatively simple. It first finds the hash position in the table and then loops through the list to find an Entry. If there is an Entry, it returns null

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null)?0 : hash(key);
    for(Entry<K,V> e = table[indexFor(hash, table.length)]; e ! =null;
         e = e.next) {
        Object k;
        if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
            return e;
    }
    return null;
}
Copy the code

The remove method

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

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null)?0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];    // The previous node
    Entry<K,V> e = prev;    // The current node

    while(e ! =null) {
        Entry<K,V> next = e.next;   // Next node
        Object k;
        if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)  // If it is equal, it is the head node that needs to be deleted. The head node is directly equal to next
                table[i] = next;
            else
                prev.next = next;   // If it is not the head node, the next of the previous node equals the next node, delete the current node
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}
Copy the code

Resize method, capacity expansion (key)

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if(oldCapacity == MAXIMUM_CAPACITY) {// If the capacity has reached MAXIMUM_CAPACITY, do not expand the capacity. Threshold = integer. MAX_VALUE;return; } Entry[] newTable = new Entry[newCapacity]; // the initHashSeedAsNeeded method determines whether to recalculate stringshashValue transfer (newTable, initHashSeedAsNeeded (newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }Copy the code

Transfer method to transfer all nodes from the old table to the new table

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null ! = e) { Entry<K,V> next = e.next;if (rehash) { e.hash = null == e.key ? Zero:hash(e.key); } /** * recalculatehashThe position of the value in the new table (data from a linked list in the old table * is split into two new tables at most, */ int I = indexFor(e.hash, newCapacity); */ int I = indexFor(e.hash, newCapacity); // insert into newTable e.next = newTable[I]; newTable[i] = e; e = next; }}}Copy the code

jdk1.8

HashMap 1.8 has many changes compared to 1.7

The Entry structure becomes a Node structure, and the hash variable has a final declaration, meaning it cannot be rehash
The method of inserting nodes is changed from ab initio to tail insertion
Red black trees were introduced
TableSizeFor method, hash algorithm, etc

define

public class HashMap<K.V> extends AbstractMap<K.V>
    implements Map<K.V>, Cloneable.Serializable
Copy the code

Member variables

Default initial capacity

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
Copy the code

The maximum capacity

static final int MAXIMUM_CAPACITY = 1 << 30;
Copy the code

The default load factor is 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75 f;
Copy the code

Link list to red black tree threshold 8

static final int TREEIFY_THRESHOLD = 8;
Copy the code

Red black tree spinner list threshold 6

static final int UNTREEIFY_THRESHOLD = 6;
Copy the code

The minimum table capacity required to transform a linked list into a red-black tree is 64, that is, when the length of the linked list reaches the critical value 8 for red-black tree transformation, if the table capacity is less than 64, the linked list will not be transformed into a red-black tree, but will be expanded to reduce the length of the linked list

static final int MIN_TREEIFY_CAPACITY = 64;
Copy the code

Table, Node array

transient Node<K,V>[] table;
Copy the code

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

Total number of nodes

transient int size;
Copy the code

Modify the number of times

transient int modCount;
Copy the code

Capacity threshold

int threshold;
Copy the code

The load factor

final float loadFactor;
Copy the code

structure

The Node structure implements Entry, and the hash value is declared final and no longer mutable, i.e. the rehash operation in 1.7 does not exist

static class Node<K.V> implements Map.Entry<K.V> {
    final int hash;
    final K key;
    V value;
    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;
    }

    public final K getKey(a)        { return key; }
    public final V getValue(a)      { return value; }
    public final String toString(a) { return key + "=" + value; }

    public final int hashCode(a) {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false; }}Copy the code

The constructor

public HashMap(a) {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the code

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
Copy the code

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

The Map constructor calculates the required capacity and then inserts the node by calling putVal

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

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0 F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        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

TableSizeFor method: Returns the actual initialized table capacity (must be a multiple of 2) given the initialized table capacity value. This method is optimized and more concise than 1.7.

static final int tableSizeFor(int cap) {
    int n = cap - 1;    Cap = 1; cap = 1; cap = 1; cap = 1
    n |= n >>> 1;   // Move right 1 bit, perform the or operation, and then assign the value to n so that the next bit of the highest 1 becomes a 1
    n |= n >>> 2;   // Move the 1 of the top 2 bits right to cover the values of the next 2 bits, i.e. the top 4 bits are all 1
    n |= n >>> 4;   // Move 4 bits to the right...
    n |= n >>> 8;   // Move 8 bits to the right...
    n |= n >>> 16;  // Move 16 bits to the right...
    If cap<=0, return 1; if >MAXIMUM_CAPACITY, return MAXIMUM_CAPACITY; otherwise, the last n+1 operation returns a multiple greater than or equal to the minimum cap multiple of 2
    return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code

The main method

The hash algorithm is simplified by simply shifting the high 16 of hashCode() down to xOR

static final int hash(Object key) {
    int h;
    return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

Put method

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

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @paramValue the value to put * onlyIfAbsent If the value is true, the value is inserted only when the value does not exist. If the value exists, the original value * is not changed@param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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)
        // If table is null or length is 0, call resize (no separate /// initializer)
        n = (tab = resize()).length;
        // I = (n-1) & //hash] Computs the hash position in the table. If the header is null, insert it directly
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // If key exists, assign it to e
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // If it is a tree node, call putTreeVal
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {// loop over TAB [I = (n-1) & //hash], binCount counts the length of the list to determine whether to convert to a tree //hash
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {// If the key is not found, insert it directly
                    p.next = newNode(hash, key, value, null);
                    // -1 for 1st, if the length reaches 8, convert to tree structure
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break; p = e; }}if(e ! =null) { 
        If onlyIfAbsen//t is true and the original value is null, the value will be replaced. Otherwise, the original value will not be changed
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e); //LinkedHashMap is overwritten to use
            return oldValue;
        }
    }
    ++modCount; // Number of changes +1
    if (++size > threshold) // If the size reaches the capacity expansion threshold, expand the capacity
        resize();
    afterNodeInsertion(evict);  //LinkedHashMap
    return null;
}
Copy the code

The get method

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

GetNode method is very simple, (n – 1) & calculation key hash value corresponding table subscript, find list, first determine head node, then loop through, if the head node is tree node, called getTreeNode method of tree node

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) {
        if (first.hash == hash && // Determine the first node first((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        if((e = first.next) ! =null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            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 remove method

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

/**
 * Implements Map.remove and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @paramMatchValue if true only remove if value is equal // If true, value is equal *@param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
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;
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) ! =null) {// Find the corresponding head node
        Node<K,V> node = null, e; K k; V v;
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))// Determine the head node first
            node = p;
        else if((e = p.next) ! =null) {
            if (p instanceof TreeNode)  // If it is a tree, call the tree's getTreeNode method
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {  // loop linked lists
                do {
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while((e = e.next) ! =null); }}if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) { // If matchValue is true, value must be equal to delete the node
            if (node instanceof TreeNode)   // Delete the tree node
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p) // If it is a head node, the next node of the head node is assigned to the head node
                tab[index] = node.next;
            else    // Assign the next node of the current node to the next node of the previous node.
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node); // Empty method, LinkedHashMap overridden with
            returnnode; }}return null;
}
Copy the code

Resize method (capacity expansion)

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
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 the old table is already initialized
        if (oldCap >= MAXIMUM_CAPACITY) {   // No further expansion is required
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // If the capacity is greater than or equal to 16 and *2 is smaller than the upper limit, expand the capacity by 2. The capacity of the new table is equal to the old table *2, and the new threshold is equal to the old threshold *2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // Initialize the table. The parameter constructor assigns the capacity to be initialized to threshold
        newCap = oldThr;
    else {               // If there is no specified capacity, 16 is initialized by default. The threshold is 16*0.75=12
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes"."unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    /** * If there is a value in the old table, you need to recalculate the value in the new table * hash & (oldCap*2-1) to calculate the position in the new table, Hash & (oldCap-1) in the previous table and hash & (oldCap-1) + oldCap in the later table * hash & oldCap == 0 is the first result,! Theta equals 0 is the second result */
    if(oldTab ! =null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if((e = oldTab[j]) ! =null) {
                oldTab[j] = null;
                if (e.next == null)  // The head node is null, which is directly assigned
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // Tree node processing
                    ((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 {    // loop linked lists
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // The list assigned to the previous table is placed in a linked list
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {  // The ones assigned to the back table are placed in a linked list
                            if (hiTail == null)
                                hiHead = e;
                            elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
                    if(loTail ! =null) {   // Put it in the new table
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if(hiTail ! =null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
Copy the code

Multithreading security issues

HashMap is not thread-safe

In JDK1.7, when two threads perform an insert operation at the same time, the second thread overwrites the insert operation of the first thread and the data inserted by the first thread is lost. In JDK1.8, the same problem occurs when two threads acquire the same node and assign the new key-value pair to next, overwriting the previous one.
In JDK1.7 and JDK1.8, when map capacity is expanded, the next value of nodes may change, resulting in the actual key value, but the read operation returns NULL.
In 1.7, when two threads perform capacity expansion operations at the same time, an infinite loop of the linked list may occur, resulting in the following process:

Now there is a map:
Thread 1 performs expansion operation, executes transfer method, and blocks after assigning nodes E and next.

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null! = e) { Entry<K,V> next = e.next;Copy the code

Thread 2 expands and completes the expansion, creating newTable2.
At this point, the connection between node E and next is as shown in the figure above. If thread 1 continues to execute, the execution process is as follows:

int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
Copy the code

e = next;
Entry<K,V> next = e.next;
Copy the code

inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; ```java ! [](https://user-gold-cdn.xitu.io/2018/1/20/1611330db7c085de? w=668&h=444&f=png&s=149071)
```java
e = next;
Entry<K,V> next = e.next;
Copy the code

int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
Copy the code

e = next;
Copy the code

The linked list then forms an infinite loop.

The transfer method in 1.8 has been changed and the linked list is no longer inverted, so it will not cause an endless loop.

conclusion

The structure of a HashMap, the main method
Difference between 1.7 and 1.8
The section on red black trees is added later

Welcome to pay attention to my studio and friends (https://juejin.cn/user/2770425031440103) no.

glmapper_2018

JAVA Collections: HashMap Deep Parsing (Version comparison)

jdk1.7

define

Member variables

The internal structure

The constructor

The main method

Put method

The get method

Resize method, capacity expansion (key)

jdk1.8

define

Member variables

structure

The constructor

The main method

Put method

The get method

The remove method

Resize method (capacity expansion)

Multithreading security issues

conclusion

Related Posts

How to optimize the database paging query method in a scenario with hundreds of millions of data

A Python tool commonly used by system administrators is recommended

Learning hongmeng OS to write a page jump function