Homework 8: Words That Don't Exist? Let's Hash it Out!
I'm starting a company, and it needs a name! Something that sounds like a word, but isn't… Yet.
Like Kodak. Somebody made that up, and now it sounds like it was always a word.
I bet we could write a program that makes up words. Count up which letters follow which in a list of real words, then roll some imaginary dice to pick out pairs of letters….
Counting things? Meh. Sounds like a lot of counting.
It is! Which is why this homework's hash table is a counter.
In this eighth and final homework, you'll implement your own hash-table class, HashMultiset<T>, which counts how many times each key has been inserted (like Python's Counter). Then you'll use that class to build a program that invents words: words that sound like they belong in a list of English adverbs, or Welsh villages, or company names, but aren't in the list you've fed it.
This assignment lets you practice:
- Analyzing hash functions and choosing the best one for the task.
- Implementing a hash table using separate chaining.
- Using a hash table to count a few hundred thousand things quickly.
The HashMultiset class, and the idea of using it to count things, come from Jonathan Chang's Spring 2026 version of Homework 8. The word generator we're using is a letter-by-letter cousin of the text generator in Chapter 3 of Brian Kernighan and Rob Pike's The Practice of Programming.
Getting Started
This assignment is paired, and your repository belongs to your pair.
You'll use the same pairing as Homework 7 (which came from the pairing board). We've already set up your repository for you; it's named after your group.
- Your group is
group (members ) - Your repository for Homework 8 is
repo - You can see it on the web at https://github.com/hmc-cs70-fall2026/
As usual, both members have push access, so you can work together on whatever machine is most convenient for you.
Clone your repository on the CS 70 server to get started:
git clone https://github.com/hmc-cs70-fall2026/repo .git
- Phase 1: Words That Don't Exist
- Phase 2:
HashMultiset<T>Interface and Stubs - Phase 3: Evaluating Hash Functions
- Phase 4: Constructor, Destructor,
swap,size, andbuckets - Phase 5:
insert,count,contains, andprintToStream - Phase 6: Rehashing
- Phase 7:
HashMultiset<T>Performance Statistics - Phase 8: Inventing Words
- Phase 9: More Fun with Hash Tables (Optional)
- Written Questions
- Check Your Submission
Resources
Grading
This assignment is graded on the following parts:
- Your answers to the written questions.
- Your code, based on
- The autograder results (i.e., your program builds without warnings, passes
cpplint, has the right files, passes our tests of your hash table and your word generator, and your tests catch our deliberately broken versions). - A code review of its clarity and style by the course staff.
- The autograder results (i.e., your program builds without warnings, passes
- Your planning images (for completeness, not correctness).
- Your written justification of your choice of hash function.
- Bonus points for any optional bonus work you choose to do.
Each question shows its points beside it, on its own page, so there's only one place to look. Your grade for the assignment is the percentage of its points you earned, which is what the gradebook shows.
(When logged in, completion status appears here.)