Hash Tables
Overview
Hash tables are also data structures that can be used to implement finite sets and mappings. Their worst-case performance is not very good, and their analysis is complicated — but they work extremely well in practice (especially when used to represent a set or mapping that does not change very much) and they can be proved to have very good “expected” performance under certain assumptions.
Lecture #13: Hash Tables — Part One
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
- Supplement — Average-Case Analysis for Hash Tables
with Chaining:
[ PDF ]
- Questions for Review: [ PDF ]
Lecture Presentation
Reading Exercise #3: Hash Functions — Static Hashing
Lecture #14: Hash Tables — Part Two
Required Reading
- Lecture Notes:
[ PDF ]
[ Video ]
-
Supplement — Proofs of Claims from the Lecture Notes:
[ PDF ]
- Questions for Review: [ PDF ]
