The purpose of this lab is to help implement double hashing in C++. You will be using table1.h and table1.template files for this exercise.

A few things to take care of for this Lab:

Add the Hash2 function prototype to the table1.h file in the private member section

Change the value of CAPACITY in table1.h to be equal to 2n (16,32,etc.)

Replace data[i].key with just data[i] in your template function

Replace entry.key with just entry in your table1.template file

For your test file main.cpp:

Create a hash table object that can hold int values.

Insert test data so that they have collision ( eg: if CAPACITY is 16, then use data values 3, 19, 51, 67, etc. ) have enough test data to show multiple collisions.

Print the hash table values such that it is clear at which index the collision happened.

Output should include the index position for all values in the table.

You do not need to print the entire table. Only print the index positions that have a valid entry in them.

table1.h

// FILE: table1.h (part of the namespace main_savitch_12A) // TEMPLATE CLASS PROVIDED: table (a table of records with keys). // This class is a container template class for a table of records. // The template parameter, RecordType, is the data type of the records in the // table. It may be any of the bulit-in C++ types (int, char, etc.), or a // class with a default constructor, an assignment operator, and an integer // member variable called key. // // MEMBER CONSTANT for the table class: // static const size_type CAPACITY = ________ // table::CAPACITY is the maximum number of records held by a table. // // CONSTRUCTOR for the table template class: // table( ) // Postcondition: The table has been initialized as an empty table. // // MODIFICATION MEMBER FUNCTIONS for the table class: // void insert(const RecordType& entry) // Precondition: entry.key >= 0. Also if entry.key is not already a key in // the table, then the table has space for another record // (i.e., size( ) < CAPACITY). // Postcondition: If the table already had a record with a key equal to // entry.key, then that record is replaced by entry. Otherwise, entry has // been added as a new record of the table. // // void remove(int key) // Postcondition: If a record was in the table with the specified key, then // that record has been removed; otherwise the table is unchanged. // // CONSTANT MEMBER FUNCTIONS for the table class: // bool is_present(const Item& target) const // Postcondition: The return value is true if there is a record in the // table with the specified key. Otherwise, the return value is false. // // void find(int key, bool& found, RecordType& result) const // Postcondition: If a record is in the table with the specified key, then // found is true and result is set to a copy of the record with that key. // Otherwise found is false and the result contains garbage. // // size_type size( ) const // Postcondition: Return value is the total number of records in the // table. // // VALUE SEMANTICS for the table template class: // Assignments and the copy constructor may be used with table objects.

#ifndef TABLE1_H #define TABLE1_H #include // Provides size_t

namespace main_savitch_12A { template class table { public: // MEMBER CONSTANT -- See Appendix E if this fails to compile. static const std::size_t CAPACITY = 811; // CONSTRUCTOR table( ); // MODIFICATION MEMBER FUNCTIONS void insert(const RecordType& entry); void remove(int key); // CONSTANT MEMBER FUNCTIONS bool is_present(int key) const; void find(int key, bool& found, RecordType& result) const; std::size_t size( ) const { return used; } private: // MEMBER CONSTANTS -- These are used in the key field of special records. static const int NEVER_USED = -1; static const int PREVIOUSLY_USED = -2; // MEMBER VARIABLES RecordType data[CAPACITY]; std::size_t used; // HELPER FUNCTIONS std::size_t hash(int key) const; std::size_t next_index(std::size_t index) const; void find_index(int key, bool& found, std::size_t& index) const; bool never_used(std::size_t index) const; bool is_vacant(std::size_t index) const; }; } #include "table1.template" // Include the implementation. #endif

table1.template

// FILE: table1.template // TEMPLATE CLASS IMPLEMENTED: table (see table1.h for documentation) // INVARIANT for the table ADT: // 1. The number of records in the table is in the member variable used. // 2. The actual records of the table are stored in the array data, with // a maximum of CAPACITY entries. Each used spot in the array has a // non-negative key. Any unused record in the array has a key field of // NEVER_USED (if it has never been used) or PREVIOUSLY_USED (if it once // was used, but is now vacant).

#include // Provides assert #include // Provides size_t

namespace main_savitch_12A { template const std::size_t table::CAPACITY;

template const int table::NEVER_USED;

template const int table::PREVIOUSLY_USED;

template table::table( ) { std::size_t i;

used = 0; for (i = 0; i < CAPACITY; ++i) data[i].key = NEVER_USED; // Indicates a spot that's never been used. }

template void table::insert(const RecordType& entry) // Library facilities used: cassert { bool already_present; // True if entry.key is already in the table std::size_t index; // data[index] is location for the new entry

assert(entry.key >= 0);

// Set index so that data[index] is the spot to place the new entry. find_index(entry.key, already_present, index);

// If the key wasn't already there, then find the location for the new entry. if (!already_present) { assert(size( ) < CAPACITY); index = hash(entry.key); while (!is_vacant(index)) index = hash2(index);//next_index(index); ++used; }

data[index] = entry; }

template inline std::size_t table::hash2(int key) const { return ((key+4) % CAPACITY); }

template void table::remove(int key) // Library facilities used: cassert { bool found; // True if key occurs somewhere in the table std::size_t index; // Spot where data[index].key == key

assert(key >= 0);

find_index(key, found, index); if (found) { // The key was found, so remove this record and reduce used by 1. data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use. --used; } }

template bool table::is_present(int key) const // Library facilities used: assert.h { bool found; std::size_t index;

assert(key >= 0);

find_index(key, found, index); return found; }

template void table::find(int key, bool& found, RecordType& result) const // Library facilities used: cassert.h { std::size_t index;

assert(key >= 0);

find_index(key, found, index); if (found) result = data[index]; }

template inline std::size_t table::hash(int key) const { return (key % CAPACITY); }

template inline std::size_t table::next_index(std::size_t index) const // Library facilities used: cstdlib { return ((index+1) % CAPACITY); }

template void table::find_index(int key, bool& found, std::size_t& i) const // Library facilities used: cstdlib { std::size_t count; // Number of entries that have been examined

count = 0; i = hash(key); while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key)) { ++count; i = next_index(i); } found = (data[i].key == key); }

template inline bool table::never_used(std::size_t index) const { return (data[index].key == NEVER_USED); } template inline bool table::is_vacant(std::size_t index) const { return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED); } }