Hashing in Seperate Chainning

The file HashInt.txt (in a separate file) contains 100,000 integers all randomly chosen between 1 and 1,000,000 (there might be some repetitions).This is considered as an array of integers where the ith row of the file gives you the ith entry of the array. Given below are 9 "target sums", in increasing order: 231552, 234756, 596873, 648219, 726312, 981237, 988331, 1277361, 1283379. You are required to implement the hash table-based algorithm and determine, for each of the 9 target sums x, whether or not x can be formed as the sum of two entries in the given array.

Your answer should be in the form of a 9-bit string, with a 1 indicating "yes" for the corresponding target sum and 0 indicating "no". For example, if you discover that all of the target sums except for the 5th and the 7th one (i.e., except for 726312 and 988331) can be formed from pairs from the input file, then your answer should be "111101011" (without the quotes). The answer should be in the same order as the target sums listed above (i.e., in increasing order of the target).

Solution to the above problem

According to our solution we used Separate Chaining concept to implement the hash table. Because in Open addressing methods that have primary clustering and secondary clustering scenarios. And also separate chaining not critical to make the table size a prime number, as it is with the quadratic probes and double hashing. When we use the open addressing concept, the exception is the plenty of memory is available and size should not expand after the table is created. Hash Table consists of 10000 slots which each has its own list to keep data. Each line read from the text file and gets the hash value to select the corresponding slot in the Hash Table for data.

We used 10000 slots, because of its help to constant time (O (1)) to access the corresponding slot for each data. In this implementation duplicates are allowed. All items with the same hash key should be inserted in the same list. So if we want to discover those elements we must search the entire list in both successful search and unsuccessful searches.

In our implementation we included the sorted list which not speeds up the successful search, but it could reduce the time of unsuccessful search. There insertion time gets increase, because the new item can’t just be inserted at the beginning of the list. But if the list gets too short the increase of the insertion time may not be important. That’s another reason for I selected the Hash Table size to 10000 slots.

According to the problem we must have to search the target sums inside the Hash table. As a result searching method uses frequently to find the sums in the Hash Table. To get the solution for that we reduce the each data from the text with target sums and find remaining element in the Hash Table. There should be happened successful searches and unsuccessful searches (element not at the list). In successful search that hashes to the appropriate list which associates with a slot in Hash table. And searches along the list for the element. In average time half the elements must be examined before the correct one is located (time: 1+loadfactor/2). This is guaranteed whether the lists are sorted or not. In an unsuccessful search, if the lists are unsorted all elements must be searched (time: 1+loadfactor). But in sorted list half the element must be examined in an unsuccessful search. That’s the reason for that we choose the sorted list structure.

Implementation in C#

SeperateChaining.cs 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Hashing
{
    class SeperateChaining
    {
        static void Main(string[] args)
        {
  
        int aKey;
        ListNode item;
        int size=1000;
        int[] targetSums={231552, 234756, 596873, 648219, 726312, 981237, 988331, 1277361, 1283379};
        int strlen = targetSums.Length;
        char[] str=new char[strlen];
        HashTable theHashTable=new HashTable(size);//Create the HashTable
     
        Console.WriteLine("\n---------------------------System Controllers-----------------------------------");
        Console.WriteLine("\n\t\t1. Insert Data to List : i");
        Console.WriteLine("\n\t\t2. Delete Data from the List : d");
        Console.WriteLine("\n\t\t3. Find specific value in the List : f");
        Console.WriteLine("\n\t\t4. Show the List : s");
        Console.WriteLine("\n\t\t5. Show the String bit pattern of target sums : t");
        Console.WriteLine("\n\t\t6. Exit from the System : e");
        Console.WriteLine("\n--------------------------------------------------------------------------------\n");
     
        //Read the File
        Readfile r=new Readfile();
        r.openFile();
        int[] dataSet = r.readFile();
        r.closeFile();//End of the file reading
     
        SeperateChaining sep_chain=new SeperateChaining();
     
        while(true){
            sep_chain.printMessage("\nEnter the control key : ");
            char choice=sep_chain.getChar();//Get the one character at a time to control the system

            switch(choice){
                case 's':
                    theHashTable.displayHashTable();//Display the whole HashTable
                    break;
                case 'i':
                    for(int k=0;k<dataSet.Length;k++){
                        aKey=dataSet[k];
                        item=new ListNode(aKey);//Create a new ListNode to each element
                        theHashTable.insert(item);//Insert ListNode to the HashTable
                    }
                    break;
                case 'd':
                    sep_chain.printMessage("\nEnter value to delete : ");
                    aKey=sep_chain.getInt();//Get the value to delete
                    item=theHashTable.search(aKey);//Find that element in the HashTable
                    if(item != null)
                        theHashTable.delete(aKey);//Element get hit then perform the delete operation
                    else
                        Console.WriteLine("Could not search "+aKey);
                    break;
                case 'f':
                    sep_chain.printMessage("\nEnter value to search : ");
                    aKey=sep_chain.getInt();
                    item=theHashTable.search(aKey);//Search the given element in the HashTable
                    if(item != null)
                        Console.WriteLine("Found "+aKey);
                    else
                        Console.WriteLine("Could not search "+aKey);
                    break;
                case 't':
                    int txtValue=0;
                    for(int k=0;k<targetSums.Length;k++){
                        for(int j=0;j<dataSet.Length;j++){
                            txtValue=(targetSums[k]-dataSet[j]);
                            if(txtValue < 0)
                                continue;
                            if(theHashTable.search(txtValue) != null){
                                str[k]='1';
                                break;
                            }
                            else
                                str[k]='0';
                        }
                    }
                    for(int k=0;k<targetSums.Length;k++){
                        Console.Write(str[k]+" ");
                    }
                    Console.WriteLine("\n");
                    break;
                case 'n':
                    Console.WriteLine("\nWARNING : Don't send NULL character again............\n");
                    break;
                case 'm':
                    Console.WriteLine("\nWARNING : Don't send more than one character.............\n");
                    break;
                case 'e':
                    Console.WriteLine("\nExit from the System sucessfully...................\n");
                    Environment.Exit(0);
                    break;
                default:
                    sep_chain.printMessage("\nYour input is invalid\n");
                    break;
                }
        }
      
    }
    //Print the message
    public void printMessage(string s){
        Console.Write(s);
    }
    //Read the console input as string
    public static string getString(){
        string s=Console.ReadLine();
        return s;
    }
    //Read the one character from the console input
    public char getChar(){
        string s=getString();
        if (s.Length == 0)
            return 'n';
        else if(s.Length > 1)
            return 'm';
        else
            return s[0];
    }
    //Cast the given searching or deleting element to int
    public int getInt(){
        string s=getString();
        int numValue;
        bool parsed = Int32.TryParse(s, out numValue);
        if (!parsed)
        {
            Console.WriteLine("\nWARNING : Could not parse '{0}' to an int.............",s);
            Console.Write("Return value become zero : ");
            return 0;
        }
        else
            return Int32.Parse(s);
    }
    }
}

