“This is the 17th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Introduction to the

Implementation relation of HashMap in Map system:

A HashMap is what we call a hash table. Hash table representation: juejin.cn/post/705658…

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

HashMap extends to AbstractMap, and implements Map, Cloneable, Serializable interfaces that support copy-able and Serializable operations.

The underlying implementation of HashMap is the == array + linked list + red-black tree ==. To deal with conflicts, use the linked address method, which is the combination of array and linked list. Each array element has a linked list structure. When the data is hashed, the array subscript is obtained, and the data is placed on the linked list of the corresponding subscript element.

The initial capacity of the hash table is 16, the maximum capacity is 1,073,741,824 (1<<30, 2^30^), and the load factor is 0.75. The capacity of the HashMap must be 2^ N ^. If the length of the list exceeds 8 with the same hash value, it is converted from the list to a red-black tree.

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

    /** * 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;
Copy the code

A constructor

HashMap is also one of the most commonly used Map constructs. There are several constructors in HashMap, as follows:

HashMap(int initialCapacity, float loadFactor)

Construct an empty HashMap with the specified 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);
    }
Copy the code

HashMap(int initialCapacity)

Construct an empty HashMap with the specified initial capacity and default load factor (0.75).

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

HashMap()

Construct an empty HashMap with a default initial capacity and a default load factor (0.75).

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

HashMap(Map<? extends K, ? extends V> m)

Constructs a new HashMap with the same mapping Map specified. The HashMap has a default load factor (0.75) and an initial capacity large enough to accommodate mappings created in the specified Map.

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

HashMap.Node

The backbone of a Map set is an Entry array. An Entry is a basic unit of a Map. Each Entry contains a key-value pair.

Node is a static inner class in a HashMap that implements the Map.Entry interface. A Node is an Entry. Node is defined in a HashMap as follows:

    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

Commonly used method

int size()

Returns the number of key-value mappings in this hash table.

    public int size(a) {
        return size;
    }
Copy the code

boolean isEmpty()

Returns true if this hash table does not contain key-value mappings.

    public boolean isEmpty(a) {
        return size == 0;
    }
Copy the code

V get(Object key)

Returns the value mapped to the specified key.

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

boolean containsKey(Object key)

Returns true if this map contains the mapping for the specified key.

    public boolean containsKey(Object key) {
        returngetNode(hash(key), key) ! =null;
    }
Copy the code

V put(K key, V value)

Associates the specified value with the specified key in this mapping.

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

void putAll(Map<? extends K, ? extends V> m)

Copies all mappings of the specified map to this map.

    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }
    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

V remove(Object key)

Removes the mapping for the specified key from the map, if it exists.

    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

void clear()

Delete all mappings from the map.

    public void clear(a) {
        Node<K,V>[] tab;
        modCount++;
        if((tab = table) ! =null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null; }}Copy the code

boolean containsValue(Object value)

Returns true if this map maps one or more keys to the specified value.

    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if((tab = table) ! =null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for(Node<K,V> e = tab[i]; e ! =null; e = e.next) {
                    if((v = e.value) == value || (value ! =null && value.equals(v)))
                        return true; }}}return false;
    }
Copy the code

Set keySet()

Returns the Set view of the keys contained in this map.

    public Set<K> keySet(a) {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
Copy the code

Collection values()

Returns the Collection view of the values contained in this map.

    public Collection<V> values(a) {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }
Copy the code

Set<Map.Entry<K,V>> entrySet()

Returns the Set view of the mapping contained in this map.

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
Copy the code

V getOrDefault(Object key, V defaultValue)

Returns the value mapped to the specified key, or if this mapping does not contain the key mapping, returns defaultValue.

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

V putIfAbsent(K key, V value)

Associates the specified key with the given value and returns NULL if it is not already associated (or mapped to NULL), otherwise returns the current value.

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

boolean remove(Object key, Object value)

Deletes the entry only if the specified key is currently mapped to the specified value.

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

boolean replace(K key, V oldValue, V newValue)

The entry for the specified key can only be replaced if it is currently mapped to the specified value.

    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if((e = getNode(hash(key), key)) ! =null&& ((v = e.value) == oldValue || (v ! =null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }
Copy the code

V replace(K key, V value)

An entry with a specified key can only be replaced if the target maps to a value.

    public V replace(K key, V value) {
        Node<K,V> e;
        if((e = getNode(hash(key), key)) ! =null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }
Copy the code

Object clone()

Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned.

    public Object clone(a) {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this.false);
        return result;
    }
Copy the code