Hash maps & sets

O(1) lookups by turning data into an address.

The idea

Finding an item in a list takes O(n) time because you might have to check every single element. A hash table solves this by using a "hash function" to instantly turn the key into a number (an index), and stores the item at that exact index in an array. This gives us O(1) average lookup time.

Sometimes, two different keys hash to the same index. This is a collision. The most common way to handle it is "chaining": storing a linked list of items at that index.

Frequency Map

{ }

Ready to insert words into the hash map.

How it works

A hash map wraps this logic nicely. In Python, dictionaries are implemented as highly optimized hash tables.

def count_frequencies(words):
    counts = {}
    for word in words:
        if word in counts:
            counts[word] += 1
        else:
            counts[word] = 1
    return counts

Cost

Time Complexity O(1) average

Space Complexity O(N)

Insert, delete, and lookup are O(1) on average. In the worst case (e.g. bad hash function where everything collides), they degrade to O(N). Space is O(N) to store N keys.

Watch out for

Unhashable types: You cannot use mutable objects (like lists or other dictionaries in Python) as dictionary keys, because their hash value would change if they are modified.
Worst-case collisions: While rare with built-in string hashing, an attacker who knows your hash function could intentionally feed keys that all collide, causing Denial of Service (O(n) lookups). Modern languages often use randomized hashing to prevent this.