Lesson 5.1
Sets and Maps as Abstractions
A set stores membership without duplicates; a map stores key-to-value associations. Both are specifications, implementable by hashing or by a tree.
Lessons and exercises
Lookup by key instead of by position. Hashing is the first place where average and worst case diverge sharply, which makes stating the case a required part of every answer.
Lesson 5.2
Hash Functions
A hash function maps a key to a bucket. A good one spreads keys evenly, which is exactly the assumption behind constant average lookup.
Lesson 5.3
Collision Resolution
Chaining hangs a secondary structure off each bucket; open addressing probes for another slot. Linear probing suffers primary clustering, where occupied runs lengthen future probes.
Lesson 5.4
Load Factor and Resizing
Load factor is entries divided by buckets, and rising load predicts more collisions. Implementations resize past a threshold, rehashing every key.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic