Subversion Repositories programming

//import chap09.list03.Map;

import java.io.*;

import java.util.*;

public class HashTable implements Map {  // open addressing

    private Entry[] entries; 

    //size is the total number of elements, including NIL

    //used is the total number of elements, NOT INCLUDING NIL

    private int size, used;

    private float loadFactor;

    private final Entry NIL = new Entry(null,null);  // dummy

    private int probeType; //holds the type of probing to use    

    //variable to hold total number of collisions this run.

    //Definition: collision - the number of times we must jump to

    //                        get to the next null space in the table

    //                        This includes jumping NIL's

    //

    //NOTE: will only be counted on inserting values

    private int collisions; //initialized to 0 by default

    //create a HashTable with a certain capacity (maximum items)

    //and a maximum load factor (if we exceed this we will rehash)

    public HashTable(int capacity, float loadFactor) {

        entries = new Entry[capacity];

        this.loadFactor = loadFactor; }

    //create a HashTable with a certain capacity (maximum items)

    //and a default load factor of 0.75

    public HashTable(int capacity) {

        this(capacity,0.75F);} //calls the HashTable( int, float ) constructor

    //create a default HashTable with default capacity (101 items) and

    //default load factor of 0.75

    public HashTable() {

        this(101); } //calls the HashTable( int ) constructor

    //Method to find a certain key in the HashTable

    //Precondition: key != null

    //Postcondition: return the entry's value if the key is found

    //               otherwise return null for not found

    public Object get(Object key) {

        int h=hash(key);

        for (int i=0; i<entries.length; i++) {

            int j = nextProbe(h,i);

            Entry entry=entries[j];

            if (entry==null) break;

            if (entry==NIL) continue;

            if (entry.key.equals(key)) return entry.value;  // success

        }

        return null;  // failure: key not found

    }

    //Method to add a key/value pair to the HashTable

    //Key - the value that gets hash() called on it. Should be unique (hopefully)

    //Value - the actual data that is to be stored.

    //Precondition: key != null

    //Postcondition: return null if the object was inserted sucessfully

    //               return the value that was there if we updated a value

    //               return null if the table overflows (should never happen,

    //               but it is there just in case)

    public Object put(Object key, Object value) {

        if (used>loadFactor*entries.length) rehash();

        int h=hash(key); //hash the key

        for (int i=0; i<entries.length; i++) { //run once for each place in the Table

            int j = nextProbe(h,i); //get the [first, next] place to try putting the value

            Entry entry=entries[j]; //get the Entry at j (where we want to put value)

	    //if entry[j] == null then we have found a good place to put value!

	    if (entry==null) {

                entries[j] = new Entry(key,value);

                ++size;

                ++used;

                return null;  // insertion success

            }

	    //if entry[j] == NIL then we must continue to probe for a new place,

	    //otherwise we will confuse the remove() and get() methods

            if (entry==NIL) { collisions++; continue; }

	    //if entry[j].key == key then we need to update the record

            if (entry.key.equals(key)) {

                Object oldValue=entry.value;

                entries[j].value = value;

                return oldValue;  // update success

            }

	    //if we get here, we have had a collision that is not a NIL,

	    //and is not an Entry that needs updating, therefore it is something

	    //else that hashes to the same value.  Therefore we must increment the

	    //collision counter

	    collisions++;

	}

        return null;  // failure: table overflow

    }

    //Method to remove a key/value pair from the table.  This will leave a NIL behind

    //Precondition: key != null

    //Postcondition: return the old value if the key was found, then put a NIL in it's place

    //               return null if the key was not found in the table.

    public Object remove(Object key) {

        int h=hash(key); //hash the key

        for (int i=0; i<entries.length; i++) { //run once for every place in the table

            int j = nextProbe(h,i); //find the [first, next] place to put the value

            Entry entry=entries[j];

            if (entry==null) break; //break out of the loop, since the key was not found

            if (entry==NIL) continue; //keep going, since we found a NIL

            if (entry.key.equals(key)) { //we found the key we are looking for...

                Object oldValue=entry.value; //save value to return

                entries[j] = NIL; //replace the value with a NIL

                --size; //decrement size

                return oldValue;  // success

            }

        }

        return null;  // failure: key not found

    }

