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

    //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) {
        return (h + i)%entries.length;      // Linear Probing
        
        //return (h + (i * 3 ))%entries.length; //Prime Probing ( p=3  )
        //return (h + (i * 5 ))%entries.length; //Prime Probing ( p=5  )
        //return (h + (i * 7 ))%entries.length; //Prime Probing ( p=7  )
        //return (h + (i * 11))%entries.length; //Prime Probing ( p=11 ) 
    
        //return (h + (i * i ))%entries.length; //Quadratic Probing

        // STILL NEED TO ADD DOUBLE HASHING IMPLEMENTATION HERE
    
    }

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