Implement a hash table using 3 different collection handling techniques: linear probing, quadratic probing and chaining.

hash.java

/**
 * Author:      Douglas Hall
 * Course:      CSC345
 * Assignment:  Homework #7
 * Instructor:  Steven Kobourov
 * Due Date:    2009-11-16 23:59
 * 
 * Purpose:     Implement a hash table using 3 different collection handling techniques.
 *              Linear probing, quadratic probing and chaining.
 */

import java.util.Random;
import java.util.Stack;
import java.lang.Math;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class hash {
    public static Integer table[] = new Integer[8];
    public static Integer valueCount = 0;
    public static boolean resizing = false;
    
    /**
     * Name:    main
     * Desc:    Opens hash_input.txt, reads each line and performs the operation specified
     *          in the line read. Then outputs any data to hash_output.txt
     */
    public static void main(String[] args) {
        //Instantiate all 3 of the hash table classes
        LinearHash linearHash = new LinearHash();
        QuadraticHash quadraticHash = new QuadraticHash();
        ChainingHash chainingHash = new ChainingHash();

        try {
            //Setup the input and output files
            FileReader iFile = new FileReader("hash_input.txt");
            BufferedReader in = new BufferedReader(iFile);
            FileWriter oFile = new FileWriter("hash_output.txt");
            BufferedWriter out = new BufferedWriter(oFile);
            
            //For each line in the file
            while(in.ready()) {
                //Split the line so that we can extract it's operation and operand(s)
                String[] currentInput = in.readLine().split("\\s");
                String command = currentInput[0];
                
                //Perform commands based off of operation specified
                if(command.equals("INS")) {
                    //Insert value into each hash table
                    linearHash.insert(Integer.parseInt(currentInput[1]));
                    quadraticHash.insert(Integer.parseInt(currentInput[1]));
                    chainingHash.insert(Integer.parseInt(currentInput[1]));
                }
                if(command.equals("DEL")) {
                    //Delete value from each hash table
                    linearHash.delete(Integer.parseInt(currentInput[1]));
                    quadraticHash.delete(Integer.parseInt(currentInput[1]));
                    chainingHash.delete(Integer.parseInt(currentInput[1]));
                }
                if(command.equals("PRT")) {
                    //Print values in each hash table and write them to the file
                    out.write(linearHash.print());
                    out.write(quadraticHash.print());
                    out.write(chainingHash.print());
                }
            }
            
            out.close();
            in.close();
        } catch (FileNotFoundException e) {
            //Couldn't find the input file
            e.printStackTrace();
        } catch (IOException e) {
            //Couldn't write to the output file
            e.printStackTrace();
        }
    }
    
    /**
     * Name:    LinearHash
     * Desc:    Implements insert, delete and print for a hash table that uses linear probing.
     */
    public static class LinearHash {
        //The table to store data
        private Integer table[] = new Integer[8];
        //The number of values in the table
        private Integer valueCount = 0;
        //Whether or not we're resizing
        private boolean resizing = false;
        //Number of traversals
        public Integer traversals = 0;
        
        /**
         * Name:    hashFunction
         * Desc:    Calculate the hash of the given value.
         */
        private Integer hashFunction(Integer value) {
            return (2 * value + 5) % table.length;
        }
        
        /**
         * Name:    loadFactor
         * Desc:    Return the load factor of the hash table.
         */
        private Float loadFactor() {
            return (float) valueCount / table.length;
        }
        
        /**
         * Name:    probe
         * Desc:    Given a value and whether or not we're looking for an empty space or a value
         *          this function will return the index cooresponding to the desired value using
         *          linear probing.
         */
        private Integer probe(Integer value, Boolean deleting) {
            //Calculate the hash
            Integer hash = hashFunction(value);
            //If we're deleting then we're looking for the table entry value exists in
            //Else we're looking for an empty space
            if(deleting) {
                //While we haven't found what we're looking for
                while(table[hash] != value) {
                    traversals++;
                    hash = (hash + 1) % table.length;
                }
            } else {
                //While we haven't found what we're looking for
                while(table[hash] != null) {
                    traversals++;
                    hash = (hash + 1) % table.length;
                }
            }
            return hash;
        }
        
        /**
         * Name:    resize
         * Desc:    Shrinks the table if the load factor drops below 0.25 and is greater than 8 elements.
         *          Grows the table if the load factor is greater than 0.5.
         */
        private void resize() {
            //Make sure our inserts don't recursively call this function
            resizing = true;
            //Make a temporary table
            Integer tempTable[] = table;
            //If the load factor is greater than 0.5, we need to enlarge
            if(loadFactor() >= 0.5) {
                //Make a new table with double the original elements
                table = new Integer[tempTable.length * 2];
                //Reinsert all the values from the previous table into this one
                //effectively rehashing all existing values
                for(Integer i = 0; i < tempTable.length; i++) {
                    if(tempTable[i] != null) {
                        insert(tempTable[i]);
                    }
                }
                //If the load factor is 0.25 and greater than 8 elements, we need to shrink
            } else if(loadFactor() <= 0.25 && tempTable.length > 8) {
                //Make a new table with half as many elements
                table = new Integer[tempTable.length / 2];
                //For each element in the previous table reinert them
                //effectively rehashing the table
                for(Integer i = 0; i < tempTable.length; i++) {
                    if(tempTable[i] != null) {
                        insert(tempTable[i]);
                    }
                }
            }
            //Let the rest of the functions know we're not resizing anymore
            resizing = false;
        }

        /**
         * Name:    insert
         * Desc:    Given an integer value calculate it's hash and insert it into the table
         *          at the appropriate location.
         */
        public void insert(Integer value) {
            //Probe the table for a place to stick the element
            Integer hash = probe(value, false);
            //Insert the value at the location found
            table[hash] = value;
            //Provided we haven't been called by the resize function
            if(!resizing) {
                //Increment the number of values for loadFactor calculation
                valueCount++;
                //Attempt to resize the table
                resize();
            }
        }
        
        /**
         * Name:    delete
         * Desc:    Given an Integer value find the value in the table and remove it,
         *          shrink if necessary.
         */
        public void delete(Integer value) {
            //Probe for the value
            Integer hash = probe(value, true);
            //Delete the value from the table
            table[hash] = null;
            //Provided we haven't been called by the resize function
            if(!resizing) {
                //Decrement the value counter
                valueCount--;
                //Attempt to resize
                resize();
            }
        }
        
        /**
         * Name:    print
         * Desc:    Print the contents of the table in order of keys
         *          to a string and return the string
         */
        public String print() {
            String result = "";
            for(Integer i = 0; i < table.length; i++) {
                if(table[i] != null) {
                    result += table[i] + " ";
                }
            }
            return result + "\n";
        }
    }

    /**
     * Name:    QuadraticHash
     * Desc:    Implements insert, delete and print for a hash table that uses quadratic probing.
     */
    public static class QuadraticHash {
        //The table to store data
        private Integer table[] = new Integer[8];
        //The number of values in the table
        private Integer valueCount = 0;
        //Whether or not we're resizing
        private boolean resizing = false;
        //Number of traversals
        public Integer traversals = 0;
        
        /**
         * Name:    hashFunction
         * Desc:    Calculate the hash of the given value.
         */
        private Integer hashFunction(Integer value) {
            return (2 * value + 5) % table.length;
        }
        
        /**
         * Name:    loadFactor
         * Desc:    Return the load factor of the hash table.
         */
        private Float loadFactor() {
            return (float) valueCount / table.length;
        }
        
        /**
         * Name:    probe
         * Desc:    Given a value and whether or not we're looking for an empty space or a value
         *          this function will return the index cooresponding to the desired value using
         *          quadratic probing.
         */
        private Integer probe(Integer value, Boolean deleting) {
            //Calculate the hash
            Integer hash = hashFunction(value);
            //Set the index = 0 for the quadratic traversal
            Integer index = 0;
            //If we're deleting then we're looking for the table entry the value exists in
            //else we're looking for an empty space
            if(deleting) {
                //While we haven't found the value we're looking for
                while(table[hash] != value) {
                    traversals++;
                    //Calculate the next key to check using quadratic probing c1 = 1/2 and c2 = 1/2
                    //h(k, i) = (h(k) + i/2 + i^2 / 2) % (length of table)
                    hash = (int) ((hash + (float)index / 2 + (float)(index * index) / 2) % table.length);
                    //increment index
                    index++;
                }
            } else {
                //Same thing as above just looking for an empty space instead of the value
                while(table[hash] != null) {
                    traversals++;
                    hash = (int) ((hash + (float)index / 2 + (float)(index * index) / 2) % table.length);
                    index++;
                }
            }
            return hash;
        }
        
        /**
         * Name:    resize
         * Desc:    Shrinks the table if the load factor drops below 0.25 and is greater than 8 elements.
         *          Grows the table if the load factor is greater than 0.5.
         */
        private void resize() {
            resizing = true;
            Integer tempTable[] = table;
            if(loadFactor() >= 0.5) {
                table = new Integer[tempTable.length * 2];
                for(Integer i = 0; i < tempTable.length; i++) {
                    if(tempTable[i] != null) {
                        insert(tempTable[i]);
                    }
                }
            } else if(loadFactor() <= 0.25 && tempTable.length > 8) {
                table = new Integer[tempTable.length / 2];
                for(Integer i = 0; i < tempTable.length; i++) {
                    if(tempTable[i] != null) {
                        insert(tempTable[i]);
                    }
                }
            }
            resizing = false;
        }

        /**
         * Name:    insert
         * Desc:    Given an integer value calculate it's hash and insert it into the table
         *          at the appropriate location.
         */
        public void insert(Integer value) {
            Integer hash = probe(value, false);
            table[hash] = value;
            if(!resizing) {
                valueCount++;
                resize();
            }
        }
        
        /**
         * Name:    delete
         * Desc:    Given an Integer value find the value in the table and remove it,
         *          shrink if necessary.
         */
        public void delete(Integer value) {
            Integer hash = probe(value, true);
            table[hash] = null;
            if(!resizing) {
                valueCount--;
                resize();
            }
        }
        
        /**
         * Name:    print
         * Desc:    Print the contents of the table in order of keys
         *          to a string and return the string
         */
        public String print() {
            String result = "";
            for(Integer i = 0; i < table.length; i++) {
                if(table[i] != null) {
                    result += table[i] + " ";
                }
            }
            return result + "\n";
        }
    }
    
    /**
     * Name:    ChainingHash
     * Desc:    Implements insert, delete and print for a hash table that uses chaining.
     */
    public static class ChainingHash {
        private ChainNode table[] = new ChainNode[8];
        private Integer valueCount = 0;
        private boolean resizing = false;
        public Integer traversals = 0;
        
        /**
         * Name:    hashFunction
         * Desc:    Calculate the hash of the given value.
         */
        private Integer hashFunction(Integer value) {
            return (2 * value + 5) % table.length;
        }
        
        /**
         * Name:    loadFactor
         * Desc:    Return the load factor of the hash table.
         */
        private Float loadFactor() {
            return (float) valueCount / table.length;
        }

        /**
         * Name:    resize
         * Desc:    Shrinks the table if the load factor drops below 0.25 and is greater than 8 elements.
         *          Grows the table if the load factor is greater than 0.5.
         */
        private void resize() {
            resizing = true;
            //Make a new temporary table
            ChainNode tempTable[] = table;
            //Grow if load factor >= 0.5, else shrink if load factor < 0.25 and has greater than 8 elements
            if(loadFactor() >= 0.5) {
                //Make new table
                table = new ChainNode[tempTable.length * 2];
                //For each element in the temporary table find the position to insert
                //the element into the new table
                for(Integer i = 0; i < tempTable.length; i++) {
                    //Start at the beginning of the list at the current index
                    ChainNode currentNode = tempTable[i];
                    //While we haven't reached the end of the list
                    while(currentNode != null) {
                        //Insert element
                        insert(currentNode.data);
                        //Go to next element
                        currentNode = currentNode.next;
                    }
                }
            } else if(loadFactor() <= 0.25 && tempTable.length > 8) {
                //Shrink table
                table = new ChainNode[tempTable.length / 2];
                //For each element in the temporary table
                for(Integer i = 0; i < tempTable.length; i++) {
                    //Start at the beginning of the list at this index
                    ChainNode currentNode = tempTable[i];
                    //While we haven't reached the end of the list
                    while(currentNode != null) {
                        //Insert the data
                        insert(currentNode.data);
                        //Go to next node
                        currentNode = currentNode.next;
                    }
                }
            }
            //Let the rest of the functions know we're not resizing anymore
            resizing = false;
        }

        /**
         * Name:    insert
         * Desc:    Given an integer value calculate it's hash and insert it into the table
         *          at the appropriate location. Resize if necessary.
         */
        public void insert(Integer value) {
            //Calculate the hash of the value
            Integer hash = hashFunction(value);
            //If the index of the table there is null then insert it
            if(table[hash] == null) {
                table[hash] = new ChainNode(value);
            } else {
                //The index isn't empty so we need to insert the value
                //at the end of the list
                ChainNode currentNode = table[hash];
                while(currentNode.next != null) {
                    traversals++;
                    currentNode = currentNode.next;
                }
                currentNode.next = new ChainNode(value);
            }
            //If we weren't called while resizing
            if(!resizing) {
                //Increment value counter
                valueCount++;
                //Attempt to resize
                resize();
            }
        }
        
        /**
         * Name:    delete
         * Desc:    Given an Integer value find the value in the table and remove it.
         *          Resize if necessary.
         */
        public void delete(Integer value) {
            //Calculate the hash of the value
            Integer hash = hashFunction(value);
            //If the first element of the list is the value we're looking for
            if(table[hash].data.equals(value)) {
                //Splice the node out
                table[hash] = table[hash].next;
            } else {
                //We need to find the value in the list
                ChainNode currentNode = table[hash];
                while(currentNode.next.data != value) {
                    traversals++;
                    //Traverse the list
                    currentNode = currentNode.next;
                }
                //Splice the value out
                currentNode.next = currentNode.next.next;
            }
            //If we weren't called while resizing
            if(!resizing) {
                //Decrement value counter
                valueCount--;
                //Attempt to resize
                resize();
            }
        }
        
        /**
         * Name:    print
         * Desc:    Print the contents of the table in order of keys
         *          to a string and return the string
         */
        public String print() {
            String result = "";
            for(Integer i = 0; i < table.length; i++) {
                if(table[i] != null) {
                    ChainNode currentNode = table[i];
                    while(currentNode != null) {
                        result += currentNode.data + " ";
                        currentNode = currentNode.next;
                    }
                }
            }
            return result + "\n";
        }
        
        /**
         * Name:    ChainNode
         * Desc:    Basic structure of the linked lists used for storing multiple
         *          values at a single table index.
         */
        private static class ChainNode {
            public ChainNode next = null;
            public Integer data = null;
            
            public ChainNode(Integer value) {
                data = value;
            }
        }
    }
}