Question

Please implement a HashSet using Separate Chaining to deal with collisions.

public interface SetInterface<T> {

   public boolean add(T item);
   public boolean remove(T item);
   public boolean contains(T item);
   public int size();
   public boolean isEmpty();
   public void clear();
   public Object[] toArray();
  
}

public class HashSet<T> implements SetInterface<T> {
   //============================================================================= Inner node class
   private class Node<E> {
       private E data;
       private Node<E> next;

       public Node(E data) {
           this.data = data;
           this.next = null;
       }
   }

   //============================================================================= Properties
   private Node<T>[] buckets;   // An array of nodes
   private int size;
   private static final double LOAD_FACTOR = .6;
   private static final int DEFAULT_SIZE = 11; // should be prime

   //============================================================================= Constructors
   public HashSet() {
       buckets = (Node<T>[]) new Node[DEFAULT_SIZE];
       size = 0;
   }

   public HashSet(T[] items) {
       //************************************************************* TO-DO
       // Make a call to your empty constructor and then somehow fill
       // this set with the items sent in

   }
  
   //============================================================================= Methods
   @Override
   public boolean add(T item) {
       //************************************************************* TO-DO
       // Check to see if item is in the set. If so return false. If not,
       // check if the LOAD_FACTOR has already been exceeded by the previous
       // add and if so, call the resize() before adding.
      

       return true; // returns true because we know it's been added
   }

   @Override
   public boolean remove(T item) {
       //************************************************************* TO-DO
       // To remove an item, you are removing from a linked chain of nodes.
       // Our algorithm is to copy the data from that head node to the node to be
       // removed, and then remove the head node.
       boolean success = false;

       return success;
   }

   @Override
   public boolean contains(T item) {
       //************************************************************* TO-DO
       // A one-line method that calls
       // the find() method
       return false;
   }

   @Override
   public void clear() {
       //************************************************************* TO-DO
       // sets all items in the array to null
   }

   @Override
   public int size() {
       return size;
   }

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

   @Override
   public Object[] toArray() {
       Object[] result = new Object[size];

       // The structure of this is similar to the structure of toString
       //************************************************************* TO-DO

      
       return result;
   }

   // Return a string that shows the array indexes, and the items in each bucket
   public String toString() {
       String result = "";
       String format = "[%" + ("" + buckets.length).length() + "d] ";
      
       // Loop through the array of buckets. A bucket is just a chain of linked nodes.
       // For each bucket, loop through the chain, displaying the contents of the bucket
       for (int i = 0; i < buckets.length; i++) {
           result += String.format(format, i);
          
           // add the data in bucket i
           Node curr = buckets[i];
           while (curr != null) {
               result += curr.data + " ";
               curr = curr.next;
           }
           result += "\n";
       }
       return result;
   }

   // helper methods

   // Adds all items in an array to this set.
   // resize() could make use of this.
   // One of the constructors can make use of this too.
   private void addAll(T[] items) {
       //************************************************************* TO-DO
       // loop to add each item to the set (calls add())
   }

   private void resize() {
      
       T[] allData = (T[]) toArray();   // toArray() is method above
       buckets = (Node<T>[]) new Node[ firstPrime(2 * buckets.length) ];
       size = 0;
      
       //************************************************************* TO-DO
       // now, allData contains all the data from the set
       // and buckets points to a new empty array
       // call addAll to do the adding
       // double-check size when you are done

   }

   // Very important
   // Returns the node containing a particular item, or null if not found.
   // Useful for add, remove, and contains. This is a PRIVATE helper method
   private Node<T> find(T item) {
       // Step 1:    find the index of where this T would be...
       int index = getHashIndex(item);
      
       // Step 2:    using the index, check the linked nodes at that array index
       // by looping through all nodes of the bucket      
       Node<T> curr = buckets[index];  
       while(curr != null && !curr.data.equals(item))
           curr = curr.next;
      
       return curr;   // we will either be returning null (not found) or the node
                       // that contains the node we are looking for
   }

   // Gets the index of the bucket where a given string should go,
   // by computing the hashCode, and then compressing it to a valid index.
   private int getHashIndex(T item) {
       // item will always have the hashCode() method.
       // From the
       int hashCode = item.hashCode();
       int index = -1;   // calculate the actual index here using the
                       // hashCode and length of of the buckets array.
      
       //************************************************************* TO-DO
      
       return index;
   }

   // Returns true if a number is prime, and false otherwise
   private static boolean isPrime(int n) {
       if (n <= 1)   return false;
       if (n == 2)   return true;

       for (int i = 2; i * i <= n; i++)
           if (n % i == 0)   return false;
      
       return true;
   }

   // Returns the first prime >= n
   private static int firstPrime(int n) {
       while (!isPrime(n)) n++;
       return n;
   }

}

