Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Write a class, MyHashTable to implement a hash table that uses Open Hashing, and insert it in a test prosram The hash table efficiently stores
Write a class, MyHashTable to implement a hash table that uses Open Hashing, and insert it in a test prosram The hash table efficiently stores records and uses character strings as loeys. The member functions will be: MyHashTable(int sz) boolean inaert(String key, String record): // returns fale if key is present, true othervise // create an enpty has table of fixed size sz // key is a string of lover case alpbabetic chars /o spaces String isPresent (String key)/ returns the record if key is present, null othervise boolean delete(String key) returns false if key is not present, true othervise int senberahsp; void listall I/ returns the nunberof recorda in the data structure // list a11 embers of the hash table in the order that I/ 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 k, int tableSize) int ky.lengthO int aus-0 for(int i-1:i 0:1-- /I use unsigsed ints in c/c sun .,un.31 + (int) (ky.charkt(i)); sun sun &0x7fffffff: return sum % tableSize; // automatically applies nod 2.(32) // 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 // create haa? table of size a: that u ea linear probing II create a haa table of aize az that uses quadratie probing // create a has table of size sz that uses doubl bashing with D sz R If expty the hash table and reset the statistics A soap:Keeps you elean Insert record "Keeps you clean vith "soap" as its key // Prist ase of the lines "Key aoap nserted at locatia 8". *Key soap already exista". OR I Table has overfloved". In the latter case, the record isn't inserted R sin /Delete the record that has sin" as its key I/ Print ose of the lines "Key sin deleted" OR "Key sin not found 3 fortune II Search for the key "fortune II Print ose of the linea "Key fortune: then the record correaponding to that key // then the text found at location #.. OR Key fortune 20t found. // Print the line "Membership is #. where # is te number of records tored in the table Print a liat of the elecents in the Table ia the order of their position in the table // one record per line in the form-# key:Record, where # is the position in tbe table Print the folloving three lines // Total probes during isserts# // Total Drobes during unsuccessful searches " # // Total probes during #accessful earches- / where the bash marks indicate integer values / The end of the input file The first command and will a L, or D Oaly one LQ. D command will be present in any data file. The hash table size could be as large as 10000 and will always be prime. YOU WILL ONLY HAVE TO IMPLEMENT ONE OF THE TYPES OF HASH TABLES DEPENDING ON THE FIRST CHARACTER OF YOUR LAST NAME: A-H: Implement type L I-N: Implement type Q O-Z: Implement type D Sample Input Sample Output Key ant inserted at loeation lKey goat inserted at location 1 iKey frog inserted at location IKey horse inserted at location 0 lKey nouse inaerted at locatien 2 Menberahip ia IKey goat already ezists IKey goat deleted IKey goat not foand 10 horse:Equua ferus caballus 12 souse: Manalsa Rodeatia Mus 4 frog:Anphibia Raza S ant:Anthropoda Messor IKey frog Anphibia Rana found at location 4 IKey ?0use :Mana2 ia Bodeata Hus found at locatioa 2 IKey mouse :Manalia Rodentia Mus found at location 2 ITotal probes during inserts7 Total probes during unsuccessful searches 0 Total probes during succesnfel searches- s ?6 A antiAnthrepoda Messor A goat Capra aegagrus hircus A frog:Amphibia Rana A souse:Manalia Rodeatia Mas A goatiA four legged friesd D goat D goat 8 souse 3. Name your souroe file as NNzFiF2P3 java where your given name begins with the characters NMN2 and your family name begins with the characters FiF2. For example my nane is Ivor Page, so my source file will be called IVPAP3java. Note that in all but the "java" extension, the characters are upper case . Your program must not output any prompts. Its output must exactly match the format of the Sample Output above 5. Do not use any Java Collection Classes, except Strings and arrays. If in doubt, ask me. Write a class, MyHashTable to implement a hash table that uses Open Hashing, and insert it in a test prosram The hash table efficiently stores records and uses character strings as loeys. The member functions will be: MyHashTable(int sz) boolean inaert(String key, String record): // returns fale if key is present, true othervise // create an enpty has table of fixed size sz // key is a string of lover case alpbabetic chars /o spaces String isPresent (String key)/ returns the record if key is present, null othervise boolean delete(String key) returns false if key is not present, true othervise int senberahsp; void listall I/ returns the nunberof recorda in the data structure // list a11 embers of the hash table in the order that I/ 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 k, int tableSize) int ky.lengthO int aus-0 for(int i-1:i 0:1-- /I use unsigsed ints in c/c sun .,un.31 + (int) (ky.charkt(i)); sun sun &0x7fffffff: return sum % tableSize; // automatically applies nod 2.(32) // 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 // create haa? table of size a: that u ea linear probing II create a haa table of aize az that uses quadratie probing // create a has table of size sz that uses doubl bashing with D sz R If expty the hash table and reset the statistics A soap:Keeps you elean Insert record "Keeps you clean vith "soap" as its key // Prist ase of the lines "Key aoap nserted at locatia 8". *Key soap already exista". OR I Table has overfloved". In the latter case, the record isn't inserted R sin /Delete the record that has sin" as its key I/ Print ose of the lines "Key sin deleted" OR "Key sin not found 3 fortune II Search for the key "fortune II Print ose of the linea "Key fortune: then the record correaponding to that key // then the text found at location #.. OR Key fortune 20t found. // Print the line "Membership is #. where # is te number of records tored in the table Print a liat of the elecents in the Table ia the order of their position in the table // one record per line in the form-# key:Record, where # is the position in tbe table Print the folloving three lines // Total probes during isserts# // Total Drobes during unsuccessful searches " # // Total probes during #accessful earches- / where the bash marks indicate integer values / The end of the input file The first command and will a L, or D Oaly one LQ. D command will be present in any data file. The hash table size could be as large as 10000 and will always be prime. YOU WILL ONLY HAVE TO IMPLEMENT ONE OF THE TYPES OF HASH TABLES DEPENDING ON THE FIRST CHARACTER OF YOUR LAST NAME: A-H: Implement type L I-N: Implement type Q O-Z: Implement type D Sample Input Sample Output Key ant inserted at loeation lKey goat inserted at location 1 iKey frog inserted at location IKey horse inserted at location 0 lKey nouse inaerted at locatien 2 Menberahip ia IKey goat already ezists IKey goat deleted IKey goat not foand 10 horse:Equua ferus caballus 12 souse: Manalsa Rodeatia Mus 4 frog:Anphibia Raza S ant:Anthropoda Messor IKey frog Anphibia Rana found at location 4 IKey ?0use :Mana2 ia Bodeata Hus found at locatioa 2 IKey mouse :Manalia Rodentia Mus found at location 2 ITotal probes during inserts7 Total probes during unsuccessful searches 0 Total probes during succesnfel searches- s ?6 A antiAnthrepoda Messor A goat Capra aegagrus hircus A frog:Amphibia Rana A souse:Manalia Rodeatia Mas A goatiA four legged friesd D goat D goat 8 souse 3. Name your souroe file as NNzFiF2P3 java where your given name begins with the characters NMN2 and your family name begins with the characters FiF2. For example my nane is Ivor Page, so my source file will be called IVPAP3java. Note that in all but the "java" extension, the characters are upper case . Your program must not output any prompts. Its output must exactly match the format of the Sample Output above 5. Do not use any Java Collection Classes, except Strings and arrays. If in doubt, ask me
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started