Hash Chaining With Java

HashChain.java

/*
	HashTable Object that solves hash collisions with chains
	Program 7 
	Written by: Justin Tew, [email protected]
	Created with the help of Dr. Xu's hash table psudocode

*/
  
   public class HashChain
   {
      final static int CAPACITY = 5; //USED BY THE toString VERY IMPORTANT MUST BE THE SAME AS THE GIVEN INPUT ARGUMENT WHEN CREATING A HASHCHAIN OBJECT
      protected SLinkedList[] HashTable; //referrence to the actual array of Singly Linked Lists (the hashtable)
      protected int size; //size is actually the number of nodes/students in the entire hashtable (size is not the best name for this value sorry)
   
   
      public HashChain(int cap)
      {
         size = 0;
         HashTable = new SLinkedList[cap];
      	
         for (int i = 0; i < cap; i++)
         {
            HashTable[i] = new SLinkedList();
         
         }
      
      
      }
   
   
      public int getSize() { //gets the amount of nodes/students in the entire hash table  (a method to get the number size of the array would be nice too but i just made a constant)
         return size; }
   
   	//the actual Hash function 
      public int hash(int key)
      {
         return ((7 * key) + 29) %5; //h(x) = 7x + 29 mod(5)
      }
   	
   	//gets a student using their id
      public Node getStudent (int key)
      {
         Node temp = HashTable[hash(key)].search(key);
      	
         if (temp == null)
            return null;
         	
         else
         {
            return temp;
         }
      
      }
      
   	//put method... used to add students to the hash table
      public int put(Node NewOne)//very interesting, i never knew you could just call a method and ignore the return type (for example i call hashtable.put without doing anything with the int returned in my other class)
      {
         Node temp = HashTable[hash(NewOne.getId())].search(NewOne.getId());
      	
         if (temp == null)
         {
            HashTable[hash(NewOne.getId())].addLast(NewOne);
            size ++;
            return -9999; //also un used if im not mistaken
         }
         
         else
         {
            int old_id = temp.getId(); //not required but it makes it easy to see what is going on for me
            HashTable[hash(NewOne.getId())].addAfter(temp,NewOne); //this works, i didnt think it would, test more to make sure
            HashTable[hash(NewOne.getId())].delete(temp.getId());
            return old_id; //this value isnt used 
         }
      
      }
      
   	//removes any given node from the table using their id as a key
      public Node remove(int key)
      {
         Node temp = HashTable[hash(key)].delete(key);
      	
         if (temp == null)
            return null;
         	
         else
         {
            size --;
            return temp;
         
         }
      	
      
      }
   	
   	
   	//toString formatted to look like a hash table 
      public String toString()
      {
      
         StringBuilder all = new StringBuilder();
         
         for(int i = 0; i < CAPACITY; i++)
         {
            all.append(HashTable[i].toString() + " \n");
         }
      	
         return all.toString();
      
      
      }
   	
   	
   	
   
   }

Node.java

/*
	Node object
	Program 7 
	Written by: Dr. Xu
	Edited by: Justin Tew, [email protected]

*/

   public class Node{
      private String name; 
      private int id;
      private Node next;  //the link referencing to the next node in the link list.
    
      public Node(int id, String name, Node next)
      {
         this.id = id;
         this.name = name; 
         this.next = next; 
      }
   
      public String getName() { 
         return name; }
      public int getId() {
         return id; }
      public Node getNext() { 
         return next; }
      public void setName(String name) { this.name = name; }
      public void setNext(Node next) { this.next = next; }
      public void setId(int id) { this.id = id; }
		
		public String toString()
		{
			StringBuilder s = new StringBuilder();
			s.append(this.id);
			return s.toString();
		}
   }

SLinkedList.java

