Quadratic Probing And Linear Probing : Java Program Source Code

Quadratic Probing and Linear Probing are the techniques to avoid collision in the hash tables . Suppose the hash value generated  is already occupied in the hash table , then quadratic probing or linear probing helps to find a lace in the hash table .
linear probing

Quadratic Probing takes arbitrary quadratic polynomial and add it to the original hash index . The arbitrary quadratic polynomial is added till the hash value generated is not occupied in the hash table .

It works on the following formula

For a original hash index H , H+1*1 , H+2*2 ,H+3*3 ,H+4*4......


Read Also :   Hamming Distance : Nucleic Acid Bases String    


Linear Probing is somewhat easy  , it search sequentially in the hash table for a given hash value . It does not involve any arbitrary polynomial value .

Linear probing including two values one is starting value and other is interval value . If the hash value is occupied at starting point then the next hash value is calculated by adding the interval value to the starting value . If , it is also occupied in the hash table , then again we add interval value to the hash value generated .
Then again we keep looking for the hash value for which the hash table has no entry .

It works on the following formula

For a starting value H and interval value 1   :   H, H+1,H+2 , H+3,H+4.....

Pseudo code is given below :

Quadratic Probing algorithm  to insert key in the hash table

1. Retrieve key k
2. Compute hash function h[k] = k % size of the table
3. If hash table is empty at the computed hash value place
          then insert key at h[k]
    else
     we need to find another empty place in the hash table to insert the key in the hash table
        3.1    Use quadratic probing to compute the hash value of the key again   
        3.2    If   hash table place is empty then insert key at h[k] and exit
                 else
                 Repeat 3.1 step again   


Read Also :   Snakes And Ladder Game


Linear Probing algorithm to insert key in the hash table

1. Retrieve key k
2. Compute hash function h[k]= k %size of the table
3. If hash table is empty at the computed hash value place
          then insert key at h[k]
    else
        we need to find another empty place in the hash table to insert the key in the table
         3.1    Use linear probing to compute the hash value of the key again , in linear probing we generally 
                  keep adding some constant value to the computed hash value . 
         3.2    If hash table place is empty then insert key at  h[k] and exit
                  else 
                  Repeat  3.1 step again .


Read Also :   Langton's Ant : Java Program Code Explain

Demo :

quadratic probing and linear probing java program code output image

Code :

/**
* A class that implements the ADT dictionary by using hashing
* and linear probing to resolve collisions.
* The dictionary is not sorted and has distinct search keys.
* Notes: Uses probe for add, but locate for remove and getValue.
*        Uses linear probing, but includes code for quadratic probing.
*        Has a display method for illustration and testing.
*
* @author Sonia
* @version 2.0
*/
public class HashedDictionary<K, V>
{
    public TableEntry<K, V>[] hashTable;          // dictionary entries
    private int                numberOfEntries;
    private int                locationsUsed;          // number of table locations not null
    private static final int DEFAULT_SIZE = 101;      // must be prime
    private static final double MAX_LOAD_FACTOR = 0.5; // fraction of hash table that can be filled
    
    public HashedDictionary()
    {
        this(DEFAULT_SIZE); // call next constructor
        
    } // end default constructor
    
    public HashedDictionary(int tableSize)
    {
        // ensure that table is prime size at least as big as user wants;
        // if tableSize is prime, do not change it
        int primeSize = getNextPrime(tableSize);
        
        hashTable = new TableEntry[primeSize];
        numberOfEntries = 0;
        locationsUsed = 0;
    } // end constructor
    
    // -------------------------
    // We've added this method to display the hash table for illustration and testing
    // -------------------------
    public void display()
    {
        for (int index = 0; index < hashTable.length; index++)
        {
            if (hashTable[index] == null)
            System.out.println("null ");
            else if (hashTable[index].isRemoved())
            System.out.println("notIn ");
            else
            System.out.println(hashTable[index].getKey() + " " + hashTable[index].getValue());
        } // end for
        System.out.println();
    } // end display
    // -------------------------
    
