Do in C++. Thank you Write a program to simulate a Separate Chaining Hash Table.
ID: 3880784 • Letter: D
Question
Do in C++. Thank you
Write a program to simulate a Separate Chaining Hash Table. The input data specifies the size of the table in includes data to insert, delete, and to find. The table size will not be larger than 16381, and will always be prime. The load factor will not exceed 10.
Create the following classes:
class Node {
private Node next; // the linkage in the singly linked list
private String key; // the key of the element
private long value; // the data stored
Node(String ky, long val, Node nxt); // constructor
. . .
}
class LinkedList {
Node head;
boolean insert(String key, long value); // insert at head, or
// do nothing, and return false if key is already present
boolean delete(String key); // return false if key doesn't exist
boolean find(String key); // return result of the search
LinkedList(); // constructor
. . .
}
class HashTable {
LinkedList [] L; // uses an array of (your) LinkedLists
HashTable(int size); // constructor
boolean insert(String key, long val); // attempt to insert a record. Return false if
// the key is already present in the table
boolean delete(String key); // attempt to delete a record. Return false if
// the key isn't present in the table
long search(String key); // attempt to find a record. Return the value
// or -1 if the key is not found
void clearTable(); // empty the hash table
int size(); // returns the number of records in the table
. . .
}
The insert, delete and search functions will employ a function:
static int hash(String key, int tableSize);
the function will return the int: (I WILL ATTACH AN IMAGE OF IT)
INPUT DATA:
The input data will be read from system.cin. The data will begin with an integer M on a line by itself giving the size of the table, M <= 16381, M prime. The second line will contain an integer q, q<10000 giving the number of lines to follow. Each of these q lines will have one of the following formats, where “k” is a sequence of up to 20 upper and/or lower case alphabetical characters, and “v” is an integer in
[1,[1, 2^(63) -1]]
I k v // insert record with key k and value v.
// print “Key k inserted” or “Key k already exists”
D k //delete record with key k
// print “Key k deleted” or “Key k doesn’t exist”
S k // search for key k
//print “Key k found, record = value” or “Key k doesn’t exist”
P //print “Number of records in table = #####”
Sample input
Output for sample input
7
24
I Salvage 1234567890
I Junk 2345678901
I Garbage 3456789012
I refuse 4567890123
P
I waste 5678901234
I scrap 6789012345
I drivel 7890123456
I refuse 5567890123
I refuse 6567890123
S Junk
S key
D Salvage
D trash
I scraps 89012345678
I obsolete 9012345678
I deprecated 0123456789
S trash
S Salvage
I Salvage 1234567899
S Junk
S refuse
S Salvage
P
Key Salvage inserted
Key Junk inserted
Key Garbage inserted
Key refuse inserted
Number of records in table = 4
Key waste inserted
Key scrap inserted
Key drivel inserted
Key refuse already exists
Key refuse already exists
Key Junk found, record = 2345678901
Key key doesn’t exist
Key Salvage deleted
Key trash doesn’t exist
Key scraps inserted
Key obsolete inserted key deprecated inserted
Key trash doesn’t exist
Key Salvage doesn’t exist
Key Salvage doesn’t exist
Key Salvage inserted
Key Junk found, record = 2345678901
Key refuse found, record = 4567890123
Key Salvage found, record = 1234567899
Number of records in table = 10
Sample input
Output for sample input
7
24
I Salvage 1234567890
I Junk 2345678901
I Garbage 3456789012
I refuse 4567890123
P
I waste 5678901234
I scrap 6789012345
I drivel 7890123456
I refuse 5567890123
I refuse 6567890123
S Junk
S key
D Salvage
D trash
I scraps 89012345678
I obsolete 9012345678
I deprecated 0123456789
S trash
S Salvage
I Salvage 1234567899
S Junk
S refuse
S Salvage
P
Key Salvage inserted
Key Junk inserted
Key Garbage inserted
Key refuse inserted
Number of records in table = 4
Key waste inserted
Key scrap inserted
Key drivel inserted
Key refuse already exists
Key refuse already exists
Key Junk found, record = 2345678901
Key key doesn’t exist
Key Salvage deleted
Key trash doesn’t exist
Key scraps inserted
Key obsolete inserted key deprecated inserted
Key trash doesn’t exist
Key Salvage doesn’t exist
Key Salvage doesn’t exist
Key Salvage inserted
Key Junk found, record = 2345678901
Key refuse found, record = 4567890123
Key Salvage found, record = 1234567899
Number of records in table = 10
// returns the number of te, and scarch functions will employ a function: sh(String key, int tableSize); The function will return the i (key charAt@s31" -ma d232 mod232 modtableSize n characters in the key. So if the key is ABCD the hash function w 232 )-((ifi × 31 2 mod 232 )+(67x 31 1 mrd 232)+(68 x 31 0 mod 232)) rnodExplanation / Answer
//template1 for generic type
template<typename K, typename V>
//Node class
class Node
{
public:
V value;
K key;
//Constructor of Node
Node(K key, V value)
{
this->value = value;
this->key = key;
}
};
//template for generic type
template<typename K, typename V>
//Our own HashTable class
class HashTable
{
//hash element array
Node<K,V> **arr;
int capacity;
//current size
int size;
//dummy node
Node<K,V> *dummy;
public:
HashTable()
{
//Initial capacity of hash array
capacity = 20;
size=0;
arr = new Node<K,V>*[capacity];
//Initialise all elements of array as NULL
for(int i=0 ; i < capacity ; i++)
arr[i] = NULL;
//dummy node with value and key -1
dummy = new Node<K,V>(-1, -1);
}
// This implements hash function to find index
// for a key
int hashCode(K key)
{
return key % capacity;
}
//Function to add key value pair
void insertNode(K key, V value)
{
Node<K,V> *temp = new Node<K,V>(key, value);
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//find next free space
while(arr[hashIndex] != NULL && arr[hashIndex]->key != key
&& arr[hashIndex]->key != -1)
{
hashIndex++;
hashIndex %= capacity;
}
//if new node to be inserted increase the current size
if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
size++;
arr[hashIndex] = temp;
}
//Function to delete a key value pair
V deleteNode(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//finding the node with given key
while(arr[hashIndex] != NULL)
{
//if node found
if(arr[hashIndex]->key == key)
{
Node<K,V> *temp = arr[hashIndex];
//Insert dummy node here for further use
arr[hashIndex] = dummy;
// Reduce size
size--;
return temp->value;
}
hashIndex++;
hashIndex %= capacity;
}
//If not found return null
return NULL;
}
//Function to search the value for a given key
V get(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//finding the node with given key
while(arr[hashIndex] != NULL)
{
//if node found return its value
if(arr[hashIndex]->key == key)
return arr[hashIndex]->value;
hashIndex++;
hashIndex %= capacity;
}
//If not found return null
return NULL;
}
//Return current size
int sizeofMap()
{
return size;
}
//Return true if size is 0
bool isEmpty()
{
return size == 0;
}
//Function to display the stored key value pairs
void display()
{
for(int i=0 ; i<capacity ; i++)
{
if(arr[i] != NULL && arr[i]->key != -1)
cout << "key = " << arr[i]->key
<<" value = "<< arr[i]->value << endl;
}
}
};
//template1 for generic type
template<typename K, typename V>
//Node class
class Node
{
public:
V value;
K key;
//Constructor of Node
Node(K key, V value)
{
this->value = value;
this->key = key;
}
};
//template for generic type
template<typename K, typename V>
//Our own HashTable class
class HashTable
{
//hash element array
Node<K,V> **arr;
int capacity;
//current size
int size;
//dummy node
Node<K,V> *dummy;
public:
HashTable()
{
//Initial capacity of hash array
capacity = 20;
size=0;
arr = new Node<K,V>*[capacity];
//Initialise all elements of array as NULL
for(int i=0 ; i < capacity ; i++)
arr[i] = NULL;
//dummy node with value and key -1
dummy = new Node<K,V>(-1, -1);
}
// This implements hash function to find index
// for a key
int hashCode(K key)
{
return key % capacity;
}
//Function to add key value pair
void insertNode(K key, V value)
{
Node<K,V> *temp = new Node<K,V>(key, value);
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//find next free space
while(arr[hashIndex] != NULL && arr[hashIndex]->key != key
&& arr[hashIndex]->key != -1)
{
hashIndex++;
hashIndex %= capacity;
}
//if new node to be inserted increase the current size
if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
size++;
arr[hashIndex] = temp;
}
//Function to delete a key value pair
V deleteNode(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//finding the node with given key
while(arr[hashIndex] != NULL)
{
//if node found
if(arr[hashIndex]->key == key)
{
Node<K,V> *temp = arr[hashIndex];
//Insert dummy node here for further use
arr[hashIndex] = dummy;
// Reduce size
size--;
return temp->value;
}
hashIndex++;
hashIndex %= capacity;
}
//If not found return null
return NULL;
}
//Function to search the value for a given key
V get(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//finding the node with given key
while(arr[hashIndex] != NULL)
{
//if node found return its value
if(arr[hashIndex]->key == key)
return arr[hashIndex]->value;
hashIndex++;
hashIndex %= capacity;
}
//If not found return null
return NULL;
}
//Return current size
int sizeofMap()
{
return size;
}
//Return true if size is 0
bool isEmpty()
{
return size == 0;
}
//Function to display the stored key value pairs
void display()
{
for(int i=0 ; i<capacity ; i++)
{
if(arr[i] != NULL && arr[i]->key != -1)
cout << "key = " << arr[i]->key
<<" value = "<< arr[i]->value << endl;
}
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.