    //Method to access private variable size

    //Precondition: none

    //Postcondition: return size

    public int size() {

        return size;

    }

    //Method to access private variable collisions

    //Precondition: none

    //Postcondition: return collisions

    public int collisions() {

    	return collisions;

    }

    //Method to set the probeType variable

    //

    //0 == Linear Probing (step size 1) DEFAULT

    //1 == Prime  Probing (step size 3)

    //2 == Prime  Probing (step size 5)

    //3 == Prime  Probing (step size 7)

    //4 == Prime  Probing (step size 11)

    //5 == Quadratic Probing

    //6 == Double Hashing

    //

    //Precondition: 0 <= newValue <= 6

    //Postcondition: probeType will be changed

    //WARNING: Please do NOT change probeType while in a test run

    public void setProbeType( int newValue ) {

    	if( newValue < 0 || newValue > 6 ) { newValue = 0; } //put in for safety, just in case

	probeType = newValue;

    }

    //A private class which will hold a key/value pair

    private class Entry {

        Object key, value;

        Entry(Object k, Object v) { key=k; value=v; }

    }

    //our implementation of the hash() function. Takes the Object.hashCode() method

    //and chops off the sign bit

    //Precondition: None (we check for key == null)

    //Postcondition: throw an IllegalArgumentException() if the key == null

    //               return an integer hash for the given key

    private int hash(Object key) {

        if (key==null) throw new IllegalArgumentException();

        return (key.hashCode() & 0x7FFFFFFF) % entries.length;

    }

    //Method to implement linear probing

    //Precondition: h != null; i != null

    //Postcondition: return the next place to try and put the value

    private int nextProbe(int h, int i) {

	int returnVal = 0; //set to zero to stop compiler error

	switch( probeType ) {

		case 0: { //linear probing

			returnVal = (h + i)%entries.length;

			break;

		}

		case 1: { //Prime Probing ( p=3  )

			returnVal = (h + (i * 3 ))%entries.length; 

			break;

		}

		case 2: { //Prime Probing ( p=5  )

			returnVal = (h + (i * 5 ))%entries.length;

			break;

		}

		case 3: {  //Prime Probing ( p=7  )

			returnVal = (h + (i * 7 ))%entries.length;

			break;

		}

		case 4: { //Prime Probing ( p=11 )

			returnVal = (h + (i * 11))%entries.length;

			break;

		}

    		case 5: { //Quadratic Probing

			returnVal = (h + (i * i ))%entries.length;

			break;

		}

		//I am aware that my implementation of Double Hashing (which follows) is

		//wasteful in terms of computation time (we must create the array "step"

		//each and every time this code is run.  I did it this way to abstract the

		//method used to find the nextProbe() location from the put method.

		case 6: { //Double Hashing

			int[] step = { 2,3,5,7,11 };

			int stepSize = step[h%4];

			returnVal = (h + (i * stepSize))%entries.length;

			break;

		}

	}

	//return the final value

	return returnVal;

    }

    //Method to rehash the entire table.  This will get rid of NIL's

    //Precondition: none

    //Postcondition: entries will be twice the size plus one (ensures odd size)

    //               all NIL will be gone

    //               all values will be re-hash()ed

    private void rehash() {

        Entry[] oldEntries = entries;

        entries = new Entry[2*oldEntries.length+1];

        for (int k=0; k<oldEntries.length; k++) {

            Entry entry=oldEntries[k];

            if (entry==null || entry==NIL) continue;

            int h=hash(entry.key);

            for (int i=0; i<entries.length; i++) {

                int j = nextProbe(h,i);

                if (entries[j]==null) {

                    entries[j] = entry;

                    break;

                }

            }

        }

        used = size;

    }

}