    // 20.14
    public V add(K key, V value)
    {
        V oldValue;
        if (isHashTableTooFull())
        rehash();
        int index = getHashIndex(key);
        index = quadraticProbe(index, key);
        assert (index >= 0) && (index < hashTable.length);
        if ( (hashTable[index] == null) || hashTable[index].isRemoved())
        { // key not found, so insert new entry
            hashTable[index] = new TableEntry<K, V>(key, value);
            numberOfEntries++;
            locationsUsed++;
            oldValue = null;
        }
        else
        { // key found; get old value for return and then replace it
            oldValue = hashTable[index].getValue();
            hashTable[index].setValue(value);
        } // end if
        
        return oldValue;
    } // end add
    
    
    // 20.12
    public V remove(K key)
    {
        V removedValue = null;
        
        int index = getHashIndex(key);
        index = locate(index, key);
        
        if (index != -1)
        {
            // key found; flag entry as removed and return its value
            removedValue = hashTable[index].getValue();
            hashTable[index].setToRemoved();
            numberOfEntries--;
        } // end if
        // else not found; result is null
        
        return removedValue;
    } // end remove
    
    // 20.11
    public V getValue(K key)
    {
        V result = null;
        
        int index = getHashIndex(key);
        index = locate(index, key);
        
        if (index != -1)
        result = hashTable[index].getValue(); // key found; get value
        
        // else not found; result is null
        
        return result;
    } // end getValue
    
    // 20.15
    private int quadraticProbe(int index, K key)
    {
        boolean found = false;
        int removedStateIndex = -1; // index of first location in
        // removed state
        int i=0;
        while ( !found && (hashTable[index] != null) && i< hashTable.length)
        {
            if (hashTable[index].isIn())
            {
                if (key.equals(hashTable[index].getKey()))
                found = true; // key found
                else // follow probe sequence
                {
                    index = (index + i*i) % hashTable.length;         // linear probing
                    i++;
                }
            }
            else // skip entries that were removed
            {
                // save index of first location in removed state
                if (removedStateIndex == -1)
                removedStateIndex = index;
                
                index = (index + i*i) % hashTable.length;         // linear probing
                i++ ;
            } // end if
        } // end while
        // Assertion: either key or null is found at hashTable[index]
        
        if (found || (removedStateIndex == -1) )
        return index;             // index of either key or null
        else
        return removedStateIndex; // index of an available location
    } // end probe
    
    // 20.13
    public int locate(int index, K key)
    {
        boolean found = false;
        int i=0;
        while ( !found && (hashTable[index] != null) && i<hashTable.length)
        {
            if ( hashTable[index].isIn() && key.equals(hashTable[index].getKey()) )
            found = true; // key found
            else // follow probe sequence
            {
                index = (index + i*i) % hashTable.length;         // linear probing
                i++;
            }
        } // end while
        // Assertion: either key or null is found at hashTable[index]
        
        int result = -1;
        if (found)
        result = index;
        
        return result;
    } // end locate
    
    public boolean contains(K key)
    {
        return getValue(key) != null;
    } // end contains
    
    
    public boolean isEmpty()
    {
        return numberOfEntries == 0;
    } // end isEmpty
    
    
    public boolean isFull()
    {
        return false;
    } // end isFull
    
    
    public int getSize()
    {
        return numberOfEntries;
    } // end getSize
    
    
    public final void clear()
    {
        for (int index = 0; index < hashTable.length; index++)
        hashTable[index] = null;
        
        numberOfEntries = 0;
        locationsUsed = 0;
    } // end clear
    
    public int getHashIndex(K key)
    {
        
        int hashIndex = key.hashCode() % hashTable.length;
        
        if (hashIndex < 0)
        {
            hashIndex = hashIndex + hashTable.length;
        } // end if
        
        return hashIndex;
    } // end getHashIndex
    
