Hash Maps

The most useful data structure in computing

A hash map (also called hash table, dictionary, or associative array) stores key-value pairs and offers average O(1) lookup, insertion, and deletion. It is the backbone of caches, databases, config systems, and almost every object you have ever used in JavaScript or Python.

The core idea

You run the key through a hash function, which converts it into an integer. That integer is mapped to a slot (a bucket) in an internal array:

index = hashFunction(key) % arrayLength
buckets[index] → the value

Because computing the hash and indexing into an array are both constant-time operations, the whole lookup is O(1) on average.

Collisions

Two different keys can hash to the same bucket — a collision. There are two classic resolution strategies:

• Chaining — each bucket holds a linked list of entries. A collision just appends to the list.
• Open addressing — on collision, probe for the next free slot (linear probing, quadratic probing, or double hashing).

// Chaining example
bucket[7] → [(k1, v1)] → [(k9, v9)]   // two keys hashed to 7

Load factor and rehashing

The load factor is entries / buckets. As it rises, collisions become more frequent and lookups slow down. When it crosses a threshold (commonly 0.75), the map allocates a larger array and re-inserts every entry — this is rehashing.

Rehashing is amortized O(1): it happens rarely, and the cost is spread across all the cheap operations that came before. This is why hash maps are described as O(1) "on average" rather than worst case.

Why worst case is O(n)

If every key collides into the same bucket, the hash map degenerates into a linked list and lookups become O(n). A good hash function distributes keys uniformly to prevent this — which is why adversarial inputs that target a known hash function are a real security concern (hash flooding attacks).