A single testing file has been provided.

Requirements:

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

Dynamically Resizing Hash Tables using Double Hashing: Dynamic_double_hash_table.

In this project, you will create a hash table which stores objects. We will assume that the hash function is sufficiently even so as to allow all expected constant-time operations to be O(1).

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:

`Dynamic_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 (the one determining the bin) is the object statically cast as an int (see static_cast<int>) and taking this integer modulo M (i % M) and adding M if the value is negative. The secondary (odd) hash function (the one 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 five members:

An array of objects Type *array,
An array storing the current state of a bin state *occupied,
An array size int array_size, and
A count int count.
A count of deleted bins int deleted_count.

You may need additional member variables. An enumerated type state is provided; however, you may use a different solution.

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 and if m < 2, use the value m = 2, i.e., the initial size is no smaller than 4.

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. (O(1))
int capacity() const: Returns the number of bins in the hash table. (O(1))
double load_factor() const: Returns the load factor of hash table (see static_cast<double>(...)). (O(1))
double deleted_factor() const: Returns the number of deleted bins over the number of bins. (O(1))
bool empty() const: Returns true if the hash table is empty, false otherwise. (O(1))
bool member( Type const & ) const: Returns true if object obj is in the hash table and false otherwise. (Amortized O(1))
Type bin( int ) 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 the class with the expected locations. (O(1))

Mutators

This class has three mutators:

void insert( Type const & ): If the object is currently a member of the hash table, do not add it. Insert a new object into the hash table in the appropriate bin as determined by the two aforementioned hash functions and the rules of double hashing. If before the insertion the load factor greater or equal than 0.75, double the size of the hash table and rehash all original entries into the new hash table in the order in which they appear in the current hash table prior to doubling. Only add the new entry after any doubling has occured. (Amortized O(1))
bool remove( Type const & ): Remove the object 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. If the argument was successfully removed and the load factor is lesser or equal than 0.25 and the hash table is not already the initial size of the hash table, halve the size of the hash table and insert the entries into the new hash table in the order in which they appear in the current hash table prior to halving. If the table was not halved in size but the proportion of deleted bins is greater or equal than 0.25, rehash all the entries into the same sized hash table in the order(ordered from index 0 to M) in which they appear in the current hash table. (Amortized O(1))
void clear(): Removes all the elements in the hash table and resets the size to the initial size. (O(M))

It is suggested that you have one function which deals with halving, rehashing, and doubling the hash table.

Friends

The class has one friend: the << operator.

Testing

Consider testing your code with something like:

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

using namespace std;

int main() {
	Dynamic_double_hash_table ht(4);

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

	return 0;
}

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

Dynamic Double Hash Tables