Hash Table
hash-table
Data Structures
Hash Table (Advanced)
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.
Not Started
0%
Code Snippets
Group an Array by a Key
Grouping records by a derived key is one of the most common data-shaping tasks in JavaScript: bucketing users by role, orders by status, logs by date. This snippet shows a portable `Map`-based helper, a plain-object variant, and the modern `Object.groupBy` API that landed in Node 22 and recent browsers. It also covers the multi-key composite-key trick for grouping by tuples like `[city, role]`.
LRU Cache (Map-Backed)
An LRU (Least Recently Used) cache evicts the entry that has been untouched the longest when capacity overflows. The trick that makes both `get` and `put` O(1) is JavaScript's `Map` preserving insertion order. This snippet covers the Map-backed implementation, an explicit doubly-linked-list version that mirrors what other languages need, and a TTL-aware variant that evicts entries that are too old.
Counter for Frequency Counting
`collections.Counter` is the dict-of-counts that every other 'count occurrences' implementation tries to be. It supports increment-by-add, most-common-K, and arithmetic between counters. This snippet covers the basic frequency count, the most-common-K shortcut, and the multiset arithmetic that makes Counter the right choice for inventory math and difference reports.
defaultdict for Implicit Init
`collections.defaultdict` removes the boilerplate of checking-then-initialising before every increment or append. It supplies a default value when a missing key is read, and that default lives in the dict from then on. This snippet covers the bucket-by-key pattern with `defaultdict(list)`, the count pattern with `defaultdict(int)`, and a nested `defaultdict` for two-level groupings.
Community
Design HashMap
Implement a HashMap from scratch using a fixed bucket array with separate chaining; support put / get / remove on integer keys.
Subdomain Visit Count
Aggregate visit counts across every subdomain prefix from a list of count-paired domain strings.
Find the Town Judge
Identify the unique person trusted by everyone but trusts nobody, using in-degree minus out-degree.
Top K Frequent Words
Return the k most frequent words, breaking frequency ties alphabetically and returning results in descending frequency.
Hash Tables: The Most Useful Data Structure
Why hash tables earn their reputation, where collisions and load factor actually bite, and the language-specific quirks (JS Map vs Object, Python dict, Java HashMap) that change the game.
Subarrays with K Different Integers
Count subarrays containing exactly K distinct integers using the at-most-K window trick.
Intersection of Two Linked Lists
Find the node where two singly-linked lists merge using the two-pointer rendezvous trick that runs in O(m + n) time and O(1) space.
Open the Lock
Find the minimum wheel turns to open a 4-digit combination lock while avoiding deadend states.
Find All Duplicates in an Array
Identify every value that appears twice in an array of integers in [1, n], using O(1) extra space via index-negation.
Delete and Earn
Maximize total points earned by picking values, where picking value v deletes v-1 and v+1, by reducing to House Robber on a frequency line.
Fruit Into Baskets
Find the longest contiguous subarray that contains at most two distinct values.
LFU Cache
Implement a Least Frequently Used (LFU) cache with O(1) get and put using a frequency-bucket map plus per-bucket doubly linked lists.