Subversion Repositories programming

//import chap09.list03.Map;

// License: Public Domain (added on 07-11-2005)

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();

        System.out.print(key); //print out the key

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

        //run once for each position in the Table

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

            //get the [first, next] place to try putting the value

            int j = nextProbe(h,i); 

            //get the Entry at j (where we want to put value)

            Entry entry=entries[j]; 

            //print the location we tried to place the value

            System.out.print(" -> " + j); 

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

            if (entry==null) {

                System.out.println(); //terminate the line

                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++;

        } //end for loop

    return null;  // failure: table overflow

    } //end put()

    //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

        //run once for every place in the table

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

            //find the [first, next] place to put the value

            int j = nextProbe(h,i);

            Entry entry=entries[j];

            //break out of the loop, since the key was not found

            if (entry==null) break; 

            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 ) {

        //put in for safety, just in case

        if( newValue < 0 || newValue > 6 ) { newValue = 0; } 

        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;

    }

}