Program Exercise (Can be done either in Java or C): Implementing a hash table wi

Question

Program Exercise (Can be done either in Java or C):

Implementing a hash table with insertion, deletion and searching by using the double hashing method. Your double hashing is of h(k) = i + jd(k)mod N and d(k) = q - k mod q. Pick q as the largest prime thats less than N.

*/Sample input: Sequence of random integers "1.in 4.in 6.in 4.del 8.in 10.in 13.in 1.sch 19.in". Once the hash table is full stop your input. Sample output: Two output sets should be displayed with one being before and the other after the operation. Not that output of sch is to be "found" or "not found". Sample output format

0:

1: 1

2:215

3:

4: ...

12:12

If duplicate is inserted please display "duplicate key". */

Please help me with this exercise will rate! Thank you!

Explanation / Answer

CODE:

Please find C++ program below.

#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;

// Node Type Declaration
enum EntryType {Legitimate, Empty, Deleted};

// HashNode defined.
struct HashNode
{
int element;
enum EntryType info;
};

// HashTable declared here
struct HashTable
{
int size;
HashNode *table;
};

// Function to Genereate First Hash
int HashFunc1(int key, int size)
{
return key % size;
}

// Function to Genereate Second Hash
int HashFunc2(int key, int size)
{
return (key * size - 1) % size;
}

// Function to Initialize Table
HashTable *initializeTable(int size)
{
HashTable *htable;
if (size < MIN_TABLE_SIZE)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
htable = new HashTable;
if (htable == NULL)
{
cout<<"Out of Space"<<endl;
return NULL;
}
htable->size = size;
htable->table = new HashNode [htable->size];
if (htable->table == NULL)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
for (int i = 0; i < htable->size; i++)
{
htable->table[i].info = Empty;
htable->table[i].element = NULL;
}
return htable;
}

// Function to Find Element from the table
int Find(int key, HashTable *htable)
{
int hashVal= HashFunc1(key, htable->size);
int stepSize= HashFunc2(key, htable->size);
while (htable->table[hashVal].info != Empty &&
htable->table[hashVal].element != key)
{
hashVal = hashVal + stepSize;
hashVal = hashVal % htable->size;
}
return hashVal;
}

// Function to Insert Element into the table
void Insert(int key, HashTable *htable)
{
int pos = Find(key, htable);
if (htable->table[pos].info != Legitimate )
{
htable->table[pos].info = Legitimate;
htable->table[pos].element = key;
}
}
// Function to Rehash the table
HashTable *Rehash(HashTable *htable)
{
int size = htable->size;
HashNode *table = htable->table;
htable = initializeTable(2 * size);
for (int i = 0; i < size; i++)
{
if (table[i].info == Legitimate)
Insert(table[i].element, htable);
}
free(table);
return htable;
}

// Function to Retrieve the table
void Retrieve(HashTable *htable)
{
for (int i = 0; i < htable->size; i++)
{
int value = htable->table[i].element;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}

}

int main()
{
int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{
cout<<" ----------------------"<<endl;
cout<<"Operations on Double Hashing"<<endl;
cout<<" ----------------------"<<endl;
cout<<"1.Initialize size of the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Display Hash Table"<<endl;
cout<<"4.Rehash The Table"<<endl;
       cout<<"5.Search The Table"<<endl;
cout<<"6.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter size of the Hash Table: ";
cin>>size;
htable = initializeTable(size);
break;
case 2:
if (i > htable->size)
{
cout<<"Table is Full, Rehash the table"<<endl;
continue;
}
   cout<<"Enter element to be inserted: ";
   cin>>value;
Insert(value, htable);
i++;
break;
case 3:
Retrieve(htable);
break;
case 4:
htable = Rehash(htable);
break;
case 5:
           cout << "Enter the key to search" << endl;
           cin >> value;
           int pos = Find(value, htable);
           cout << "Given key is at position" << pos << endl;
           break;
       case 6:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.