Question

Follow the TODOs and complete the insertItem(), searchItem() and printTable() functions in hash.cpp. The hash function has already been implemented for you.

// hash.CPP program to implement hashing with chaining
#include<iostream>
#include "hash.hpp"

using namespace std;

node* HashTable::createNode(int key, node* next)
{
node* nw = new node;
nw->key = key;
nw->next = next;
return nw;
}

HashTable::HashTable(int bsize)
{
this->tableSize= bsize;
table = new node*[tableSize];
for(int i=0;i<bsize;i++)
table[i] = nullptr;
}

//function to calculate hash function
unsigned int HashTable::hashFunction(int key)
{
return (key % tableSize);
}

// TODO Complete this function
//function to search
node* HashTable::searchItem(int key)
{
//Compute the index by using the hash function
int index = hashFunction(key);

//TODO: Search the list at that specific index and return the node if found
}

//TODO Complete this function
//function to insert
bool HashTable::insertItem(int key)
{
if(!searchItem(key))
{
// TODO :
// Use the hash function on the key to get the index/slot,
// create a new node with the key and insert it in this slot's list

}
else{
cout<<"duplicate entry: "<<key<<endl;
return false;
}

}

//TODO Complete this function
// function to display hash table
void HashTable::printTable()
{
for (int i = 0; i < tableSize; i++) {
cout << i <<"|| ";

//TODO
}

}

///////////////////////hash.hpp//////////////////////

#ifndef HASH_HPP
#define HASH_HPP

#include <string>

using namespace std;

struct node
{
int key;
struct node* next;
};

class HashTable
{
int tableSize; // No. of buckets (linked lists)

// Pointer to an array containing buckets
node* *table;

node* createNode(int key, node* next);
public:
HashTable(int bsize); // Constructor

// inserts a key into hash table
bool insertItem(int key);

// hash function to map values to key
unsigned int hashFunction(int key);

void printTable();

node* searchItem(int key);
};

#endif

////////////////////driver.cpp

// Driver program
#include<iostream>
#include "hash.hpp"
using namespace std;

// GOLD TODO Complete this function
void printPairs(int* arr, int size, int sum, HashTable ht){

bool pairFound = false;

//TODO :
// iterate over each element in the array,
// search for sum-arr[i] in the hashtable, if you find it, print out the pairs giving this sum
// and you are done!

if(pairFound==false){
cout<<"pair not found";
}

}

int main()
{
int a[] = {15, 11, 27, 8, 12, 7, 18};
int n = 7;

// 7 is count of buckets in hash table
HashTable ht(7);

// insert the keys into the hash table.
// SILVER TODO : Complete insertItem() function
for (int i = 0; i < n; i++) {
ht.insertItem(a[i]);
}

cout<< "Contents of the hash table are"<<endl;
// SILVER TODO : Complete printTable() function
ht.printTable();

cout<<endl;

int searchFor = 8;
// SILVER TODO : Complete searchItem() function
if(ht.searchItem(searchFor))
{
cout<<searchFor<<" found in the hash table"<<endl;
}
else{
cout<<searchFor<<" not found in the hash table"<<endl;
}
cout<<"------------------------------------"<<endl;

int sum = 19;

// GOLD TODO Complete printPairs() function
printPairs(a,n,sum,ht);

return 0;
}

Answer 1

//Follow the TODOs and complete the insertItem(), searchItem() and printTable() functions in hash.cpp.The hash function has already been implemented for you.
////////////////////driver.cpp
// Driver program
#include<iostream>
#include <string>
using namespace std;

///////////////////////hash.hpp//////////////////////
struct node
{
   int key;
   struct node* next;
};
class HashTable
{
   int tableSize; // No. of buckets (linked lists)

   // Pointer to an array containing buckets
   node* *table;

   node* createNode(int key, node* next);
public:
   HashTable(int bsize); // Constructor

   // inserts a key into hash table
   bool insertItem(int key);

   // hash function to map values to key
   unsigned int hashFunction(int key);

   void printTable();

   node* searchItem(int key);
};

node* HashTable::createNode(int key, node* next)
{
   node* nw = new node;
   nw->key = key;
   nw->next = next;
   return nw;
}
HashTable::HashTable(int bsize)
{
   this->tableSize = bsize;
   table = new node*[tableSize];
   for (int i = 0; i < bsize; i++)
       table[i] = nullptr;
}
//function to calculate hash function
unsigned int HashTable::hashFunction(int key)
{
   return (key % tableSize);
}
// TODO Complete this function
//function to search
node* HashTable::searchItem(int key)
{
   //Compute the index by using the hash function
   int index = hashFunction(key);
   node* temp = table[index];
   while (temp != nullptr)
   {
       if (temp->key == key)
           return temp;
       temp = temp->next;
   }
   return nullptr;
   //TODO: Search the list at that specific index and return the node if found
}
//TODO Complete this function
//function to insert
bool HashTable::insertItem(int key)
{
   if (!searchItem(key))
   {
       // TODO :
       // Use the hash function on the key to get the index/slot,
       // create a new node with the key and insert it in this slot's list
       int index = hashFunction(key);
       table[index] = createNode(key, table[index]);
       return true;
   }
   else {
       cout << "duplicate entry: " << key << endl;
       return false;
   }
}
//TODO Complete this function
// function to display hash table
void HashTable::printTable()
{
   for (int i = 0; i < tableSize; i++) {
       cout << i << "||";
       node* temp = table[i];
       while (temp != nullptr)
       {
           cout << temp->key << " ";
           temp = temp->next;
       }
       cout << endl;
       //TODO
   }

}
// GOLD TODO Complete this function
void printPairs(int* arr, int size, int sum, HashTable ht) {

   bool pairFound = false;

   //TODO :
   // iterate over each element in the array,
   // search for sum-arr[i] in the hashtable, if you find it, print out the pairs giving this sum
   // and you are done!

  
   for (int i = 0; i < size; i++)
   {
       int toFind = sum - arr[i];
       node* val = ht.searchItem(toFind);
       if (val)
       {      
           cout << arr[i] << " + " << val->key << " = " << sum << endl;
           pairFound = true;
           break;
       }
   }

   if (pairFound == false) {
       cout << "pair not found";
   }
   else cout << "pair found";
}

int main()
{
   int a[] = { 15, 11, 27, 8, 12, 7, 18 };
   int n = 7;

   // 7 is count of buckets in hash table
   HashTable ht(7);

   // insert the keys into the hash table.
   // SILVER TODO : Complete insertItem() function
   for (int i = 0; i < n; i++) {
       ht.insertItem(a[i]);
   }

   cout << "Contents of the hash table are" << endl;
   // SILVER TODO : Complete printTable() function
   ht.printTable();

   cout << endl;

   int searchFor = 8;
   // SILVER TODO : Complete searchItem() function
   if (ht.searchItem(searchFor))
   {
       cout << searchFor << " found in the hash table" << endl;
   }
   else {
       cout << searchFor << " not found in the hash table" << endl;
   }
   cout << "------------------------------------" << endl;

   int sum = 19;

   // GOLD TODO Complete printPairs() function
   printPairs(a, n, sum, ht);

   return 0;
}

COMMENT DOWN FOR ANY QUERY

PLEASE GIVE A THUMBS UP