CS253

This file defines the header for each page. An optional "icon" image (I use the textbook):

Replace this with info about this class:

CS253: Problem Solving with C++

Spring 2013

Hash Lab

Links to the various pages for this class:

Wish I could do this: * Schedule

Hash Lab

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

A Hash Template

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.)

Understanding the code

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

Exercises

  1. Add empty() to hset. Make it efficient—don’t just check if size()==0.
  2. Add a hset<double> to main, and insert a series of doubles between 1.0 and 2.0. Observe that it works poorly. Why?
  3. Improve Hasher to hash doubles.
  4. The design of hset_iter is horrible. Discuss.
  5. Note how 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.

For extra fame & glory

  1. Make hset_iter less horrible.

Modified: 2010-11-17T13:00

User: Guest

Check: HTML CSS
Edit History Source
Apply to CSU | Contact CSU | Disclaimer | Equal Opportunity
Colorado State University, Fort Collins, CO 80523 USA
© 2015 Colorado State University
CS Building