HashMap

HashMap is a data structure that stores key-value pairs and provides fast retrieval of values by their keys. It uses a hash function to compute an index into an internal array, called buckets, from which the value can be found. If multiple keys collide and map to the same bucket, the entries are stored in a secondary structure within that bucket, such as a linked list or a tree.

Typical operations include put(key, value), get(key), remove(key), and containsKey(key). On insertion, the key’s hash is computed and the value is placed in the corresponding bucket. On lookup, the hash is recomputed and the bucket is searched for an entry with an equal key. Time complexity is usually constant on average for these operations, assuming a good hash function and low collision rate; worst-case performance degrades to linear time.

Hash maps rely on correct key equality semantics, such that two keys considered equal map to the same bucket and are stored as equivalent entries. In languages like Java, this is enforced by implementing proper hashCode and equals methods for key objects.

To maintain performance, hash maps resize when the load factor—the ratio of stored entries to the number of buckets—exceeds a threshold. Resizing expands the bucket array and rehashes entries, which reduces collisions at the cost of a temporary slowdown during the operation.

Variants and related structures include LinkedHashMap, which preserves insertion order, and ConcurrentHashMap, which provides thread-safe access. In different languages, similar structures may be called dictionaries, maps, or hash tables.