Answered step by step
Verified Expert Solution
Link Copied!

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

image text in transcribed

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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Murach's SQL Server 2012 For Developers

Authors: Bryan Syverson, Joel Murach, Mike Murach

1st Edition

1890774693, 9781890774691

More Books

Students also viewed these Databases questions

Question

=+g. Does it deliver one, instantly understandable message?

Answered: 1 week ago

Question

=+e. Does it entertain, inform and/or engage the reader?

Answered: 1 week ago

Question

=+h. Do all of the related materials project one cohesive message?

Answered: 1 week ago