Question

[Hash Tables] Given the following code in C++, implement the functions in table2.cpp. The first 2 files (table2.h, short story text file) are all fully coded and commented for convenience.

*****I have given references that I've completed previously for the table2.cpp file, I just need help applying them. Will provide good rating, thanks******

--------------------------------------------------------------------------------------------------------------------------

table2.h (given file, do not edit):

// FILE: table2.h
//
// ABSTRACT BASE CLASS: Table
//    1. The number of records in the Table is stored in total_records
// 2. The hashcode function returns a location in the table for the
// input key. It calls hash function in functional library.
// 3. insert and print are two virtual functions to be overridden
// insert: Add a new record into the Table;
//           If key is already in the table, increment count
// print_max: print the record with the highest count
//
// DERIVED CLASS: ChainTable
//    The actual records are stored in a chained hash table.
//       datatable[i] stores a list of Records
//
// DERIVED CLASS: QuadTable
//    The actual records of the table are stored in an array.
// datatable[i] stores one Record
//

#ifndef TABLE_H
#define TABLE_H

#include <string>       // Provide string
#include <functional> // Provide hash
#include <list>        // Provide list
using namespace std;

class Table
{
public:
   // MEMBER CONSTANT
   static const unsigned int TABLE_SIZE = 5801;

   Table() { total_records = 0; }
   virtual ~Table() { }

   unsigned int get_total() { return total_records; }

   virtual void insert(string key) =0;
   virtual void print_max() =0;
  
protected:
   unsigned int total_records;

   // HELPER FUNCTION
   unsigned int hashcode(string key) const
   {
       hash<string> thishash;
       return thishash(key) % TABLE_SIZE;
   }
};

class Record
{
public:
   Record(string k="", unsigned int c=0) { key = k; count = c; }
   string key;
   unsigned int count;
};

class ChainTable : public Table
{
public:
   ChainTable() {}

   virtual void insert(string key);
   virtual void print_max();
  
private:
   list<Record> datatable[TABLE_SIZE];
};

class QuadTable : public Table
{
public:
   QuadTable() {}
  
   virtual void insert(string key);
   virtual void print_max();
   bool full() { return total_records == TABLE_SIZE; }
  
private:
   Record datatable[TABLE_SIZE];
};

#endif

--------------------------------------------------------------------------------------------------------------------------

shortstory.txt (given file, do not edit):

John Rento looked at the giant hawk in his hands and felt stressed.

He walked over to the window and reflected on his quiet surroundings. He had always loved cold Athens with its faithful, friendly fields. It was a place that encouraged his tendency to feel stressed.

Then he saw something in the distance, or rather someone. It was the figure of Georgina Rockatansky. Georgina was an intuitive god with curvy fingers and grubby eyelashes.

John gulped. He glanced at his own reflection. He was a spiteful, proud, port drinker with handsome fingers and short eyelashes. His friends saw him as a queenlike, queasy queen. Once, he had even saved a homely disabled person that was stuck in a drain.

But not even a spiteful person who had once saved a homely disabled person that was stuck in a drain, was prepared for what Georgina had in store today.

THE END

--------------------------------------------------------------------------------------------------------------------------

table2.cpp (code to complete):

// FILE: table2.cpp
// CLASS IMPLEMENTED: ChainTable and QuadTable (see table2.h for documentation)

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

void ChainTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the chained hash table
   // ------
   // 1. use hashcode function to calculate bucket index i
   //   2. check if key is already in the list at datatable[i];
   //   - if yes, increment the count by 1
   //   - if no, insert key into the list, increment total_records
  
  
}

// print the Record with the highest count
void ChainTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use ChainTable::print() from part 1 as a reference
   // This is the Part 1 ChainTable::print() (reference)
  
   // void ChainTable::print()
   //{
   // cout << "ChainTable content: \n";
   // if (total_records==0)
   //{
   //   cout << "\t Empty!\n";
   //   return;
   //}

   // for (unsigned int i=0; i<TABLE_SIZE; i++)
   //{  
   //   if (datatable[i].empty())
   //       continue;
//
   //   cout << "\t Entry " << i << ": ";
   //   for (list<string>::iterator it = datatable[i].begin(); it != datatable[i].end(); it++)
   //   {
   //       cout << (*it) << " -> ";
   //   }
   //   cout << "NULL\n";
   // }
// }
}

//////////////////////////////////////////////////
void QuadTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the hash table using quadratic probing
   // ------
   // Modify from the implementation from part 1
   //   1. use hashcode function to calculate array index i
   //   2. check if datatable[i] is empty
   //   - if yes, insert key at datatable[i]
   //   - if no, use quadratic probing with probe function c(i)=i^2,
   //       if key is found, increment total_records;
   //       if key is not found, then look for an empty location,
   //       insert key at that location, set total_records = 1
   //   4. if datatable is full and key is new, do nothing and return

}

