A single testing file has been provided.

Requirements:

In this sub-project, you will implement one class:

1. Hash Tables using Double Hashing: Double_hash_table.

In this project, you will create a hash table which stores objects. We will assume that the hash functions are appropriate so as to allow all operations to run in Θ(1) time when the load factor is not greater than, say, 0.666.

Run time:

The run time of each member function is specified in parentheses at the end of the description. We assume that the distribution of the hash function is even.

Class Specifications:

---

Double_hash_table

Description

A class which implements a hash table using double hashing. For run-time requirements, the number of elements in the hash table is n and the size of the hash table is M.

The primary hash function (that determining the bin) is the object statically cast as an int (see static_cast<int>) and taking this integer module M (i % M) and adding M if the value is negative. The secondary (odd) hash function (that determining the jump size) is derived from the integer divided by M modulo M ((i / M) % M) which is again made positive, if necessary, by adding M.

Member Variables

The class has at least three members:

• An array of objects Type *array,
• An array size int array_size, and
• A count int count.

You may need additional member variables.

Member Functions

Constructors

The constructor takes an argument m and creates a hash table with 2^m bins, indexed from 0 to 2^m − 1. The default value of m is 5.

Destructor

The destructor frees up any memory allocated by the constructor.

Accessors

This class has seven accessors:

int size() const

Returns the number of elements currently stored in the hash table. (Θ(1))

int capacity() const

Returns the number of bins in the hash table. (Θ(1))

double load_factor() const

Returns the load factor of hash table (see static_cast<double>(...)). This should be the ratio of occupied bins over the total number of bins. (Θ(1))

bool empty() const

Returns true if the hash table is empty, false otherwise. (Θ(1))

bool member( Type const & ) const

Returns true if object obj is in the hash table and false otherwise. (Θ(1) under our assumptions)

Type bin( int n ) const

Return the entry in bin n. The behaviour of this function is undefined if the bin is not filled. It will only be used to test locations that are expected to be filled by specific values. (Θ(1))

void print() const

A function which you can use to print the class in the testing environment. This function will not be tested.

Mutators

This class has three mutators:

void insert( Type const & )

Insert the argument into the hash table in the appropriate bin as determined by the two aforementioned hash functions and the rules of double hashing. If the table is full, thrown an overflow exception. If the argument is already in the hash table, do nothing. An object can be placed either into an empty or deleted bin. (Θ(1) under our assumptions)

bool erase( Type const & )

Remove the argument from the hash table if it is in the hash table (returning false if it is not) by setting the corresponding flag of the bin to deleted. (Θ(1) under our assumptions)

void clear()

Removes all the elements in the hash table. (Θ(M))

Friends

The class has no friends.

Testing

Consider testing your code with something like:

#include <iostream>
#include "Double_hash_table.h"

using namespace std;

int main() {
	Double_hash_table ht(10);

	for ( int i = 93251234; i < 93251534; i += 9382 ) {
		ht.push( i );
	}

	return 0;
}

or perhaps something smaller with only 16 = 2⁴ entries.