Module: Hash Tables

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

Prerequisite Modules

Hash Tables

Introduction to the Hash Table and Map abstract data types.

Learning Outcomes

Design, implement, and characterize the behavior of the hash table data structure, including:.

Use of open addressing.
Characterizing run-time complexity.
Use of skip lists and chaining.

Readings

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

Notes

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

Homework