Interpretation of HashMap source code (1)

1. Preface

                              . Let's start reading the source code of HashMap.

2. Inheritance and implementation of HashMap classes

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

Through the above code, we know that HashMap inherits AbstractMap, implements Map, Cloneable and Serializable interfaces

3. Constants in the HashMap class

    private static final long serialVersionUID = 362498820763181265L;//Serialization of ID
    /**
     * The default initial capacity must be a multiple of 2, in this case 16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 <<4;

    /**
     * The maximum capacity must be a multiple of 2 and less than 30 times of 2
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The default load factor is 0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
    * When the number of boxes in the HashMap bucket reaches 8, the
    * The data structure of the box is transformed from linked list to red black tree
    */
    static final int TREEIFY_THRESHOLD = 8;
    /**
    * Threshold value of conversion from tree to linked list
    * When the capacity of HashMap is expanded, when the number of nodes in the tree is less than 6, the tree will be transformed into a linked list
    */
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
    * The minimum capacity of the barrel that may be treelized, at least 4 * treeify_treehold,
    * Avoid the conflict between the expansion and tree threshold.
    * Only when the capacity of the table reaches 64 can it be treelized
    */
    static final int MIN_TREEIFY_CAPACITY = 64;
      /**
     * Table, structure of array implementation
     */
    transient Node<K,V>[] table;

    /**
     * Save cached entrySet
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * HashMap Number of key value pairs present in
     */
    transient int size;

    /**
     * HashMap Number of times the structure has been modified
     */
    transient int modCount;

    /**
     * Next resized value, capacity * load factor
     *
     * @serial
     */
    int threshold;

    /**
     * Hash Table Load factor of
     *
     * @serial
     */
    final float loadFactor;

4. Data structure in HashMap

The underlying implementation of HashMap is mainly based on arrays and linked lists, and of course, red black trees. When dealing with conflicts, the method of combining linked list and red black tree is applied. For specific implementation, please see the following picture:

We know that the data stored in HashMap is stored in the data structure of entry. Entry is the storage node of HashMap.
The specific JDK source code is as follows:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//final type
        final K key;   //final type
        V value;
        Node<K,V> next;
        /**
        * Node constructor
        */
        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()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        /**
        * Calculate HashCode
        * It is generated by exclusive or of hashcode of key and hashcode of value.
        */
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        /**
        * For node comparison, the address is the same, and the Key and Value are the same.
        */
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

5.HashMap constructor

There are four constructors for HashMap, as follows:

    /**
    * Default constructor, load factor is 0.75 by default
    */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    /**
    * Constructor initializes initial 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;
        this.threshold = tableSizeFor(initialCapacity);
    }
    /**
    * Constructor initialization initial capacity
    */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    /**
    * Constructor, copy Map to construct HashMap
    */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    //Take on the above approach
    /**
     * Implements Map.putAll and Map constructor.
     *
     * @param m the map
     * @param evict false´╝îWhen it was first constructed
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            //Determine whether the original table is empty, and initialize parameters
            if (table == null) { // pre-size
                //Calculate the length of the required table
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    //Setting threshold
                    threshold = tableSizeFor(t);
            }
            //Over threshold for capacity expansion
            else if (s > threshold)
                resize();
            //Traverse the Map to insert the Map node and enter the HashMap
            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);
            }
        }
    }

Keywords: less JDK

Added by Andy-H on Sun, 05 Apr 2020 21:45:04 +0300