Algorithm Science (Summer 2025) - 20 - Hashing I

This video was made as part of a second-year undergraduate algorithms course sequence (Algorithms and Data Structures I and II).

0:00 Introduction
2:22 Pigeons
19:10 Tables
44:01 Compressed Tables
52:57 Hashing
59:34 Hash Tables
1:05:32 Chaining
1:15:00 Uniform Hashing
1:38:22 Dictionaries and Hash Tables
1:44:56 Universal Hashing
1:51:35 String Hashing

The following sources were used while creating the slides.
Algorithm Design by M. Goodrich and R. Tamassia (2002)
Algorithms by R. Sedgewick and K. Wayne (4th edition, 2011)
Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein (4th edition, 2022)
The Art of Computer Programming, Volume III by D. E. Knuth (2nd Edition, 1998)
Full proofs of the theoretical results in this lecture can be found in the sources above as well.

All slides and diagrams are original content (developed in early 2025). The materials used in this video, and the video itself, were prepared without any assistance from generative AI.

As any viewer will quickly realize, these videos were made just like in-person lectures: in one sitting, with no breaks, editing or script. If you find any of this helpful or interesting, please let me know (I really appreciate any other feedback as well).