Hashing turns a key into an index, but the raw output of a hash function is almost never in the range your table actually occupies. Compression is the step that maps that arbitrary integer into a valid slot number between 0 and M-1, and the most common compression strategy is the modulo operation: index = hash(key) % M. It is cheap, easy to reason about, and — when M is chosen well — spreads keys fairly evenly across the table.
The interesting part is the "chosen well." Because modulo keeps only the remainder, any structure in your keys can survive compression and pile up in a few buckets. Table sizes that are powers of two throw away all but the low-order bits; table sizes that share factors with patterns in your data create regular collisions. Prime table sizes are the standard defense, and load factor (n/M) tells you when the table itself needs to grow. This topic also asks you to recognize the failure cases of plain modular compression, which motivates alternatives such as multiplicative and universal hashing.
As you watch, keep three questions in mind: where exactly in the pipeline does compression happen, what assumptions about the key distribution is a given method making, and what happens to lookup cost as the load factor climbs. The videos below move from a plain-language introduction to hashing, to a concrete look at how hash tables use the modulo step, to a more formal alternative that explains why modulo alone is not always enough.
A short, example-driven introduction to what hashing is and why it is used in data structures, from the widely followed Gate Smashers channel. It should establish the basic pipeline — key, hash function, index, table — and work through a simple example of mapping keys into buckets, which is typically done with a division/modulo style hash.
It is the right starting point if you need the vocabulary and the mental picture before analyzing compression, and it gives you a concrete example of reducing a large key space to a small index range.
Professor Kevin Wortman presents multiplicative hashing as a method for building the universal hash functions used in hash table implementations. The treatment is more formal than the other two and should explain how a multiplier and a modulus are combined, and why randomized or universal families give distribution guarantees that a fixed function cannot.
This is the contrast case for the topic: it shows the limitations of relying on a single simple modular hash and gives you the vocabulary to evaluate trade-offs between simplicity and distribution quality.
An animated walkthrough of the hash table data structure, covering how keys are converted to indices and stored in an array of buckets. Expect to see the modulo step applied explicitly against a chosen table size, along with the collisions that arise when two keys compress to the same slot.
Dinesh Varyani's visuals make the modulo-to-index mapping and the resulting bucket occupancy easy to see, which directly supports the subtopics on reducing key space, distribution uniformity, and how table size choice shows up in practice.
Together the three videos trace the arc of the module's outcomes. The Gate Smashers and Dinesh Varyani videos build the definitions and the concrete mechanics — what a hash function does, how the modulo step produces a valid index, and what a collision looks like — supporting MO1 and the modular-arithmetic portion of MO2. Watching bucket occupancy fill in as keys are inserted gives you the intuition behind MO3, where table size and load factor determine how uniform the distribution stays. The multiplicative hashing video pushes into MO4 by presenting a more sophisticated alternative, letting you compare efficiency, uniformity, and implementation complexity rather than defaulting to modulo in every situation. Note that the folding, digit extraction, and mid-square methods named in MO2 are covered in the module readings rather than in these videos.
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.