    /** Task: Increases the size of the hash table to a prime > twice its old size. */
    private void rehash()
    {
        TableEntry<K, V>[] oldTable = hashTable;
        int oldSize = hashTable.length;
        int newSize = getNextPrime(oldSize + oldSize);
        hashTable = new TableEntry[newSize]; // increase size of array
        numberOfEntries = 0; // reset number of dictionary entries, since
        // it will be incremented by add during rehash
        locationsUsed = 0;
        
        // rehash dictionary entries from old array to the new and bigger
        // array; skip both null locations and removed entries
        for (int index = 0; index < oldSize; index++)
        {
            if ( (oldTable[index] != null) && oldTable[index].isIn() )
            add(oldTable[index].getKey(), oldTable[index].getValue());
        } // end for
    } // end rehash
    
    /** @return true if lambda > MAX_LOAD_FACTOR for hash table;
    *       otherwise returns false. */
    private boolean isHashTableTooFull()
    {
        return locationsUsed > MAX_LOAD_FACTOR * hashTable.length;
    } // end isHashTableTooFull
    
    private int getNextPrime(int integer)
    {
        // if even, add 1 to make odd
        if (integer % 2 == 0)
        {
            integer++;
        } // end if
        
        // test odd integers
        while(!isPrime(integer))
        {
            integer = integer + 2;
        } // end while
        
        return integer;
    } // end getNextPrime
    
    private boolean isPrime(int integer)
    {
        boolean result;
        boolean done = false;
        
        // 1 and even numbers are not prime
        if ( (integer == 1) || (integer % 2 == 0) )
        {
            result = false;
        }
        
        // 2 and 3 are prime
        else if ( (integer == 2) || (integer == 3) )
        {
            result = true;
        }
        
        else // integer is odd and >= 5
        {
            assert (integer % 2 != 0) && (integer >= 5);
            
            // a prime is odd and not divisible by every odd integer up to its square root
            result = true; // assume prime
            for (int divisor = 3; !done && (divisor * divisor <= integer); divisor = divisor + 2)
            {
                if (integer % divisor == 0)
                {
                    result = false; // divisible; not prime
                    done = true;
                } // end if
            } // end for
        } // end if
        
        return result;
    } // end isPrime
    
    
    // 20.09
    class TableEntry<S, T>
    {
        private S key;
        private T value;
        private boolean inTable; // true if entry is in table
        
        private TableEntry(S searchKey, T dataValue)
        {
            key = searchKey;
            value = dataValue;
            inTable = true;
        } // end constructor
        
        public S getKey()
        {
            return key;
        } // end getKey
        
        private T getValue()
        {
            return value;
        } // end getValue
        
        private void setValue(T newValue)
        {
            value = newValue;
        } // end setValue
        
        private boolean isIn()
        {
            return inTable;
        } // end isIn
        
        private boolean isRemoved() // opposite of isIn
        {
            return !inTable;
        } // end isRemoved
        
        // state = true means entry in use; false means entry not in use, ie deleted
        private void setToRemoved()
        {
            key = null;
            value = null;
            inTable = false;
        } // end setToRemoved
        
        private void setToIn() // not used
        {
            inTable = true;
        } // end setToIn
    } // end TableEntry
} // end HashedDictionary




HashedDictionaryTest.java



