Artificial Intelligent - [Assignment-2013]

♠ Posted by Unknown in , at 08:17

Que:2 What is Open Addressing? Write a Java code for Linear probing with explanation.

The goal of hash functions is to minimize collisions, collisions are normally unavoidable in practice. Thus, hashing implementations must include some form of collision resolution policy. Collision resolution techniques can be broken into two classes: Separate Chaining and Open addressing. The difference between the two has to do with whether collisions are stored outside the table, or whether collision result in storing one of the records at another slot in the table respectively.

Open addressing stores all records directly in the hash table. Each record R with key value KR has a home position that is h(KR), the slot computed by the hash function. If R is to be inserted and another record already occupies R’s home position, then R will be stored at some other slot in the table.

There are three methods of open addressing, which vary in the method used to find the next vacant cell. These methods are  linear probing, quadratic probing, and double hashing.

Linear Probing:

In linear probing we search sequentially for vacant cells. if 2421 is occupied when we try to insert a data item there, we go to 2422, then 2423, and so on, increment the index until we find an empty cell. This is called linear probing because it steps sequentially along the line of cells.

/*Author: Viral Vyas
 * Linear Probing...
 */

package aiassignment2013;
import java.io.*;
import java.lang.*;

class LBDataItem
{
    private int iData; // data item (key)
   
    public LBDataItem(int ii) // constructor
    { iData = ii; }   
    public int getKey()
    { return iData; }
}

class LBMethods
{
    private LBDataItem[] hashArray; // array holds hash table
    private int arraySize;
    private LBDataItem nonItem; // for deleted items

    public LBMethods(int size) // constructor
    {
        arraySize = size;
        hashArray = new LBDataItem[arraySize];
        nonItem = new LBDataItem(-1); // deleted item key is -1
    }

    public void displayTable()
    {
        System.out.print("Table: ");
        for(int j=0; j<arraySize; j++)
        {
            if(hashArray[j] != null)
                System.out.print(hashArray[j].getKey() + " ");
            else
                System.out.print("** ");
        }
        System.out.println("");
    }

    public int hashFunc(int key)
    {
        return key % arraySize; // hash function
    }

    public void insert(LBDataItem item) // insert a LBDataItem
    {
        int key = item.getKey(); // extract key
        int hashVal = hashFunc(key); // hash the key
       
        // until empty cell or -1,
        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)
        {
            ++hashVal; // go to next cell
             hashVal %= arraySize; // wraparound if necessary
        }
        hashArray[hashVal] = item; // insert item
    }

    public LBDataItem delete(int key) // delete a LBDataItem
    {
        int hashVal = hashFunc(key); // hash the key
        while(hashArray[hashVal] != null) // until empty cell,
        { // found the key?
            if(hashArray[hashVal].getKey() == key)
            {
                LBDataItem temp = hashArray[hashVal]; // save item
                hashArray[hashVal] = nonItem; // delete item
                return temp; // return item
            }
            ++hashVal; // go to next cell
            hashVal %= arraySize; // wraparound if necessary
        }
        return null; // can’t find item
    }

    public LBDataItem find(int key) // find item with key
    {
        int hashVal = hashFunc(key); // hash the key
       
        while(hashArray[hashVal] != null) // until empty cell,
        { // found the key?
            if(hashArray[hashVal].getKey() == key)
                return hashArray[hashVal]; // yes, return item
           
            ++hashVal; // go to next cell
            hashVal %= arraySize; // wraparound if necessary
        }
        return null; // can’t find item
    }
}

class LBMain
{
   
    public static String getString() throws IOException
    {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }

    public static char getChar() throws IOException
    {
        String s = getString();
        return s.charAt(0);
    }

    public static int getInt() throws IOException
    {
        String s = getString();
        return Integer.parseInt(s);
    }
   
    public static void main(String[] args) throws IOException
    {
        LBDataItem aDataItem;
        int aKey, size, n, keysPerCell;

        // get sizes
        System.out.print("Enter size of hash table: ");
        size = getInt();
        System.out.print("Enter initial number of items: ");
        n = getInt();
       
        keysPerCell = 10;

        // make table
        LBMethods theHashTable = new LBMethods(size);
        for(int j=0; j<n; j++) // insert data
        {
            aKey = (int)(java.lang.Math.random() * keysPerCell * size);
            aDataItem = new LBDataItem(aKey);
            theHashTable.insert(aDataItem);
        }

        while(true) // interact with user
        {
            System.out.print("Enter first letter of ");
            System.out.print("show, insert, delete, or find: ");
            char choice = getChar();
            switch(choice)
            {
                case 's':
                    theHashTable.displayTable();
                    break;
                case 'i':
                    System.out.print("Enter key value to insert: ");
                    aKey = getInt();
                    aDataItem = new LBDataItem(aKey);
                    theHashTable.insert(aDataItem);
                    break;
                case 'd':
                    System.out.print("Enter key value to delete: ");
                    aKey = getInt();
                    theHashTable.delete(aKey);
                    break;
                case 'f':
                    System.out.print("Enter key value to find: ");
                    aKey = getInt();
                    aDataItem = theHashTable.find(aKey);
                    if(aDataItem != null)
                    {
                        System.out.println("Found " + aKey);
                    }
                    else
                        System.out.println("Could not find " + aKey);
                    break;
                default:
                    System.out.print("Invalid entry\n");
            } // end switch
        } // end while
    } // end main()  
}

Output:

Enter size of hash table: 12
Enter initial number of items: 8
Enter first letter of show, insert, delete, or find: s
Table: 108 13 0 ** ** 113 5 66 ** 117 ** 47
Enter first letter of show, insert, delete, or find: f
Enter key value to find: 66
Found 66
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 100
Enter first letter of show, insert, delete, or find: s
Table: 108 13 0 ** 100 113 5 66 ** 117 ** 47
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 100
Enter first letter of show, insert, delete, or find: s
Table: 108 13 0 ** -1 113 5 66 ** 117 ** 47

Explanation:

The main() method in the LBMain class contains a user interface that allows the user to show the contents of the hash table (enter s), insert an item (i), delete an item (d), or find an item (f).

Intially, the program asks the user to input the size of the hash table and the number of items in it. A variable in main(), keysPerCell, specifies the ratio of the range of keys to the size of the array. In the listing, it’s set to 10. This means that if you specify a table size of 20, the keys will range from 0 to 200.
Key values run from 0 to 119 (12 times 10, minus 1). the ** symbol indicates that a cell is empty. The item with key 100 is inserted at location 4 (the first item is numbered 0) because 100%12 is 4. Notice how 100 changes to -1 when this item is deleted.

1 comments:

Nice iformation for me. onlineassignmentwriter.com surfaces for your help. We provide you with quality biotechnology assignment help that will take your work to another level. We know that you have enrolled in this course because you want to do something extraordinary in life. However due to lack of time, you may not be able to handle all your work. So, let us assist you with our expertise in this line of work.

Post a Comment