HashMap is based on the hash table implementation of the Map interface. The performance of insertion and query operations is constant. The capacity and load factor can be set through the constructor to adjust performance.

Hash table: Given a table M, there exists a function f(key). For any given key value, substituting it into the function yields the address of the record containing that key in the table. Then M is called a hash table, and f(key) is called a hash function. In HashMap, the hash table is implemented using an array.

Capacity: The length of the hash table array.

Load factor: The number of entries currently stored in the hash table divided by capacity. The default load factor used by HashMap is 0.75.

HashMap is a key-value pair structure. Keys in HashMap cannot be duplicated (null is allowed), while values can be duplicated. In Java, for a class to work correctly as a key in HashMap, it must implement both the hashCode() and equals() methods.

HashMap uses equals() to determine if the current key is the same as an existing key in the table. It uses hashCode() to generate a hash code. The hashCode() method is the hash function.

A correct equals() method must satisfy the following five conditions:

• Reflexivity: For any x, x.equals(x) must return true.
• Symmetry: For any x and y, if x.equals(y) returns true, then y.equals(x) must also return true.
• Transitivity: For any x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) must also return true.
• Consistency: For any x and y, if the information used for equality comaprisons in the objects has not changed, then multiple calls to x.equals(y) should consistently return the same result.
• For any non-null x, x.equals(null) must return false.

HashMap uses hashing to determine how to store keys for faster lookup.

First, let's see how HashMap represents a key-value pair object.

Map.java

public interface Map<K, V> {
    interface Entry<K, V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        // ......
    }
    // ......
}

In Map.java, the Entry<K, V> interface defines a key-value pair. The concrete implementation is defined by the implementation class of Map.

HashMap.java

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

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

        EntryNode(int hash, K key, V value, EntryNode<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; }

        public final int hashCode() {
            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 instanceof Map.Entry<?, ?> entry)) return false;
            return Objects.equals(key, entry.getKey()) &&
                   Objects.equals(value, entry.getValue());
        }
    }
    // ......
}

HashMap is based on a hash table. In Java, an array represents the hash table. Hashing stores the key information (i.e., Map.Entry<K,V> objects) in the array. Hashing generates a number from the key object, which is used as an index in the array. This number is the hash code.

When calling the put method of HashMap, first, the hash code is calculated to get the array index. Then the specified index position in the array is checked for an existing value (Map.Entry<K,V>). If no value exists, the key-value pair is wrapped into a Map.Entry<K,V> object and stored at that position. If a value exists, it compares whether the current key already exists. If it does, the value is replaced; if not, the new key-value pair is added to the end of the linked list by setting the next field of the last Map.Entry<K,V> node.

When calling the get method of HashMap, again the hash code is calculated to get the array index. The position is queried. If no value exists, null is returned. Otherwise, the linked list of Map.Entry<K,V> nodes is traversed until the corresponding key is found and its value returned.