import java.io.*;
import java.util.*;
public class HashedDictionaryTest
{
    String method;
    String key;
    String value;
    public HashedDictionaryTest(String method, String key, String value){
        this.method = method;
        this.key = key;
        this.value = value;
    }
    public static void main(String[] args)
    {
        // declaring nameList as HashedDictionary instead of DictionaryInterface enables display method in HashedDictionary
        HashedDictionary<Name, String> nameList = new HashedDictionary<Name, String>(11);
        String line[]= new String[100];
        String subline[]=new String[100];
        String[] tokens=new String[100];
        String subtoken[] =new String[100];
        int i=0,j=0,k=0;
        try{
            Scanner scanner = new Scanner(new File("userfile.txt")).useDelimiter(" ");
            while (scanner.hasNext()) {
                line[i] = scanner.nextLine();
                Scanner scanner1 = new Scanner(line[i]).useDelimiter(" ");
                while (scanner1.hasNext()) {
                    subline[j] = scanner1.nextLine();
                    j++;
                }  i++;
            }
            String strLine;
            while ((strLine = subline[k]) != null)   {
                tokens = strLine.split(" ");
                for(int m=0; m<tokens.length;m++){
                    subtoken[m]=tokens[m];
                }
                if(tokens.length==1)
                {
                    subtoken[1]=null;
                    subtoken[2]=null;
                }
                else if (tokens.length==2)
                subtoken[2]=null;
                HashedDictionaryTest record = new HashedDictionaryTest(subtoken[0],subtoken[1],subtoken[2]);//process record , etc
                chooseMethod(subtoken[0],subtoken[1],subtoken[2],nameList);
                k++;
            }
        }
        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    
    
    public static void chooseMethod(String s , String s1 , String s2 ,HashedDictionary<Name, String> nameList )
    {
        if (s.equals("add"))
        nameList.add(new Name(s1),s2);
        else if (s.equals("print"))
        nameList.display();
        else if(s.equals("locate"))
        nameList.locate( nameList.getHashIndex(new Name(s1)),new Name(s1));
        else if (s.equals("remove"))
        {
            int   index =nameList.getHashIndex(new Name(s1));
            index=nameList.hashTable.length-index;
            Name m= (Name)nameList.hashTable[index-1].getKey();
            nameList.remove(m);
        }
    }
}

// end HashedDictionaryTest




Name.java



/** This class is like the one in the folder Comparable,
*  but adds a constructor and hashCode for testing purposes. */
public class Name
{
    private String first; // first name
    private String last;  // last name
    
    public Name()
    {
        this("","");
    } // end default constructor
    
    public Name(String firstName) // for testing ***************
    {
        this(firstName, "");
    } // end constructor
    
    public Name(String firstName, String lastName)
    {
        first = firstName;
        last = lastName;
    } // end constructor
    
    @Override
    public int hashCode() // for testing ***************
    {
        // this hash code causes collisions
        int h = 0;
        
        for (int i = 0; i < first.length(); i++)
        {
            h = h + first.charAt(i);
        }
        return h;
        //  a reasonable hash code follows:
        //  return first.hashCode() + last.hashCode();
    } // end hashCode
    
    public void setName(String firstName, String lastName)
    {
        setFirst(firstName);
        setLast(lastName);
    } // end setName
    
    public String getName()
    {
        return toString();
    } // end getName
    
    public void setFirst(String firstName)
    {
        first = firstName;
    } // end setFirst
    
    public String getFirst()
    {
        return first;
    } // end getFirst
    
    public void setLast(String lastName)
    {
        last = lastName;
    } // end setLast
    
    public String getLast()
    {
        return last;
    } // end getLast
    
    public void giveLastNameTo(Name aName)
    {
        aName.setLast(last);
    } // end giveLastNameTo
    
    @Override
    public String toString()
    {
        return first + " " + last;
    } // end toString
    
    
    @Override
    public boolean equals(Object other)
    {
        boolean result;
        
        if ((other == null) || (getClass() != other.getClass()))
        result = false;
        else
        {
            Name otherName = (Name)other;
            result = first.equals(otherName.first) &&
            last.equals(otherName.last);
        } // end if
        
        return result;
    } // end equals
    
} // end Name




userFile.txt


add 555-1234 Tabatha
add 555-1235 Toni
print
locate Toni
remove Tabatha
add 555-1236 Tobbie
print
locate Tabatha

Share this

Related Posts

Previous
Next Post »