Unit 10: Hashing

This unit covers fundamental hash tables

• hash functions
• chaining hashing
• linear probing hashing
• universal hashing

Material

• slides

• lecture notes

• Animationen:
  • Balls-and-bins model
     
• Video 10-0 (2026-06-24, 8:27): Hashing
  
• Video 10-1 (2026-06-24, 12:25): Hash-Funktionen
  
• Video 10-2 (2026-06-24, 7:23): Vom Hash zum Array-Index
  
• Video 10-3 (2026-06-24, 17:06): Chaining Hashing
  
• Video 10-4 (2026-06-24, 15:37): Linear Probing Hashing
  
• Video 10-5 (2026-06-24, 8:09): Hashing im Kontext
  
• Video 10-6 (2026-06-24, 11:30): Universal Hashing
  

Further sources

This unit mostly follows

• Sedgewick & Wayne, Algorithms, 4th Edition

More on the universal hashing part can be found in

• Morin. Open Data Structures

---

Unit 9  ⋅  Syllabus  ⋅  Unit 11