Do in either C++ or Java. Only need to implement type D. Thank you. Write a clas
ID: 3734604 • Letter: D
Question
Do in either C++ or Java. Only need to implement type D. Thank you.
Write a class, MyHashTable to implement a hash table that uses Open Hashing, and insert it in a test program The hash table efficiently stores records and uses character strings as keys. The member functions will be: MyHashTable(int sz); boolean insert (String key, String record); // returns false if key is present, true otherwise // create an empty has table of fixed size sz // key is a string of lower case alphabetic chars w/o spaces String isPresent(String key);// returns the record if key is present, null otherwise boolean delete(String key); int membership); void listAll) // returns false if key is not present, true otherwise // returns the number of records in the data structure // list all members of the hash table in the order that // they are stored. Precede each one with an integer giving // the index in the table of that record The hash function MUST BE as follows: int hash(String ky, int tableSize) [ int m - ky.lengthO; int sum0 for(int i-m-1;i>-0;i--) // use unsigned ints in C/C++ sum - sum*31 + (int) (ky.charAt(i)); // automatically applies mod 2 132) sum sum & 0x7fffffff return sum % tables ize // remove the sign bit // % works fine with a positive dividend Your program will read a text file from System.in that contains text commands. In response to each command your program will output one or more lines of text to System.out Here are the commands: L SZ Q sz D sz R // create a hash table of size sz that uses linear probing // create a hash table of size sz that uses quadratic probing // create a hash table of size sz that uses double hashing with h_2(y) R (y mod R) // empty the hash table and reset the statistics A soap:Keeps you clean /7 Insert record "Keeps you clean" with "soap" as its key. // Print one of the lines "Key soap inserted at location #", "Key soap already exists". OR // "Table has overflowed". In the latter case, the record isn't inserted // Delete the record that has "sin" as its key // Print one of the lines "Key sin deleted" OR "Key sin not found" R sin S fortune // Search for the key "fortune" // Print one of the lines "Key fortune:" then the record corresponding to that key, // then the text " found at location #" , OR Key fortune not found" // Print the line "Membership is #" where # is the number of records stored in the table // Print a list of the elements in the Table in the order of their position in the table, // one record per line in the form "# key: Record, where # is the position in the table // Print the following three lines: // Total probes during inserts = # // Total probes during unsuccessful searches = #Explanation / Answer
/*
* C++ Program to Implement Hash Tables with Double Hashing
*/
#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;
/*
* Node Type Declaration
*/
enum EntryType {Legitimate, Empty, Deleted};
/*
* Node Declaration
*/
struct HashNode
{
int element;
enum EntryType info;
};
/*
* Table Declaration
*/
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;
}
}
/*
* Main Contains Menu
*/
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.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:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.