Hash Map & Hashing

    DSA · Beginner

    Definition

    A hash map stores key-value pairs and uses a hash function to find a bucket for each key in average O(1).

    Hash maps turn many O(n²) brute-force problems into O(n) solutions.

    Diagram

    key 'apple'hash → 3bucket[3]value 5

    Flowchart

    Take keyCompute hash(key)Map to bucket indexStore or look up valueHandle collisions

    Example: Two Sum with a hash map

    def two_sum(nums, t):
    seen = {}
    for i, x in enumerate(nums):
        if t - x in seen:
            return [seen[t - x], i]
        seen[x] = i
print(two_sum([2,7,11,15], 9))

    Output: [0, 1]

    Complexity

    Average O(1) insert/search · Worst O(n)

    Key points

    • Collisions handled by chaining or open addressing
    • Load factor triggers resizing
    • Keys must be hashable

    Interview questions

    What is a collision?

    Two keys mapping to the same bucket.

    Count frequencies of characters?

    Loop once and increment counts in a dictionary.

    More DSA topics

    ArraysLinked ListStackQueue