Java HashMap

HashMap stores key/value pairs and uses a key's hash value to locate an entry efficiently. Correct behavior depends on `equals()` and `hashCode()` being consistent for keys.

A Java `HashMap<K,V>` implements the `Map` interface and associates each key with a value. Keys are unique: inserting another value for an existing key replaces the previous value.

When a key is inserted or looked up, the map uses the key's `hashCode()` to determine where to search, then uses `equals()` to distinguish keys that map to the same hash location. Average-case lookup, insertion, and removal are expected to be O(1), although collisions can increase the work required.

A key should obey the `equals()`/`hashCode()` contract: if two objects are equal according to `equals()`, they must return the same hash code. Mutable fields that participate in either method should generally not be changed while the object is being used as a key, because subsequent lookups may no longer find the entry.

`HashMap` permits one `null` key and multiple `null` values. It does not guarantee iteration order, so code should not depend on the order returned by `keySet()`, `values()`, or `entrySet()`.

Key points

• Uses `hashCode()` to narrow where a key is searched and `equals()` to establish key identity.
• Average expected `put`, `get`, and `remove` operations are O(1).
• Keys must satisfy the `equals()`/`hashCode()` contract.
• Keys should generally be immutable with respect to fields used by `equals()` and `hashCode()`.
• `HashMap` permits one `null` key and multiple `null` values.
• Iteration order is not a guaranteed ordering contract.

Interview questions

What is the relationship between equals() and hashCode()?

If two objects are equal according to `equals()`, they must return the same value from `hashCode()`. The reverse is not required: two unequal objects may have the same hash code. Violating this contract can cause a logically equal key to become difficult or impossible to retrieve from a hash-based collection.

How does HashMap find a value for a key?

The map first uses the key's `hashCode()` to determine the relevant region of its internal table. It then compares candidate keys using `equals()` to identify the requested key. This means a hash code narrows the search, but it does not by itself prove that two keys are equal.

What is the average time complexity of HashMap operations?

`get`, `put`, and `remove` are expected to take O(1) time on average under normal hashing assumptions. Collisions can make an individual operation more expensive. The implementation can reorganize its table as it grows, so performance also depends on capacity, load, and the quality of hash distribution.

Why is using a mutable object as a HashMap key dangerous?

If a field used by the key's `equals()` or `hashCode()` changes after insertion, the key may effectively belong to a different lookup location. A later lookup using that same object can therefore fail even though the entry remains in the map. Immutable key types avoid this class of problem and are usually safer.