Hash Lab
In this lab, we will look at a simple hashing container.
The files are in ~cs253/Lab/Hash.
                
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 list
s.
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
- An
hset
is a vector
of list
s, and the vector
is stuck at size 10
. Change that size to be a mandatory
second template parameter.
- Add
empty()
to hset
.
Make it more efficient than just size()==0
.
- Add a hset<double> to
main
, and insert a series of double
s
between 1.0 and 2.0. Observe that it works poorly. Why?
How does it even compile?
- Improve
Hasher
to hash double
s.
- The design of
hset_iter
is horrible.
- What is the O( ) of
hset_iter::operator*
?
- Improve it.