Write a program to simulate a Separate Chaining Hash Table. The input data specifies 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 doesnt 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 isnt 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: ""nX1 i=0 key.charAt(i) 31ni1 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 [((65313 mod 2 32)+(66312 mod 2 32)+(67311 mod 2 32)+(68310 mod 2 32)) mod 2 32] mod tableSize 1. Use Horners rule to simplify the computation. 1

2. Use unsigned int arithmetic to automatically implement mod 2 32 .

3. Java doesnt support unsigned types or unsigned arithmetic, but signed and unsigned integer arithmetic result in the same bit patterns. However the % operator isnt the same as the mathematical mod operator. It will interpret at 32 bit int as a signed value and will give a signed result. For example the unsigned value 429496728310 fits into 32 bits as FFFFFFF316 but appears to Java and its % operator as 1310 and 13%7 yields 6. The correct result for 4294967283 mod 7 is 5. Youll 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 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 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 doesnt exist S Junk Key Salvage deleted S key Key trash doesnt exist D Salvage Key scraps inserted D trash Key obsolete inserted I scraps 89012345678 Key deprecated inserted I obsolete 9012345678 Key trash doesnt exist I deprecated 0123456789 Key Salvage doesnt 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

import java.util.*; import java.io.*; // for reading from named files during testing class IVPAP1 { // for my project 1 . . . static functions go here . . . public static void main(String [] args) throws IOException { //the "throws" statement is for reading from a named file Scanner sc = new Scanner(System.in); // to read from System.in // Scanner sc = new Scanner(new File("myData.txt")); // switch the comments to the arrangement above before submitting String line = sc.nextLine(); int M = Integer.parseInt(line); line = sc.nextLine(); int q = Integer.parseInt(line); . . . } } // end of IVPAP1 class Node { . . . }