3.2 Class Dictionary This class implements a dictionary using a hash table in which collisions are...

Transcribed Image Text:

3.2 Class Dictionary This class implements a dictionary using a hash table in which collisions are resolved using separate chaining. The hash table will store objects of the class Record. You will decide on the size of the table, keeping in mind that the size of the table must be a prime number. You must design your hash function so that it produces few collisions. A bad hash function that induces many collisions will result in a lower mark. You are required to use a polynomial hash function. As mentioned above, you cannot use Java's hashCode () method in your hash function. For this class, you must implement all the public methods in the following interface: public interface DictionaryADT { public int put (Record rec) throws DuplicatedKeyException; public void remove (String key) throws InexistentKeyException; public Record get (String key); public int numRecords (); } The descriptions of these methods follows: Inserts the given This method must throw a public int put (Record rec) throws DuplicatedKeyException: Record object referenced by rec in the dictionary. DuplicatedKeyException (see below) if the string stored in the object referenced by rec is already in the dictionary. You are required to implement the dictionary using a hash table with separate chaining. To determine how good your design is, we will count the number of collisions produced by your hash function. Method put must return the value 1 if the insertion of the object referenced by rec into the hash table produces a collision, and it must return the value 0 otherwise. In other words, if for example your hash function is h(key) and the name of your table is T, this method must return the value 1 if the list in entry T[h(rec.getKey())] of the table already stores at least one element; it must return 0 if that list was empty before adding the new record. public void remove (String key) throws InexistentKeyException: Removes the Record object containing string key from the dictionary. Must throw a InexistentKeyException if the hash table does not store any Record object with the given key value. public Record get(String key): A method which returns the Record object stored in the hash table containing the given key value, or null if no Record object stored in the hash table contains the given key value. public int numRecords (): Returns the number of Record objects stored in the hash table. Since your Dictionary class must implement all the methods of the DictionaryADT interface, the declaration of your method should be as follows: public class Dictionary implements Dictionary ADT You can download the file DictionaryADT.java from OWL. The only other public method that you can implement in the Dictionary class is the constructor method, which must be declared as follows public Dictionary (int size) this initializes a dictionary with an empty hash table of the specified size. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e. not accessible to other classes). Hint. You might want to implement a class Node storing an object of the class Record to construct the linked lists associated to the entries of the hash table. You do not need to follow this suggestion. You can implement the lists associated with the entries of the table in any way you want. 3.2 Class Dictionary This class implements a dictionary using a hash table in which collisions are resolved using separate chaining. The hash table will store objects of the class Record. You will decide on the size of the table, keeping in mind that the size of the table must be a prime number. You must design your hash function so that it produces few collisions. A bad hash function that induces many collisions will result in a lower mark. You are required to use a polynomial hash function. As mentioned above, you cannot use Java's hashCode () method in your hash function. For this class, you must implement all the public methods in the following interface: public interface DictionaryADT { public int put (Record rec) throws DuplicatedKeyException; public void remove (String key) throws InexistentKeyException; public Record get (String key); public int numRecords (); } The descriptions of these methods follows: Inserts the given This method must throw a public int put (Record rec) throws DuplicatedKeyException: Record object referenced by rec in the dictionary. DuplicatedKeyException (see below) if the string stored in the object referenced by rec is already in the dictionary. You are required to implement the dictionary using a hash table with separate chaining. To determine how good your design is, we will count the number of collisions produced by your hash function. Method put must return the value 1 if the insertion of the object referenced by rec into the hash table produces a collision, and it must return the value 0 otherwise. In other words, if for example your hash function is h(key) and the name of your table is T, this method must return the value 1 if the list in entry T[h(rec.getKey())] of the table already stores at least one element; it must return 0 if that list was empty before adding the new record. public void remove (String key) throws InexistentKeyException: Removes the Record object containing string key from the dictionary. Must throw a InexistentKeyException if the hash table does not store any Record object with the given key value. public Record get(String key): A method which returns the Record object stored in the hash table containing the given key value, or null if no Record object stored in the hash table contains the given key value. public int numRecords (): Returns the number of Record objects stored in the hash table. Since your Dictionary class must implement all the methods of the DictionaryADT interface, the declaration of your method should be as follows: public class Dictionary implements Dictionary ADT You can download the file DictionaryADT.java from OWL. The only other public method that you can implement in the Dictionary class is the constructor method, which must be declared as follows public Dictionary (int size) this initializes a dictionary with an empty hash table of the specified size. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e. not accessible to other classes). Hint. You might want to implement a class Node storing an object of the class Record to construct the linked lists associated to the entries of the hash table. You do not need to follow this suggestion. You can implement the lists associated with the entries of the table in any way you want.