Hash Lab                

In this lab, we will look at a simple hashing container. The files are in ~cs253/Lab/Hash.                 

Create a file called recit14.txt, and turn it in for credit.                 

A Hash Template                

In main.cc, we have a program that implements a templated container called hset (for hash set). An hset is much like a set—it takes a single (for now) template argument, that is, the type to be contained.                 

Compile main.cc and run it. Observe that the order of the output is not the same as the order of the input. (At least, for the strings. It’s hard to tell for the random numbers.)                 

Understanding the code                

Look at hset.h, hset_iter.h, and hasher.h, and understand the following:                 

• hset: a vector of lists.
• hset_iter: an iterator class used by hset, containing a reference to the vector, and an integer.
• Hasher: a class that only defines functors.

Exercises                

1. An hset is a vector of lists, and the vector is stuck at size 10. Change that size to be a mandatory second template parameter.
2. Add empty() to hset. Make it more efficient than just size()==0.
3. Add a hset<double> to main(), and insert a series of doubles between 1.0 and 2.0. Observe that it works poorly. Why? How does it even compile?
4. Improve Hasher to hash doubles.
5. The design of hset_iter is horrible.
   1. What is the O( ) of hset_iter::operator* ?
   2. Improve it.
6. Copy your source files to recit14.txt:
           cat hasher.h hset.h hset_iter.h main.cc >recit14.txt
   Inspect your recit14.txt to ensure that it contains what you want.