CMSC 341Spring 2013
Project 4


Wednesday, May 1, 2013


11:59 pm on Tuesday May 14



The purpose of this project is to give you significant exposure to Hash Tables. You will be conducting experiments with probing hash tables using linear, quadratic and double hashing. You will be asked to analyze the data you collect and compare the data with the expected theoretical results.


In this project, you will be inserting randomly generated integers into three hash tables. For one hash table, you will use linear probing for collision resolution. For another you will use quadratic probing. For the third hash table, you will use double hashing. You will be collecting data about clustering and probing in hash tables.

Your program will attempt to insert N unique random integers into the hash tables, reporting the collected data on a specified interval (after every INTERVAL insertion attempts). For example, with N = 1000 and INTERVAL = 200, you will attempt to insert 1000 integers, and report data after attempting to insert 200, 400, 600, 800 and 1000 integers. See the sample output for recommended organization of the data. You may assume that N is a multiple of INTERVAL.

Throughout this project description, "N" will refer to the number of attempted insertions into the hash table; "K" will refer to the key being inserted; "I" will refer to the probe number; and "M" will refer to the hash table size. These definitions are the same as those used in class.

Your program will accept the following command line arguments (in this order)
  1. the name of a file which contains unique random integers separated by whitespace.
  2. N-- the total number of random integers to attempt to insert (e.g. 1000)
  3. INTERVAL -- the interval (number of attempted insertions) for reporting data (e.g. 200)
  4. M - the size of the hash table
  5. R - the largest prime less than M

After attempting to insert INTERVAL integers, your program will report the following data:
  1. the total number of attempted insertions (successful and unsuccessful) so far
  2. the value of lambda (successful insertions / table size)
  3. the total number of probes so far (for both successful and unsuccessful insertions)
  4. the average number of probes needed to insert (successfully or unsuccessfully) an integer into each hash table
  5. the maximum number of probes needed to insert (successfully or unsuccessfully) an integer into each hash table
  6. the number of successful insertions
  7. the number of unsuccessful insertion attempts
  8. the number of clusters in the hash table
    A cluster is defined to be 1 or more consecutive occupied slots in the hash table. When counting clusters, do not "wrap around".
  9. the maximum cluster size in each hash table
  10. the average cluster size in each hash table

Requirements, Notes, and Hints

  • Code for the author's hash table class can be checked out using CVS. Feel free to modify the file as needed.
  • Note that the author's code uses quadratic probing for collision resolution. This project requires three different collision resolution methods, so you'll need to add the other two collision resolution methods.
  • The author's code automatically rehashes the hash table when the table is 50% full. This code must be removed so that we can study the effects that filling the hash table.
  • The author's code also initializes the hash table to a size equal to the next prime after the integer passed to the constructor as M. You'll need to disable this code as well, so that it makes a table of size M, where M is passed as a parameter. FYI, the value of M we use will be a prime.
  • An insertion is "unsuccessful" if h(k, i) == h(k, j) for some j not equal to i. I.e. you ever attempt to store the key into the same slot twice. You should check this condition after each probe so that we all count unsuccessful insertions in the same way.
  • Your code must handle (try/throw/catch) any exceptions thrown by the author's code or by your own classes.
  • All "average" values should be printed with 2 decimal places of precision.
  • Probing Functions
    1. For all probing, use the function
      h( K ) = K mod M
    2. For linear probing, use the function
      h( K, I ) = ( h( K ) + I ) mod M
    3. For quadratic probing, use the function
      h( K, I ) = ( h( K ) + I2) mod M
    4. For double hashing, use the function
      h ( K, I ) = ( h( K ) + I * h2( K ) ) mod M
      where h2 ( K ) = R - ( K mod R )
      and where R is the largest prime that is smaller than the table size.

    Sample Output

    Mr. Winner has prepared some sample output for this project. The relevant files include:

    Kevin says that he wrote (and debugged) this program quickly, so if your output differs significantly from his and you are certain that you are right, please see him in order to discuss any discrepancies.

    The following sample output is for formatting and organizational purposes only. No real data is provided.
    In this example, N = 1000 (the total number of insertions to attempt) and INTERVAL = 100 (the reporting frequency). Your output will consist of three tables like the one shown below
    .There will be separate tables for linear probing, quadratic probing and double hashing.

    In the tables, the columns are defined as follows


    For the "Inserts" columns:

    For the "Probes" columns:

    For the "Cluster" columns:
    			Linear Probing Analysis (Table size = xxxxxx)                 
                      --- Inserts ---   ------- Probes -------    ----- Clusters ----- 
         N   lambda  success  failed     total    avg    max     number   avg     max  
       200     0.xx    xxxxx  xxxxxx   xxxxxxx  xxx.xx  xxxxx    xxxxxx  xxx.xx  xxxxx
       400     0.xx    xxxxx  xxxxxx   xxxxxxx  xxx.xx  xxxxx    xxxxxx  xxx.xx  xxxxx 
       600     0.xx    xxxxx  xxxxxx   xxxxxxx  xxx.xx  xxxxx    xxxxxx  xxx.xx  xxxxx   
       800     0.xx    xxxxx  xxxxxx   xxxxxxx  xxx.xx  xxxxx    xxxxxx  xxx.xx  xxxxx 
      1000     0.xx    xxxxx  xxxxxx   xxxxxxx  xxx.xx  xxxxx    xxxxxx  xxx.xx  xxxxx

    Submit Tools

    There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

    If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check. Make sure they work. Do this before the due date.

    Grading and Academic Integrity

    Project grading is described in the Project Policy handout.
    Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.