Separate chaining

Hash table uses key and value for storing the elements. If the key has duplicate value, it may lead to hashing Collision. Separate Chaining is one of name collision solution. It is a scheme which each position in the hash table has a list to handle collisions.

Write a program to implement separate chaining in hash table?

Algorithm Explanation

	Hash table store keys and values. The keys is unique in hash table. If the two key values same, the name collision happens. Hashtable uses many methods to resolve name collisions.
	The separate chaining is one of the methods to solve the name, Collison. The separate chaining uses linked list to store the elements when the name collision occurs.
	It uses sorted linked list to store the elements. The sorted list uses links which maintain the sort order. If the program inserts any element, it re-arrange the numbers in the list and insert the value.
	The find method passes the key of the hash table. The linked list find method find the hash key and return the value.

Source Code

package com.dsacode.DataStructre.hashtable;
 
import java.io.IOException;
 
class Link {
      public int data;
      public Link next;
 
      public Link(int d) {
        data = d;
      }
      public void displayLink() {
        System.out.print(data + ",");
      }
}
 
 
class SortedList{
     
    private Link first;
     
    public SortedList() {
        first = null;
    }
 
    public void insert(Link theLink){
      int key = theLink.data;
      Link previous = null;
      Link current = first;
 
      while (current != null && key > current.data) {
        previous = current;
        current = current.next;
      }
       
      if (previous == null)
        first = theLink;
      else
        previous.next = theLink;
       
      theLink.next = current;
    }
 
    public void delete(int key){
      Link previous = null;
      Link current = first;
     
      while (current != null && key != current.data) {
        previous = current;
        current = current.next;
      }
 
      if (previous == null)
        first = first.next;      
      else
        previous.next = current.next;
    }
 
    public Link find(int key) {
      Link current = first;
      while (current != null && current.data <= key) {
        if (current.data == key)
          return current; 
        current = current.next;
      }
      return null;
    }
 
    public void displayList() {
      Link current = first;
      while (current != null){
        current.displayLink();
        current = current.next;
      }
       
    }
}
 
public class SeparateChaining {
 
     
         private SortedList[] hashArray;
 
          private int arraySize;
 
          public SeparateChaining(int size) {
            arraySize = size;
            hashArray = new SortedList[arraySize];
            for (int i = 0; i < arraySize; i++)
              hashArray[i] = new SortedList();
          }
 
          public void displayTable() {
            for (int j = 0; j < arraySize; j++) {
              hashArray[j].displayList();
            }
          }
 
          public int hashFunc(int key) {
            return key % arraySize;
          }
 
          public void insert(Link theLink) {
            int key = theLink.data;
            int hashVal = hashFunc(key);
            hashArray[hashVal].insert(theLink);
          }
 
          public void delete(int key) {
            int hashVal = hashFunc(key);
            hashArray[hashVal].delete(key);
          }
 
          public Link find(int key) {
            int hashVal = hashFunc(key);
            Link theLink = hashArray[hashVal].find(key);
            return theLink;
          }
 
          public static void main(String[] args) throws IOException {
            SeparateChaining hashTable = new SeparateChaining(10);
 
            hashTable.insert(new Link(12));
            hashTable.insert(new Link(67));
            hashTable.insert(new Link(80));
            hashTable.insert(new Link(99));
            hashTable.insert(new Link(34));
            hashTable.insert(new Link(23));
            hashTable.insert(new Link(11));
            hashTable.insert(new Link(76));
            hashTable.insert(new Link(23));
            hashTable.insert(new Link(60));
             
            System.out.println("Insert 10 items in the hash table");
            hashTable.displayTable();
            System.out.println("\n");
             
            System.out.println("Search '50' in the hash table");
            int aKey = 50;
            Link dataItem = hashTable.find(aKey);
            if (dataItem != null)
              System.out.println("Found " + aKey);
            else
              System.out.println("Could not find " + aKey);
             
            System.out.println();
            System.out.println("Search '80' in the hash table");
            aKey = 80;
            dataItem = hashTable.find(aKey);
            if (dataItem != null)
              System.out.println("Found " + aKey);
            else
              System.out.println("Could not find " + aKey);
             
          }
 
}
   

Output

Insert 10 items in the hash table
60,80,11,12,23,23,34,76,67,99,
 
Search '50' in the hash table
Could not find 50
 
Search '80' in the hash table
Found 80