do in C++

Write a program to simulate a Separate Chaining Hash Table. The input data speci es the size of the table and 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:

[ [ (key.char At(i) x 31^(n-i-1) mod 2^32) ] mod 2^32 ] mod tableSize

where there are n characters in the key. So if the key is ABCD the hash function will return

[((65 31³ mod 2³²)+(66 31² mod 2³²)+(67 31¹ mod 2³²)+(68 31⁰ mod 2³²)) mod 2³²] mod tableSize 1. Use Horner's rule to simplify the computation.

Use unsigned int arithmetic to automatically implement mod 2³².

Java doesn't support unsigned types or unsigned arithmetic, but signed and unsigned integer arithmetic result in the same bit patterns. However the '%' operator isn't the same as the math-ematical mod operator. It will interpret at 32 bit int as a signed value and will give a signed result.

For example the unsigned value 4294967283₁₀ ts into 32 bits as FFFFFFF3₁₆ but appears to Java and its % operator as 13₁₀ and 13%7 yields 6. The correct result for 4294967283 mod 7 is 5. You'll have to think about how to do the mod tableSize operation correctly.

4. The result must be an int in [0; tableSize].

Write a fast version of this function and thoroughly test it before proceeding to use it. The function computes the table index of the linked list where the record will be, or is already, stored.

Input Data:

The input data will be read from System.in (cin for C++). 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; 2⁶³ 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	Key Salvage inserted
24	Key Junk inserted
I Salvage 1234567890	Key Garbage inserted
I Junk 2345678901	Key refuse inserted
I Garbage 3456789012	Number of records in table = 4
I refuse 4567890123	Key waste inserted
P	Key scrap inserted
I waste 5678901234	Key drivel inserted
I scrap 6789012345	Key refuse already exists
I drivel 7890123456	Key refuse already exists
I refuse 5567890123	Key Junk found, record = 2345678901
I refuse 6567890123	Key key doesn't exist
S Junk	Key Salvage deleted
S key	Key trash doesn't exist
D Salvage	Key scraps inserted
D trash	Key obsolete inserted
I scraps 89012345678	Key deprecated inserted
I obsolete 9012345678	Key trash doesn't exist
I deprecated 0123456789	Key Salvage doesn't exist
S trash	Key Salvage inserted
S Salvage	Key Junk found, record = 2345678901
I Salvage 1234567899	Key refuse found, record = 4567890123
S Junk	Key Salvage found, record = 1234567899
S refuse	Number of records in table = 10
S Salvage
P