// print the Record with the highest count
void QuadTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use QuadTable::print() from part 1 as a reference
   // This is the Part 1 QuadTable::print() (reference)
  
//   void QuadTable::print()
//{
//   cout << "QuadTable content: \n";
//   if (total_records==0)
//   {
//       cout << "\t Empty!\n";
//       return;
//   }
//
//   for (unsigned int i=0; i<TABLE_SIZE; i++)
//   {  
//       if (datatable[i].empty())
//           continue;
//
//       cout << "\t Entry " << i << ": ";
//       cout << datatable[i] << endl;
//   }
//}

  
}

Answer 1

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

void ChainTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the chained hash table
   // ------
   // 1. use hashcode function to calculate bucket index i
   //   2. check if key is already in the list at datatable[i];
   //   - if yes, increment the count by 1
   //   - if no, insert key into the list, increment total_records
    
   int index = hashcode(key);
   bool is_already_present = false;
   for(auto it = datatable[index].begin(); it != datatable[index].end(); ++it){
       if(it->key == key){
           is_already_present = true;
           it->count++;
           break;
       }
   }
   if(not is_already_present){
       datatable[index].push_back(Record(key,1));
       total_records++;
   }
  
}


// print the Record with the highest count
void ChainTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use ChainTable::print() from part 1 as a reference
   // This is the Part 1 ChainTable::print() (reference)
  
   // void ChainTable::print()
   //{
   // cout << "ChainTable content: \n";
   // if (total_records==0)
   //{
   //   cout << "\t Empty!\n";
   //   return;
   //}

   // for (unsigned int i=0; i<TABLE_SIZE; i++)
   //{  
   //   if (datatable[i].empty())
   //       continue;
//
   //   cout << "\t Entry " << i << ": ";
   //   for (list<string>::iterator it = datatable[i].begin(); it != datatable[i].end(); it++)
   //   {
   //       cout << (*it) << " -> ";
   //   }
   //   cout << "NULL\n";
   // }
// }
//   
    Record max_record;
    for(unsigned int i=0;i < TABLE_SIZE;i++){
        if(datatable[i].empty())continue;
        for(const auto val: datatable[i]){
            if(val.count > max_record.count){
                max_record = val;
            }
        }
    }
    cout<<"Record with max count is "<<max_record.key<<" and count is "<<max_record.count<<endl;
}


//////////////////////////////////////////////////
void QuadTable::insert(string key)
{
   //--------------------------------------------------------------
   // TO-DO: insert key into the hash table using quadratic probing
   // ------
   // Modify from the implementation from part 1
   //   1. use hashcode function to calculate array index i
   //   2. check if datatable[i] is empty
   //   - if yes, insert key at datatable[i]
   //   - if no, use quadratic probing with probe function c(i)=i^2,
   //       if key is found, increment total_records;
   //       if key is not found, then look for an empty location,
   //       insert key at that location, set total_records = 1
   //   4. if datatable is full and key is new, do nothing and return
   
    int index = hashcode(key);
    if(full() and datatable[index].key != key){   // if table is full and key does not match
        return;
    }
    if(datatable[index].key == "" and datatable[index].count == 0){  // if there is no entry at desired position
        datatable[index] = Record(key,1);
    }
    else{
        long unsigned counter = 0;
        while(true){   // apply quadratic probing
            int new_index = (index + counter*counter) % TABLE_SIZE;
            if(datatable[new_index].key == key){   // already present a key 
                datatable[new_index].count++;
                return;
            }
            else if(datatable[new_index].key == "" and datatable[new_index].count == 0){  // empty location
                datatable[new_index] = Record(key,1);
                total_records++;
                return ;
             }
            counter++;
        }
    }
}

// print the Record with the highest count
void QuadTable::print_max()
{
   //-------------------------------------------------------------
   // TO-DO: go through the hash table,
   //       find the record with the highest count,
   //       and print out the information.
   // ------
   // You can use QuadTable::print() from part 1 as a reference
   // This is the Part 1 QuadTable::print() (reference)
  
//   void QuadTable::print()
//{
//   cout << "QuadTable content: \n";
//   if (total_records==0)
//   {
//       cout << "\t Empty!\n";
//       return;
//   }
//
//   for (unsigned int i=0; i<TABLE_SIZE; i++)
//   {  
//       if (datatable[i].empty())
//           continue;
//
//       cout << "\t Entry " << i << ": ";
//       cout << datatable[i] << endl;
//   }
//}

  
    Record max_record;
    for(unsigned int i=0; i < TABLE_SIZE;i++){
        if(datatable[i].key == "" and datatable[i].count == 0){ // if there is no entry at desired position
            continue;
        }
        if(datatable[i].count > max_record.count)
            max_record = datatable[i];
        
    }
    cout<<"Record with max count is "<<max_record.key<<" and count is "<<max_record.count<<endl;
}