Chapter 5: Hash tables

Introduction

The grocery-store price lookup example compares search speeds and motivates the need for hash tables.

• Produce price lookup speeds: Explain why looking up a produce price takes O(n) time by scanning an unsorted book, O(log n) time with binary search on sorted entries, and why the chapter seeks an O(1) lookup instead.
  Why it matters: The speed comparison explains what problem hash tables are introduced to solve.

Key terms: simple search, binary search, O(n), O(log n), O(1), hash functions

5.1 Hash functions

The section explains how a hash function and an array form a hash table that stores and retrieves values by key, while noting that real mappings are rarely perfect.

• Hash function mapping requirements: Explain that a hash function maps a string, meaning any sequence of bytes, to a number. Describe why the same input must always produce the same output and why, when used with an array, the output must be a valid index.
  Why it matters: A repeatable, usable index is what makes storing and later finding an item possible.
• Hash table storage and lookup: Trace how a hash table combines a hash function and an array: hash a key to choose a slot for its value, then hash that key again to retrieve the value without searching the array. Identify the grocery names as keys and prices as values.
  Why it matters: This explains why you can request a price by its name rather than search through the stored prices.
• Perfect mapping limitation: Distinguish the example’s perfect one-to-one mapping from the usual case, where different items may map to the same slot and other slots remain empty.
  Why it matters: It keeps the simple grocery example from being mistaken for a guarantee about every hash table.

Key terms: hash function, strings, indexes, hash table, array, keys, values, perfect hash function, one-to-one mapping, collisions

5.2 Use cases

5.3 Using hash tables for lookups

The section shows how hash tables support lookups by mapping a key to a value, using a phone book and DNS as examples.

• Phone Book Key Lookups: Explain how a hash table can store phone numbers under people’s names and retrieve a number by looking up a name.
  Why it matters: This is the basic lookup pattern behind the section’s examples.
• Website Address DNS Lookups: Describe the section’s DNS example: a web address is translated to an IP address, and a hash table can store that mapping in a DNS cache.
  Why it matters: It shows that the same lookup idea applies beyond a personal phone book.

Key terms: hash table, mapping, key, lookup, DNS resolution, IP address, DNS cache

5.4 Preventing duplicate entries

The section shows how a hash table can track who has voted, prevent repeat votes, and avoid repeatedly scanning a long list.

• Duplicate vote prevention: Describe how to use a hash table to prevent duplicate votes: check whether a person's name is present, reject them if it is, and otherwise record the name and let them vote.
  Why it matters: Checking before recording a voter is what keeps the same person from being allowed to vote twice.
• Fast duplicate checks: Explain why a hash table is preferable to a long list for checking whether someone has already voted.
  Why it matters: The speed difference explains why the example uses a hash table rather than a list of voters.

Key terms: hash, hash table, voted, list, simple search, duplicates

5.5 Using hash tables as a cache

This section explains how caching reuses previously prepared web pages and how a hash table can store them by URL.

• Caching repeated page requests: Explain why a website caches a page that many visitors request and what benefits this provides.
  Why it matters: It explains why saving a reusable response helps both visitors and the server.
• URL keyed cache lookup: Trace how a website uses a hash table to serve a requested page from its cache or prepare and save it when absent.
  Why it matters: It shows how a hash table lets a site find and reuse the right saved page.

Key terms: caching, login page, hash, cache, page URL, page data

5.6 Recap

5.7 Collisions

The section explains what hash-table collisions are, how a linked list can handle them, and why unevenly distributed keys slow lookups.

• Collision and overwrite risk: Explain that a collision occurs when two keys are assigned the same array slot, and that simply storing the second value there would overwrite the first.
  Why it matters: Collisions explain why assigning a slot is not, by itself, enough to store every key safely.
• Linked lists at shared slots: Describe the section’s simple collision workaround: start a linked list at a slot shared by multiple keys, then search that list for the requested key.
  Why it matters: This workaround preserves entries that would otherwise overwrite one another, while adding work to some lookups.
• Key distribution and lookup speed: Explain why mapping many keys to one slot slows the hash table and why spreading keys more evenly keeps the linked lists shorter.
  Why it matters: The distribution of keys determines whether collision handling stays a small cost or dominates lookups.

Key terms: collision, keys, slot, hash function, linked list, collisions, linked lists

5.8 Performance

This section explains why hash tables are fast on average, how their worst-case performance differs, and why avoiding collisions matters.

• Constant-Time Average Performance: Explain that hash-table operations take O(1) time on average: their time stays roughly the same as the table grows, rather than being literally instantaneous.
  Why it matters: Constant time explains why hash tables are useful for quick lookups even as they grow.
• Worst-Case Performance And Collisions: Distinguish average-case from worst-case hash-table performance, including the comparison with arrays and linked lists. State that avoiding collisions is important to avoid the O(n) worst case, and name a low load factor and a good hash function as the two stated requirements.
  Why it matters: The average-case speed is useful only if the table avoids the collisions associated with poor performance.

Key terms: average case, O(1), constant time, worst case, O(n), collisions, load factor, hash function

5.9 Load factor

This section defines hash-table load factor, explains when and how to resize a table, and states the performance trade-off.

• Hash table load factor: Explain that load factor measures how full a hash table is by comparing the number of items with the number of array slots, and interpret what a value greater than 1 means.
  Why it matters: Load factor gives you a way to tell when a hash table is getting too full.
• Resizing a crowded table: Describe when the section recommends resizing and how to do it: create a larger array, typically twice the size, and reinsert the items using the hash function. Explain why lowering the load factor helps.
  Why it matters: Resizing helps keep a growing table from suffering more collisions.
• Cost of occasional resizing: State the section’s performance claim about resizing: it is expensive, so it should not happen too often, but hash tables still take O(1) when the cost is averaged out.
  Why it matters: An occasional expensive resize does not undo the section’s overall performance claim.

Key terms: load factor, slots, resizing, hash function, collisions, O(1)

5.10 A good hash function

The section explains that a good hash function spreads keys across a hash table and asks readers to judge distributions for different sets of strings.

• Even hash distribution: Explain why a good hash function spreads values across the array rather than grouping them in a few slots.
  Why it matters: Distribution gives you a way to judge a hash function by what happens to the keys.
• Distribution for given keys: Apply the distribution criterion to the exercise’s string keys and candidate hash functions. Explain why a rule that spreads one set of keys may group another.
  Why it matters: Testing the rule against the actual keys reveals collisions that the rule’s name alone would not show.

Key terms: hash function, distribution, collisions, slot, hash functions, good distribution, index, keys

5.11 Recap

Recaps how hash tables are built, why they are fast, and what they are useful for.

• Hash table construction and collisions: Explain that a hash table combines a hash function with an array, and that minimizing collisions and resizing when the load factor exceeds 0.7 help preserve its performance.
  Why it matters: These are the main factors the recap connects to keeping a hash table effective.
• Fast hash table operations: Describe the speed of hash-table search, insertion, and deletion, and state the performance assumption the recap gives for Python’s hash tables.
  Why it matters: Speed is a central reason to use a hash table, but the constant-time claim is about the average case.
• Hash table uses and availability: Describe how hash tables model relationships between items, cache data, and catch duplicates, and note that a programming language normally provides an implementation.
  Why it matters: These uses explain why hash tables appear often in everyday programs.

Key terms: hash function, array, collisions, load factor, resize, average-case performance, constant time, search, insert, delete