Timing Double Hash and Open Hash objects

Getting started:

Design a double hash class as described here: (more detail in textbook)

 

 

class DoubleHash
{
public:
    static const int CAPACITY = TABLE_SIZE;        //size of the table
    DoubleHash( );                      //CTOR

    bool insert(const T& entry);         //insert entry; false if overwriting.
    bool remove(int key);                //remove this key

    bool is_present(int key) const;      //is this key present?
    bool find(int key, T& result) const; //result <- record with this key
    int size( ) const { return used; }   //number of keys in this table
                                         //number of collisions in this table
    long collisions() const {return _collisions;}
    long capacity() const {return CAPACITY;}

    //print the entire talbe with keys, records, and hash values
    template<class TT>
    friend ostream& operator << (ostream& outs,
                                 const DoubleHash<TT>& h);
private:

    static const int NEVER_USED = -1;        //this cell has never had a value
    static const int PREVIOUSLY_USED = -2;   //this cell has previously
                                             //   held a value that has since
                                             //been deleted.

    vector<T> _data;                          //table of records
    int used;                                //number of keys in the table
    long _collisions;

    int hash(int key) const;                //hash function
    int hash2(int key) const;               //hash2 function
    int next_index(int index, int key) const;       //wrap around index
    bool find_index(int key, int& index) const;     //find index of this key
    bool never_used(int index) const;      //is this cell NEVER_USED
    bool is_vacant(int index) const;       //is this cell available for insert
};

 

In your constants.h file: Set your capacity to 811

 

#ifndef CONSTANTS_H
#define CONSTANTS_H
#include  <math.h>
using namespace std;

const int TABLE_SIZE = 811; //811; //180799; //2121737;//180799;// 101119; //811;

#endif // CONSTANTS_H

 

in a for loop (700 iterations), create a record object with random key of 0..10000 (MAX_KEY_SIZE)

Insert this record into both the open_hash and double_hash objects.

At the end of the loop, report the number of collisions for each object.

Place this code in the following function:

Timing Inserts: 

Now, change this program so we can time the two object. How long did it take for the open_hash table to insert the 700 random records? How long did it take for the double_hash table to insert THE SAME random records? Do not insert different records into the two tables.

Timing Searches:

How long did it take to search for 250 of the EXISTING keys in each object?

How long did it take to search for 250 NONEXISTENT keys in each object?