Hashing for Speed

Why a hash map turns an O(n) scan into an O(1) average lookup: buckets and hash functions explained plainly, frequency counting, the one-pass two-sum, set membership and de-duplication, plus the gotchas - unhashable keys, worst-case collisions, and unordered results.

1. Why Hash Maps Are Fast Why a hash map looks up a key in O(1) average time while scanning a list is O(n): the hash function turns a key into a bucket index so you jump straight to where the value lives instead of checking every item.
2. Frequency Counting & Two-Sum Two everyday hash-map patterns: counting occurrences with a dictionary, and the classic two-sum solved in a single O(n) pass by remembering what you've already seen - no sorting, no nested loop.
3. Sets, Membership & Dedup The set as a hash map with keys but no values: O(1) membership tests, de-duplication that keeps first-seen order, finding the first repeat, and the gotchas - unhashable keys like lists, worst-case collision slowdown, and why set iteration order is not guaranteed.