HashTable.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Hashing
{
    class HashTable
    {
    private Array[] hashArray;//Array of list
    private int arrayLength;
    //Constructor for the array
    public HashTable(int size){
        arrayLength = size;
        hashArray = new Array[arrayLength];//Create the array
        for(int j=0;j<arrayLength;j++)
            hashArray[j] = new Array();//Fill array with dummy nodes
    }
    //Display the whole elements in the Hash Table
    public void displayHashTable(){
        for(int j=0;j<arrayLength;j++){
            Console.Write("("+j+") ");
            hashArray[j].displayArraySlots();
        }
    }
    //Hash key generating function
    public int hashFunction(int key){
        return key%arrayLength;
    }
    //Insert the ListNode
    public void insert(ListNode theListNode){
        int key=theListNode.value;
        int hashVal=hashFunction(key);//Generate the hash key to value
        hashArray[hashVal].insert(theListNode);//Insert the node in to corrosponding slot in the array
    }
    //Delete the ListNode
    public void delete(int key){
        int hashVal=hashFunction(key);
        hashArray[hashVal].delete(key);
    }
    //Find the ListNode
    public ListNode search(int key){
        int hashVal=hashFunction(key);
        ListNode theListNode=hashArray[hashVal].search(key);
        return theListNode;//Return the ListNode
    }
 
    }
}

Array.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Hashing
{
    class Array
    {
        private ListNode head;//Reference to the first list item

        public Array()
        {
            head = null;
        }
        //Insert the ListNode to Array
        public void insert(ListNode theListNode)
        {
            int key = theListNode.value;
            ListNode previous = null;//Start insert at initially
            ListNode current = head;
            //Searching until end of the list
            while (current != null && key > current.value)
            {
                previous = current;
                current = current.next;//Access the next item
            }
            //At the begining of list
            if (previous == null)
                head = theListNode;
            else//Not at the begining
                previous.next = theListNode;
            theListNode.next = current;
        }
        //Delete a given ListNode
        public void delete(int key)
        {
            ListNode previous = null;//Start at initially
            ListNode current = head;

            while (current != null && key != current.value)
            {
                previous = current;
                current = current.next;//Access the next link
            }
            //At the begining of list delete the first ListNode
            if (previous == null)
                head = head.next;
            else//Delete the current ListNode
                previous.next = current.next;
        }
        //Find the relevent ListNode
        public ListNode search(int key)
        {
            ListNode current = head;//Start at the begining

            //Find the corrosponding ListNode and then return it
            while (current != null && current.value <= key)
            {
                if (current.value == key)
                    return current;
                current = current.next;//Access the next item
            }
            return null;//Didn't find return null
        }
        //Display the elements associate with each slot in the array
        public void displayArraySlots(){
        Console.Write("head(Dummy Node) ");
     
        ListNode current = head;//Start at the begining of the list
     
        while(current != null){
            Console.Write("=>");
            current.displayListNode();
            current = current.next;//Access the next ListNode
        }
        Console.WriteLine("");
    }
    }
}

Readfile.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Hashing
{
    class Readfile
    {
    StreamReader buff=null;
    List<string> v=new List<string>();
 
    public void openFile(){
        try{
            buff=new StreamReader("HashInt.txt");//Open the file to read
        }catch(Exception ex){
            Console.WriteLine("File can't open : "+ex);
        }
    }
    //Read content of the file
    public int[] readFile(){
        try
        {
            string s = buff.ReadLine();
            while (s != null)
            {
                v.Add(s);//Add each element to the list
                s = buff.ReadLine();//Read next line
            }
        }catch(NullReferenceException ex){
            Console.WriteLine(ex);
        }
        //Cast each element of the list and put it in to the int array
        int[] dataSet=new int[v.Count];
        for(int j=0;j<v.Count;j++){
            dataSet[j]=Int32.Parse(v[j]);
        }
        return dataSet;//Return the int array
    }
    //Close File after the reading completed
    public void closeFile(){
        try
        {
            buff.Close();//Close the file
        }catch(NullReferenceException ex){
            Console.WriteLine(ex);
        }
    }
    }
}

ListNode.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Hashing
{
   class ListNode
    {
       public int value;//Data of the ListNode
       public ListNode next;//Reference to the next ListNode
       //Fill Data to each ListNode
       public ListNode(int num)
        {
            value = num;
        }
       //Display the content of the ListNode
       public void displayListNode(){
            Console.Write(value+" ");
       }
    }
}