introduce

A HashMap is a container whose core function is to determine whether something exists in the container and the expected time to find and add elements is O(1).

Core fields

int capacity; / / capacity
  
double threshold;// Threshold ratio

transient Node<K,V>[] table;// An array of key-value pairs
Copy the code

These are the core parameters in HashMap that affect performance. Capacity indicates the number of elements that can be contained in a HashMap. The product of threshold and Capacity is the capacity threshold. When the number of elements in a HashMap exceeds the threshold, the container will be expanded. The value of threshold is 0.75, which is an empirical value. This value can’t be too high or too low. If this value is set to a large value, it can save space, but can be time-consuming for GET and PUT operations.

The Table array, used to store Key and Value pairs, is the core container of a HashMap.

Ideally, if the Hash function distributes the elements evenly across the table, any query only needs to be done once. For example, if the capacity of a HashMap is 16 and the threshold is 0.75, when the number of elements in the HashMap exceeds 12 (16*0.75), expansion will occur. But the 12 elements are ideally distributed evenly across the array.

Encapsulating classes for key-value pairs

    static class Node<K.V> implements Map.Entry<K.V> {
        final int hash;// The hash value of the key
        final K key;/ / key
        V value;/ / value
        Node<K,V> next;
    }
Copy the code
  • The purpose of a HashMap is to retrieve values by keys, so keys and values are required
  • When hash collisions occur, there needs to be a way to resolve hash collisions. HashMap Hash conflicts are resolved by linked lists, so you need a pointer to the Next node, Next
  • For any one key-value pair element, its position in the table depends on the hash value of the element’s key. The hash value of the key is used to locate the position of the element in the table, and then the key-value pair can be modified or deleted. This requires that the hash value of the “equal” object be the same for the key object.In this case, overriding the equals method requires overriding hashCodeIn order to improve the operation efficiency of HashMap. The object’s hashCode and equals methods are completely unrelated, but since HashMap uses HashCode to locate elements in the table, we just need to start at that location and follow a linked list or red-black tree (when the list has more than a certain number of elements, The linked list is upgraded to a binary tree) to find elements with the same hash and Key values. For example, if the hashcode of “equal” elements is different, then the value of a query based on a key will not fall into the expected bucket position, so we have to traverse all the elements to determine whether the elements are equal according to equals method, which degrades from O(1) to O(n).HashMap essentially requires that objects implement both equals and HashCode methods, essentially to improve the performance of methods like Get \put

Core method

put

Add an element to a HashMap, hash it to its position in the table, and then add it to that position or to the linked list of that position

resize

When the number of elements exceeds a set capacity * threshold, the HashMap expands. In a HashMap, the length of a table is always 2 to the power of n. After expansion, the length of a table becomes 2 to the power of n+1.

Element position in bucket = hashCode & (table.length -1)
Copy the code

Since table.length is 2 to the integer power. Given that an element is in its current position I, after expansion, there are only two cases of the element’s position:

  • i
  • i + capacity

Therefore, during resize, we can split each element of the table into two Pointers corresponding to the above two cases respectively.

If the above method of resize is not applicable, the HashMap must have extra space to expand or shrink

entrySet

The main purpose of entrySet is to provide the caller with a view to access the internal elements of the HashMap. The code is shown below:

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

As you can see, the code is actually just new an EntrySet object. The EntrySet class implements an AbstractSet interface with the following methods:

int size(a);

void clear(a)
  
Iterator<T> iterator(a)
Copy the code

Both are based on fields in a HashMap, so EntrySet simply gives us a view to access elements in a HashMap.