/*
	Singly Linked List
	Program 7 
	Written by: Dr. Xu
	Edited by: Justin Tew, [email protected]

*/
   public class SLinkedList{
      protected Node head; 
      protected long size; 
    
      public SLinkedList(){
         head = null; 
         size = 0;
      }
   
    /* add node v at the beginning of the list */
      public void addFirst(Node v){
         if(v == null)
            return; 
      
         v.setNext(head);
         head = v; 
         size ++;
      }
    
    /* add node v at the end of the list */
      public void addLast(Node v){
         if(size == 0)
            addFirst(v);
         else{
            Node cur; 
            for(cur = head; cur.getNext() != null; cur = cur.getNext())
               ;
            v.setNext(null);
            cur.setNext(v); 
            size ++; 
         }
      }
   
    /* remove the first node of the list */
      public void removeFirst(){
         if(size == 0)
            return; 
      
         Node old_head = head; 
         head = head.getNext(); 
         size --; 
         old_head.setNext(null);
      
      //If using C or C++, the memoery for the deleted node needs to be freed. 
      }
   
    /* remove the last node of the list */
      public void removeLast(){
         if(size == 0)
            return; 
      
         if(size == 1)
            removeFirst();
      
         Node cur; 
         for(cur = head; cur.getNext().getNext() != null; cur = cur.getNext())
            ;
         cur.setNext(null);
         size --;
      
      //If using C or C++, the memoery for deleted node needs to be freed. 
      }
   
    /* Insert node v right after node u*/
      public void addAfter(Node u, Node v){
         if(u == null)
            return; 
      
         v.setNext(u.getNext()); 
         u.setNext(v);
         size ++;
      }
   
    /* Insert node v right before node u*/
      public void addBefore(Node u, Node v){
         if(u == null)
            return;
         if(u == head)
            addFirst(v);
         else{
            Node cur; 
            for(cur = head; cur.getNext() != u; cur = cur.getNext())
               ;
            v.setNext(u);
            cur.setNext(v);
            size ++;
         }
      }
    
    /* remove the node that is right after v */
      public void removeAfter(Node v){
         if(v == null)
            return;
      
         if(v.getNext() == null)
            return; 
      
         Node deleted = v.getNext(); 
         v.setNext(v.getNext().getNext());
         deleted.setNext(null); 
         size --;
      }
   	

   	
   	
   
    /* remove the node that is right before v */
      public void removeBefore(Node v){
         if(v == null)
            return;
         if(v == head)
            return; 
      
         if(head.getNext() == v){
            Node old_head = head; 
            head = v;
            old_head.setNext(null);
         }
         else{
            Node cur; 
            for(cur = head; cur.getNext().getNext() != v; cur = cur.getNext())
               ;
            Node deleted = cur.getNext(); 
            cur.setNext(v);
            deleted.setNext(null);
         }
         size --; 
      }
    
    /* The concatenation of all the elements in the list */
      public String toString(){
         StringBuilder all = new StringBuilder();
         for(Node cur = head; cur != null; cur = cur.getNext())
            all.append("(" + cur.getId() + ", " + cur.getName() + ") ");
         return all.toString();
      }
   
      public Node search(int key)
      {
         if (size == 0)
            return null;
         if (head == null)
            return null;
         if (head.getId() == key)
            return head;
         
         else
         {
            for (Node cur = head.getNext(); cur != null; cur = cur.getNext())
            {
               if (cur.getId() == key)
                  return cur;
            
            } 
         }
      
         return null;
      }
   
   	
   	
   	//Not going to lie i think this method has bugs... i just can't find any
      public Node delete(int key)//delete by id
      {
         if (size == 0)
            return null;
      	
         if (head.getId() == key)
         {
            Node old_head = head; //not used
            removeFirst();
            return old_head;
         }
         
         else //this is where i think the bugs are but i cant get it to break/give me a error
         {
            for (Node cur = head.getNext(); cur != null; cur = cur.getNext())
            {
               if (cur.getId() == key)
               {
                  Node prev = head;
                  for(; prev.getNext() != cur; prev = prev.getNext());
                  {
                  }
                  prev.setNext(cur.getNext());
                  cur.setNext(null); 
                  return cur;
               }
            
            
            }
         
            
         }
         Node d = new Node(-999,null,null); //dumby node
         return d;
      }
   }

Test_HashChain.java

/*
	Class to test the HashChain object
	Program 7 
	Written by: Justin Tew, [email protected]

*/
   import java.util.Scanner; //imports
   import java.io.*;
   
   
   public class Test_HashChain
   {
      public static void main(String[] args) throws IOException 
      {
         if (args.length == 1) 
         {
            HashChain Hashtable = new HashChain(5); //creates a Hashchain object with capacity 5 (this number must be the same as the fixed constant CAPACITY in the HashChain class)
            Scanner file = new Scanner(new File(args[0])); //file reference
            while (file.hasNextLine()) //add all the students to the hash table
            {
               String line = file.nextLine();
               String[] info;
               info = line.split(",");
               int id = Integer.parseInt(info[0]);
               Hashtable.put(new Node(id, info[1], null));
            }
            int choice = 0; //the users choice of action
            Scanner kb = new Scanner(System.in); //keyboard reference 
            while (choice != 5) //the menu
            {
               System.out.println("Choose one of the following options.");
               System.out.println("====================================");
               System.out.println("1) insert/update a new student record");
               System.out.println("2) delete a student record");
               System.out.println("3) search for a student record");
               System.out.println("4) print all the student records");
               System.out.println("5) quit");
               System.out.println();
               System.out.print("Your choice:");
               choice = kb.nextInt();
            	
               if (choice == 1) //insert/update a student record
               {
                  System.out.println("Input the student id:");
                  int id = kb.nextInt();
                  System.out.println("Input the student name:");
                  String name = kb.next();
                  Node target = Hashtable.getStudent(id);
               	
                  if (target == null)
                  {
                     Hashtable.put(new Node(id,name,null));
                     System.out.println("The new student has been added successfully");
                  }
                  else
                  {
                     Hashtable.put(new Node(id,name,null));
                     System.out.println("The student was existing and the record has been updated");
                  }	
               }
               if (choice == 2) //delete a student record
               {
                  System.out.println("Input the student id:");
                  int id = kb.nextInt();
                  Node target = Hashtable.getStudent(id);
                  if (target == null)
                  {
                     System.out.println("No such student.");
                  }
                  else
                  {
                     Hashtable.remove(id);	
                     System.out.println("The student has been deleted successfully");
                  }
               
               }
               if (choice == 3)//search for a student record
               {
                  System.out.println("Input the student id:");
                  int id = kb.nextInt();
                  Node target = Hashtable.getStudent(id);
                  if (target == null)
                     System.out.println("No such student");
                  else
                  {
                     System.out.println("Student id:" + target.getId() + ". Student name:" + target.getName() + ".");
                  }
               	
               }
               if (choice == 4)//print out the hashtable
               {
                  System.out.println(Hashtable);
               }
            
            }
         }
         
         else //if incorrect number of arguments given
         {
            System.out.println("i need one and only one argument");
         }
      }
   }