Implement two hash table classes, Hash_table1 and Hash_table2, which use open addressing for collision resolution. The two hash table classes are very similar. The requirements for the two hash table classes are given as follows:

Both hash table classes take strings as their keys/elements. The maximum width of the strings/keys is 6.

Both hash tables use the same hash function which first calculates the product p of all the characters of the key and then returns the index where index=p%hash_size. The pseudo code of the hash function is given as follows.

int hash(const string &key) {

int value = 1;

for (int position = 0; position < max_key_length; position++)

value *= key[position];

value %= hash_size;

if (value < 0) value += hash_size;

return value;

}

In both hash table classes, you need to implement:

The hash function.

A constructor that takes an integer parameter specifying the hash table size (hash_size).

The retrieve() method that takes a string key as the input and returns the location (index) of the key in the hash table. If the hash table does not have the key, retrieve() returns -1.

The insert() method that takes a string key as the input and inserts it into the hash table. If the key already exists in the table or if the table is full, the insertion will not be completed and -1 is returned. If the key is inserted, the location (index) of the key in the hash table is returned.

Class Hash_table1 uses linear probing for collision resolution.

Class Hash_table2 uses quadratic probing for collision resolution.

Implement Hash_table1 and Hash_table2 in files Hash_table1.h/cpp and Hash_table2.h/cpp respectively.

const int hash_size = 997; // a prime number of appropriate size

class Hash_table {

public:

Hash_table( );

void clear( );

Error_code insert(const Record &new_entry);

Error_code retrieve(const Key &target, Record &found) const;

private:

Record table[hash_size];

};

Error_code Hash_table :: insert(const Record &new_entry)

/* Post: If the Hash_table is full, a code of overflow is returned. If the table already contains an item with the key of new_entry a code of duplicate_error is returned. Otherwise: The Record new_entry is inserted into the Hash_table and success is returned.

Uses: Methods for classes Key, and Record. The function hash

*/

{

Error_code result = success;

int probe_count, // Counter to be sure that table is not full.

increment, // Increment used for quadratic probing.

probe; // Position currently probed in the hash table.

Key null; // Null key for comparison purposes.

null.make_blank( );

probe = hash(new_entry);

probe_count = 0;

increment = 1;

while (table[probe] != null // Is the location empty?

&& table[probe] != new_entry // Duplicate key?

&& probe_count < (hash_size + 1) / 2) {

// Has overflow occurred?

probe_count++;

probe = (probe + increment) % hash_size;

increment += 2; // Prepare increment for next iteration.

}

if (table[probe] == null) table[probe] = new_entry; // Insert new entry.

else if (table[probe] == new_entry) result = duplicate_error;

else result = overflow; // The table is full.

return result;

}

Error_code Hash_table :: retrieve(const Key &target, Record &found) const

/* Post: If an entry in the hash table has key equal to target, then found takes on the value of such an entry, and success is returned. Otherwise, not_present is returned..

Uses: Methods for classes Key, and Record. The function hash

*/

{

int probe_count, // counter to be sure that table is not full

increment, // increment used for quadratic probing

probe; // position currently probed in the hash table

Key null; // null key for comparison purposes

null.make_blank();

probe = hash(target);

probe_count = 0;

increment = 1;

while ((Key) table[probe] != null // Is the location empty?

&& (Key) table[probe] != target // Search Successful?

&& probe_count < (hash_size + 1) / 2) // Full table? {

probe_count++;

probe = (probe + increment) % hash_size;

increment += 2; // Prepare increment for next iteration

}

if ((Key) table[probe] == target) {

found = table[probe];

return success;

}

else return not_present;

}