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

[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 doesnt exist

S k // search for key k

//print Key k found, record = value or Key k doesnt 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 doesnt exist Key Salvage deleted Key trash doesnt exist Key scraps inserted Key obsolete inserted key deprecated inserted Key trash doesnt exist Key Salvage doesnt exist Key Salvage doesnt 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)) rnod