Hash tables are often described as offering "constant time" lookup, insertion, and deletion, but that claim comes with conditions. The O(1) average case depends on a hash function that spreads keys evenly, a load factor that is kept under control, and a collision resolution strategy that does not degenerate. When any of those assumptions breaks down, performance slides toward O(n) — the same cost as scanning a plain array.
In this topic you will work through what actually drives hash table performance: the load factor (the ratio of stored entries to table slots), how often collisions occur, and how chaining and open addressing each respond as the table fills. You will also look at the space side of the trade-off — the extra pointers chaining requires, the empty slots open addressing needs to stay fast, and the amortized cost of resizing and rehashing when the table grows.
As you watch the videos below, keep three questions in mind. First, what operation is being performed at each step, and how many probes or list traversals does it take? Second, how would that count change if the table were nearly full versus mostly empty? Third, what input would force the worst case — and why does that matter for real systems that accept untrusted keys?
A compact overview of hash tables covering how a hash function maps keys to array indices and how the core operations — insert, search, and delete — are carried out. The video is likely to state the expected O(1) average-case cost alongside the O(n) worst case, and to introduce collisions as the reason the two differ. Accompanying Python code is linked in the description for students who want to trace the operations concretely.
Michael Sambol's algorithm videos are known for being tightly scripted and accurate, making this an efficient starting point that frames the time complexity of core operations before you dig into the details of each collision strategy.
This lecture explains separate chaining: when two keys hash to the same index, the entries are stored in a linked list attached to that slot. Expect worked examples showing keys being inserted into buckets, and discussion of how search cost depends on the length of the chain at a given index. The treatment typically connects chain length to the load factor and the expected number of comparisons per lookup.
Gate Smashers covers this material at an exam-preparation level of detail, which maps directly onto the average-case analysis with chaining — the key insight that expected search cost grows roughly in proportion to the load factor.
A longer, step-by-step treatment of linear probing as an open addressing scheme, where collisions are resolved by scanning forward to the next free slot. The extended running time allows for detailed insertion and search examples, and the video is likely to illustrate clustering — the way occupied slots group together and lengthen subsequent probe sequences. Deletion and its complications under probing are commonly addressed in lectures of this kind.
Open addressing degrades much more sharply as the load factor approaches 1 than chaining does, and seeing probe sequences worked out slot by slot makes that divergence concrete rather than abstract.
Together these videos build the foundation for MO3: the first establishes the baseline O(1) average and O(n) worst-case claims for insertion, deletion, and lookup, while the chaining and linear probing videos show exactly why and when performance diverges from constant time as collisions accumulate. They also reinforce MO1 by reviewing how keys are mapped to indices, and MO2 by letting you compare the two resolution strategies side by side on memory use, load factor tolerance, and deletion handling. Because the chaining video treats the same technique required in MO4, it doubles as conceptual preparation for implementing set, get, and remove with separate chaining in your own code.
These videos were chosen from YouTube on October 2, 2026. Each has captions; the player turns them on. Videos on YouTube can be changed or removed — if one no longer plays, tell your instructor. If a player does not appear, use its Watch on YouTube link.