Question

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 Data. You will decide on the size of the table, keeping in mind that the size of the table must be a prime number. A table of size between 5000-10000, should work well. 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 encouraged 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(Data record) throws DuplicatedKeyException;

public void remove(String key) throws InexistentKeyException;

public Data get(String key); public int numDataItems(); }

The descriptions of these methods follows:

public int put(Data record) throws DuplicatedKeyException: Inserts the given Data object referenced by record in the dictionary. This method must throw a DuplicatedKeyException (see below) if the string stored in the object referenced by record 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 record 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(record.getKey())] of the table already stores at least one element; it must return 0 if that list was empty before the insertion.

public void remove(String key) throws InexistentKeyException: Removes the Data object containing string key from the dictionary. Must throw a InexistentKeyException (see below) if the hash table does not store any Data object with the given key value.

public Data get(String key): A method which returns the Data object stored in the hash table containing the given key value, or null if no Data object stored in the hash table contains the given key value.

public int numDataItems(): Returns the number of Data 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 DictionaryADT 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 Data 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.

File :

Dictionary ADT

public interface DictionaryADT {
    public int put (Data record) throws DuplicatedKeyException;
    public void remove (String config) throws InexistentKeyException;
    public Data get (String config);
    public int numDataItems();
}

DATA.java :

public class Data {
    private String key ;
    private int score ;
    private int level ;
    public Data(String key, int score, int level) {
        this.key = key;
        this.score = score;
        this.level = level;
    }
    public String getKey(){
        return key ;
    }
    public int getScore(){
        return score ;
    }
    public int getLevel(){
        return level ;
    }
}

Answer 1

// Java program to demonstrate implementation of our
// own hash table with chaining for collision detection
import java.util.ArrayList;

// A node of chains
class HashNode<K, V>
{
   K key;
   V value;

   // Reference to next node
   HashNode<K, V> next;

   // Constructor
   public HashNode(K key, V value)
   {
       this.key = key;
       this.value = value;
   }
}

// Class to represent entire hash table
class Map<K, V>
{
   // bucketArray is used to store array of chains
   private ArrayList<HashNode<K, V>> bucketArray;

   // Current capacity of array list
   private int numBuckets;

   // Current size of array list
   private int size;

   // Constructor (Initializes capacity, size and
   // empty chains.
   public Map()
   {
       bucketArray = new ArrayList<>();
       numBuckets = 10;
       size = 0;

       // Create empty chains
       for (int i = 0; i < numBuckets; i++)
           bucketArray.add(null);
   }

   public int size() { return size; }
   public boolean isEmpty() { return size() == 0; }

   // This implements hash function to find index
   // for a key
   private int getBucketIndex(K key)
   {
       int hashCode = key.hashCode();
       int index = hashCode % numBuckets;
       return index;
   }

   // Method to remove a given key
   public V remove(K key)
   {
       // Apply hash function to find index for given key
       int bucketIndex = getBucketIndex(key);

       // Get head of chain
       HashNode<K, V> head = bucketArray.get(bucketIndex);

       // Search for key in its chain
       HashNode<K, V> prev = null;
       while (head != null)
       {
           // If Key found
           if (head.key.equals(key))
               break;

           // Else keep moving in chain
           prev = head;
           head = head.next;
       }

       // If key was not there
       if (head == null)
           return null;

       // Reduce size
       size--;

       // Remove key
       if (prev != null)
           prev.next = head.next;
       else
           bucketArray.set(bucketIndex, head.next);

       return head.value;
   }

   // Returns value for a key
   public V get(K key)
   {
       // Find head of chain for given key
       int bucketIndex = getBucketIndex(key);
       HashNode<K, V> head = bucketArray.get(bucketIndex);

       // Search key in chain
       while (head != null)
       {
           if (head.key.equals(key))
               return head.value;
           head = head.next;
       }

       // If key not found
       return null;
   }

   // Adds a key value pair to hash
   public void add(K key, V value)
   {
       // Find head of chain for given key
       int bucketIndex = getBucketIndex(key);
       HashNode<K, V> head = bucketArray.get(bucketIndex);

       // Check if key is already present
       while (head != null)
       {
           if (head.key.equals(key))
           {
               head.value = value;
               return;
           }
           head = head.next;
       }

       // Insert key in chain
       size++;
       head = bucketArray.get(bucketIndex);
       HashNode<K, V> newNode = new HashNode<K, V>(key, value);
       newNode.next = head;
       bucketArray.set(bucketIndex, newNode);

       // If load factor goes beyond threshold, then
       // double hash table size
       if ((1.0*size)/numBuckets >= 0.7)
       {
           ArrayList<HashNode<K, V>> temp = bucketArray;
           bucketArray = new ArrayList<>();
           numBuckets = 2 * numBuckets;
           size = 0;
           for (int i = 0; i < numBuckets; i++)
               bucketArray.add(null);

           for (HashNode<K, V> headNode : temp)
           {
               while (headNode != null)
               {
                   add(headNode.key, headNode.value);
                   headNode = headNode.next;
               }
           }
       }
   }

   // Driver method to test Map class
   public static void main(String[] args)
   {
       Map<String, Integer>map = new Map<>();
       map.add("this",1 );
       map.add("coder",2 );
       map.add("this",4 );
       map.add("hi",5 );
       System.out.println(map.size());
       System.out.println(map.remove("this"));
       System.out.println(map.remove("this"));
       System.out.println(map.size());
       System.out.println(map.isEmpty());
   }
}