A single testing file has been provided.

Anything in red will not be graded.

Requirements:

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

1. Hash tables using quadratic hashing: Quadratic_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:

---

Quadratic_hash_table

Description

A class which implements a hash table using quadratic 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 hash function (that determining the initial bin) is the object statically cast as an int (see static_cast<int>), taking this integer module M (i % M), and adding M if the value is negative.

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. If the user supplies a negative number, use 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 and erased 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 aforementioned hash function and the rules of quadratic hashing. If the table is full, thrown an overflow exception. If the hash table is not full and the argument is already in the hash table, do nothing. An object can be placed either into an empty or deleted bin. Do not rehash the entries even if there are many erased bins. (Θ(1) under our assumption of a small load factor)

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 assumption of a small load factor)

void clear()

Removes all the elements in the hash table by setting all entries to unoccupied. (Θ(M))

Friends

The class has no friends.

Testing

Consider testing your code with something like:

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

using namespace std;

int main() {
	Quadratic_hash_table ht(10);

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

	return 0;
}

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