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