CS253: Problem Solving with C++
Spring 2013
Hash Lab
In this lab, we will look at a simple hashing container. The files are in ~cs253/pub/Labs/HashLab.
In main.cc, we have a program that uses
the hset (for hash set) template.
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.)
Look at hset.h, hset_iter.h, and hasher.h, and understand the following:
hset: it’s a vector of lists.
hset_iter: it’s a reference to the vector, and an integer.
Hasher: it’s a class that only defines functors.
empty() to hset. Make it efficient—don’t just
check if size()==0.
main, and insert a series of doubles
between 1.0 and 2.0. Observe that it works poorly. Why?
Hasher to hash doubles.
hset_iter is horrible. Discuss.
hset takes a second, optional, argument that
specifices a hashing class. Create your own class (probably
by copying Hasher), modify it to hash differently,
and use it in main.
hset_iter less horrible.
