Module: Hash Tables

Analysis of chaining, universal chaining, open addressing, direct address tables, hash functions.

Learning Outcomes

Understand hash tables.

Understand the design and run-time characteristics of hash tables and how they compare to related data structures.


Hash tables: introduction and chaining

Introduction to hash tables

Screencast Suthers 8 min

Hash tables: analysis of chaining

Analysis of chaining

Screencast Suthers 20 min

Hash tables: Hash functions

Examples of hash functions and universal chaining

Screencast Suthers 13 min

Hash table: open addressing

Using open addressing to avoid the overhead of linked lists.

Screencast Suthers 16 min

CLRS 11 - Hash tables

Direct address tables, hash tables, hash functions, and open addressing

Textbook 23 pages

Chapter 6 Notes

Notes on hash tables


Hash tables I

Hash tables and the symbol table problem

Screencast Leiserson 77 min

Hash tables II

Universal hashing

Screencast Leiserson 79 min

Experiential Learning

Analysis of data structures

Consolidate your understanding of data structures