Lesson 1

This lesson addresses the following learning goals from Group 9:

• Goal 9A (Hash Function Properties): Describe desirable properties of a hash function.
• Goal 9B (Hash Table Operations): Perform hash table operations by hand.
• Goal 9C (Collision Resolution Strategies): Compare and contrast hash tables with different collision resolution strategies.
• Goal 9D (Hash Table Complexity): Explain the complexities of hash table operations and implications for usage.

Outline

• Before You Start
• Fixing Lookup
• Collisions
• Separate Chaining

We're about to dive into some math. If you need some fresh air first, now's good.

• Expected Number of Comparisons
• Dynamic Table Size
• Interpreting Hash Table Complexities

Nearly done. Maybe get up and stretch.

• Hash Function Properties
• Key Points
• Before You Go…

To receive credit: complete all pages above, then this page will be complete as well (and get a green check emoji at the bottom right of the page).

(When logged in, completion status appears here.)

Go to Parent Page Next Page