How does HashMap work?

HashMap stores data as key-value pairs. Internally, it uses an array of Nodes (or entries).

When adding a pair:

1. The hash code of the key is computed using hashCode().
2. The index in the array (bucket) is determined by the hash code.
3. If the bucket already contains elements, the key's uniqueness is checked using equals().
4. If the key is unique, the pair is added to the bucket. In case of collisions (different keys with the same hash), a linked list or a balanced tree (red-black tree) is used to store elements in the same bucket.

// Example of a HashMap node
class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // hash of the key
    final K key;    // key
    V value;        // value
    Node<K,V> next; // reference to the next element in the bucket in case of collision

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // ... other methods like getKey(), getValue(), setValue()
}

When retrieving a value by key:

1. The hash code of the key is computed.
2. The index in the array is determined.
3. The search for the key in the corresponding bucket is performed using equals().

Important points: Concurrency: HashMap is not thread-safe. null: Allows storing one null key and multiple null values. Performance: On average, put and get operations work in O(1), but with high collisions, they can degrade to O(n) when using a linked list. Load Factor: When a certain fill percentage is reached, the array is resized (rehashing), which can be resource-intensive.

Method	Average Complexity	Worst-case Complexity
put(key, value)	O(1)	O(n)
get(key)	O(1)	O(n)
containsKey(key)	O(1)	O(n)