Hashing

Open any production hash table, any block cipher, any RSA implementation, or any competitive programming problem that ends in "output the answer modulo `10^9 + 7`", and you will find the same machinery underneath: **modular arithmetic**, the math of working with remainders rather than full integers. It is the bridge between number theory and a huge swath of real algorithms. This lesson develops that machinery from first principles. You will revisit the `mod` operation precisely (including its relationship to division and remainders), then prove and use the addition, subtraction, and multiplication rules that let you take `mod` at every step of a long calculation without changing the answer. From there you will implement **fast modular exponentiation** in `O(log n)` time using binary exponentiation, compute **modular inverses** with **Fermat's Little Theorem** when the modulus is prime, and see exactly why hash tables, RSA, and contest problems rely on these tricks to avoid overflow and to invert multiplications. This lesson builds on **Number Theory Fundamentals**, where you learned about primes, divisibility, `gcd`, and the Euclidean algorithm. Modular arithmetic uses all of those: primality lets you apply Fermat, `gcd` decides when an inverse exists, and divisibility underlies every congruence. From here the only foundations topic remaining is **Basic Proof Techniques**, where you will learn the proof tools (induction, contradiction, contraposition) that make the kinds of arguments you have just been waving at fully rigorous.

Two Sum is the canonical example: scan the array once, and for every number `x` ask the data structure whether you have already seen `target - x`. With a list that is `O(n^2)`. With a **Hash Map**, the lookup becomes a single function call and the whole algorithm collapses to `O(n)`. This lesson covers the key-value abstraction, the intuition behind a hash function (a key gets converted to a bucket index by an integer-valued function), what a collision is, and how `get`, `set`, `delete`, and `has` behave in JavaScript's `Map` and Python's `dict`. You will also meet two recurring patterns: counting frequencies and bucketing/grouping by a derived key, both of which appear in dozens of interview problems and real applications such as analytics, caching, and indexing. In **Arrays & Strings**, you saw that searching an unsorted array is `O(n)` because every position is equally plausible. A hash map turns that linear scan into an arithmetic computation that points directly at the right slot, which is the entire reason hash-based lookups dominate practical software. With key-based lookup in hand, **Set Basics** specializes the same machinery to a single question: have I seen this value before?

Python's `dict` uses open addressing with a Robin Hood-inspired probe. Java's `HashMap` switches a bucket from a linked list to a red-black tree once chain length crosses eight. C++ `std::unordered_map` is required by the standard to use chaining. Three production hash tables, three different choices, all defending the same goal: keep expected `O(1)` lookups even as the table fills up. **Hash Table (Advanced)** unpacks the engineering decisions behind those choices. This lesson covers hash function design (division method, multiplication method, universal hashing), the two collision-resolution families (separate chaining and open addressing with linear, quadratic, or double hashing), the load-factor threshold that triggers a rehash, and the amortized `O(1)` cost of dynamic resizing. You will also see how tombstones make deletion correct under open addressing, and why Robin Hood and cuckoo hashing tame worst-case probe lengths. In **Hash Map (Dictionary) Basics**, you used a hash map as a black box; this lesson opens the box and replaces the hand-wave with a quantitative model. **Modular Arithmetic** is the workhorse behind every practical hash function: the `key % m` step that turns an arbitrary integer into a valid bucket index, and the `(h(k) + i*step) % m` formula behind double hashing. Next, **Skip List** answers the same fast-lookup question with a probabilistic, pointer-based design that has no hash function at all and no rehashing step.

Drop a million IDs into a `Set`, ask `set.has(id)` for any one of them, and the answer comes back in expected constant time without any ordering, sorting, or scanning. That single primitive (membership testing) is what makes a **Set** the quiet workhorse behind deduplication, visited-node tracking in graph traversal, and almost every cache-invalidation routine you will read. This lesson covers the uniqueness invariant of a set, the four core operations `add`, `delete`, `has`, and iteration in both JavaScript's `Set` and Python's `set`, and the four classical set-theory operations: union, intersection, difference, and symmetric difference. You will see why a set is implemented as a hash map whose values are unused, and you will practice the visited-set pattern that reappears in BFS, DFS, and cycle detection. In **Hash Map (Dictionary) Basics**, you learned that a hash function maps keys to bucket indices for `O(1)` get and set. A set keeps only the keys, drops the values, and exposes the resulting structure as a pure membership data type. Next, **Trees: Binary Tree Fundamentals** moves from flat unordered collections to hierarchical structures, where parent and child relationships unlock entirely new traversal patterns.

Two Sum was a hard problem in 2010. With a hash map it becomes a six-line interview warm-up: walk the array once, and for each value `x` ask whether `target - x` is already in the map. The same shape, single-pass plus complement lookup, solves "first duplicate," "contains nearby duplicate," "longest substring without repeats," and an entire family of trade-space-for-time problems. **Hashing Techniques** catalogs those patterns. You will work through frequency counting (most/least frequent element, group anagrams via sorted-key trick), the two-sum complement template and its three-sum / four-sum extensions, existence checking and duplicate detection, index mapping where you store positions alongside values, and a first conceptual look at rolling hashes that prepare you for Rabin-Karp later. The lesson also discusses when a hash map is overkill versus when it is the obviously correct tool. In **Hash Map (Dictionary) Basics**, you saw how hashing achieves expected `O(1)` insertion and lookup. This lesson is where that constant-time primitive turns into algorithmic leverage: brute-force `O(n^2)` scans collapse into a single pass that uses the map as an oracle. From here you move into the paid track with **Sorting (Advanced)**, which trades hash-map lookups for divide-and-conquer to break the `O(n^2)` sorting barrier.