Lesson 6: Hash maps & frequency counting

Picture a dictionary: you don't read it from the start, you jump straight to the word and get its meaning. That's exactly a hash map (in Python: dict) — a structure of key-value pairs that jumps straight to a key. A 'have I seen this before?' check that takes O(n) by scanning a list becomes nearly i

A hash map is like the index at the back of a book: instead of flipping through every page to find a word (that's a slow 'scan'), you look it up in the index and jump straight to the right page (that's O(1) — instant). The cost? A little extra paper — that is, a bit of extra memory in exchange for a lot of speed.

hash map: A structure mapping a key to a value with O(1) average lookup and insert, by computing a direct address from the key. In Python this is a dict.
set: A duplicate-free collection that checks membership (is an element present) in O(1) average — handy for spotting and removing duplicates.
frequency counting: Counting how many times each value appears in the input using a dict that maps value → counter, in a single O(n) pass.