Helpful Hints

insert() Only Inserts If Value Not Present

Recall from the specification that insert() must enforce the uniqueness of keys. If it is given a key that is already in the table, it should not insert that key.

Strong Suggestion for insert()

Subsequent phases will be much easier if your insert() function calls a private helper function to do the actual insertion after making sure the item isn't already in the table. This approach will give you a private insert() function that inserts something into the hash table without checking whether it's already there. That function will come in useful later.

Also, insert() should use push_front to add new items onto the front of the bucket.

Pick a Simple Hash Function for Testing

For testing purposes, you get to pick the hash function! In hashset-test.cpp, you can define myhash for whatever type(s) you want to test with in the place marked by the comment.

Note that a good hash function gives random-looking values that appear to have no obvious connection to the hashed value. But testing is all about easy-to-follow behavior! So you may not want to use a good hash function when testing.

Instead, you may want to use simple hash functions that cause predictable behavior. We'll discuss this more when you implement the functions that measure the performance of the table.

For now, just know that you don't need to find a fancy, well-behaved hash function. Something very simple that would be a terrible choice for real usage is enough to test the relationships between insert, exists, and the other functions you've already implemented.

Define myhash Before You Include HashSet

If you test with any of the built-in classes of C++ that live in the std:: namespace (such as std::string), your myhash function must be defined before you include hashset.hpp. This requirement is a technical limitation: because myhash(string) is in the top-level namespace, and std::string is in the std namespace, the compiler will not find myhash if you define it after you define HashSet.

We've left a comment in hashset-test.cpp that shows where you should define your myhash function(s).

Iterating Over Buckets and Template Errors

Template error messages can be pretty confusing. Do try to figure out what the compiler is saying (start from the first error message!!!), but if you have a hard time figuring out what the compiler is telling you, don't spend hours scratching your head: ask for help!

One common pitfall is failing to say typename when necessary, which is a particular issue when we are using nested classes with templates, as well as template classes that use template classes. For example, suppose you had written the following templated top-level function to print out any list:

#include <iostream>
#include <forward_list>
#include <string>

using namespace std;

template <typename T>
void printAnyList(forward_list<T>& things){
    for (forward_list<T>::iterator i = things.begin(); i != things.end(); ++i) {
        cout << *i << endl;
    }
}

This code should look clear and correct—to a human. But if you compile this code, you could be faced with the following weird error:

yuck.cpp:8:10: error: missing 'typename' prior to dependent type name 'forward_list<T>::iterator'
    for (forward_list<T>::iterator i = things.begin(); i != things.end(); ++i)
         ^~~~~~~~~~~~~~~~~~~~~~~
         typename
1 error generated.

What you actually need to do is promise that forward_list<T>::iterator will be a type (once the list template is instantiated) by prefixing the offending type with the keyword typename, as in

for (typename forward_list<T>::iterator i = things.begin(); i != things.end(); ++i) {
    cout << *i << endl;
}

This code works, but looks pretty ugly and long-winded. Remember, though, that if you're doing this kind of thing with a class, then your class can have a private type abbreviation (using) to avoid typing this ugly code over-and-over again. You could also use auto i = things.begin(); to say that i should be whatever type that can hold the result of things.begin().

Testing Using printToStream()

If you know the hash function, the number of buckets, and ensure that the final load factor is less than the maximum load factor, all hash-table implementations must print out a hash table that looks the same. So, for example, if you knew that your hash table should produce the output shown above, you could check that output against the string

"[0] bacon\n[1] sausage, avocado\n[2] waffles\n[3] toast\n[4] pancakes\n[5] cheese\n[6] juice, coffee, eggs\n[7] \n[8] tea, steak, tofu\n[9] beans\n"

Additional Sanity Check: hashset-cow-test.cpp

With these functions implemented, you should be able to successfully compile and run hashset-cow-test.

It's a very simple test (it basically just inserts something and checks to see if it exists in the table). But the key is a Cow class rather than a built-in type, so running this test checks to make sure that your table treats its keys properly. If your table performs operations on keys that it shouldn't, you'll probably get compiler errors.