public class Tester {
  
   public static void main(String[] args) {

       HashSet<String> set = new HashSet<>();
       System.out.println("true? " + set.isEmpty());
       System.out.println("true? " + set.add("cat"));
       System.out.println("true? " + set.add("dog"));
       System.out.println("false? " + set.add("dog"));
       System.out.println("2? " + set.size());
       System.out.println("false? " + set.isEmpty());
       System.out.println(set.toString());

       for(char c : "ABCDEFGHIJKLMNOPQUSTUVWXYZ".toCharArray())
           set.add("" + c);
      
       System.out.println(set.toString());
   }
  
}

Answer 1

CODE:

import java.util.Scanner;
 
/* Node for singly linked list */
class SLLNode
{
    SLLNode next;
    int data;
 
    /* Constructor */
    public SLLNode(int x)
    {
        data = x;
        next = null;
    }
}
 
/* Class HashTableChainingSinglyLinkedList */
class HashTableChainingSinglyLinkedList
{
    private SLLNode[] table;
    private int size ;
 
    /* Constructor */
    public HashTableChainingSinglyLinkedList(int tableSize)
    {
        table = new SLLNode[ nextPrime(tableSize) ];
        size = 0;
    }
    /* Function to check if hash table is empty */
    public boolean isEmpty()
    {
        return size == 0;
    }
    /* Function to clear hash table */
    public void makeEmpty()
    {
        int l = table.length;
        table = new SLLNode[l];
        size = 0;
    }
    /* Function to get size */
    public int getSize()
    {
        return size;
    }
    /* Function to insert an element */
    public void insert(int val)
    {
        size++;
        int pos = myhash(val);        
        SLLNode nptr = new SLLNode(val);                
        if (table[pos] == null)
            table[pos] = nptr;            
        else
        {
            nptr.next = table[pos];
            table[pos] = nptr;
        }    
    }
    /* Function to remove an element */
    public void remove(int val)
    {
        int pos = myhash(val);    
        SLLNode start = table[pos];
        SLLNode end = start;
        if (start.data == val)
        {
            size--;
            table[pos] = start.next;
            return;
        }
        while (end.next != null && end.next.data != val)
            end = end.next;
        if (end.next == null)
        {
            System.out.println("\nElement not found\n");
            return;
        }
        size--;
        if (end.next.next == null)
        {
            end.next = null;
            return;
        }
        end.next = end.next.next;
        table[pos] = start;
    }
    /* Function myhash */
    private int myhash(Integer x )
    {
        int hashVal = x.hashCode( );
        hashVal %= table.length;
        if (hashVal < 0)
            hashVal += table.length;
        return hashVal;
    }
    /* Function to generate next prime number >= n */
    private static int nextPrime( int n )
    {
        if (n % 2 == 0)
            n++;
        for ( ; !isPrime( n ); n += 2);
 
        return n;
    }
    /* Function to check if given number is prime */
    private static boolean isPrime( int n )
    {
        if (n == 2 || n == 3)
            return true;
        if (n == 1 || n % 2 == 0)
            return false;
        for (int i = 3; i * i <= n; i += 2)
            if (n % i == 0)
                return false;
        return true;
    }
    public void printHashTable ()
    {
        System.out.println();
        for (int i = 0; i < table.length; i++)
        {
            System.out.print ("Bucket " + i + ":  ");             
            SLLNode start = table[i];
            while(start != null)
            {
                System.out.print(start.data +" ");
                start = start.next;
            }
            System.out.println();
        }
    }   
}
 
/* Class HashTableChainingSinglyLinkedListTest */
public class HashTableChainingSinglyLinkedListTest
{ 
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Hash Table Test\n\n");
        System.out.println("Enter size"); 
        /* Make object of HashTableChainingSinglyLinkedList */
        HashTableChainingSinglyLinkedList htcsll = new HashTableChainingSinglyLinkedList(scan.nextInt() );
 
        char ch;
        /*  Perform HashTableChainingSinglyLinkedList operations  */
        do    
        {
            System.out.println("\nHash Table Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. remove");
            System.out.println("3. clear");
            System.out.println("4. size"); 
            System.out.println("5. check empty");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                htcsll.insert( scan.nextInt() ); 
                break;                          
            case 2 :                 
                System.out.println("Enter integer element to delete");
                htcsll.remove( scan.nextInt() ); 
                break;                        
            case 3 : 
                htcsll.makeEmpty();
                System.out.println("Hash Table Cleared\n");
                break;
            case 4 : 
                System.out.println("Size = "+ htcsll.getSize() );
                break; 
            case 5 : 
                System.out.println("Empty status = "+ htcsll.isEmpty() );
                break;        
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /* Display hash table */ 
            htcsll.printHashTable();  
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');  
    }
}