package finiteAutomata; import java.util.Vector; /** * Data structure which allows for insertions, deletions, and finds in * constant average time. * * <BR><BR>This Hashtable class uses separate chaining to store Associations * (key-value pairs). Any non-null object can be used as the key (which * is used as input to the hashing function). To successfully store and * retrieve values from a hashtable, the objects used as keys must * implement the hashCode method and the equals method. To store an * Association, apply the hash function to its key and store the * Association in the resulting list (first check that an equivalent * Association is not already present). To retrieve an Association, * apply the hash function to its key and search for it in the resulting * list. If the hashtable is appropriately long and if the hash function * does a good job of distributing the keys evenly among the hashing * locations, then all the lists should be short and it will be very * quick to find, insert, and delete based on keys. * * <BR><BR>Data Fields: * A Hashtable is based on an array "table" of Vectors. The integer field * "tableSize" gives the length of the array, and should be a prime number * (to help insure even distribution for the hashing function). * The integer field "size" tells how many Associations are currently * stored; load factor can thus be calculated by size / tableSize. (Load * factor around 1.0 is ideal for efficient use of time and space in open * chaining.) * * @author Barbara Wahl * @version Fall 2007 */ public class Hashtable { // ** DATA FIELDS ** /** * Vector lists for storing Assocations */ protected Vector[] table; /** * length of the "table" array */ protected int tableSize; /** * number of Associations currently stored */ protected int size; // ** CONSTRUCTORS ** /** * 1-parameter constructor. * @param n table size * @pre n > 0 * @post creates an empty Hashtable with tableSize = n */ public Hashtable(int n) { Assert.pre(n > 0,"n is positive"); table = new Vector[n]; for(int i=0; i<n; i++) table[i] = new Vector(); tableSize = n; size = 0; } /** * 0-parameter constructor. *@post creates an empty Hashtable with tableSize = 101 */ public Hashtable() { this(101); } /** * Returns tableSize. * @return tableSize */ public int tableSize() { return tableSize; } /** * Returns number of Associations currently stored. * @return size */ public int size() { return size; } /** * Returns the current load factor, size divided by tableSize. * @return size / tableSize */ public double loadFactor() { double loadF = ((double)size)/((double)tableSize); return loadF; } /** * Returns the hash location for the provided key. * @param key the key to be hashed on * @return key.hashCode() % tableSize, the hashing location * @pre key is not null */ protected int locate(Object key) { return Math.abs(key.hashCode() % tableSize); } /** * Returns the index, relative to the Vector table[hash], of * the Association with the given key. * @param key the key to be located * @param hash indexes the Vector to be searched * @return index of the Association in table[hash] with the * given key, or -1 if not found there * @pre key is not null * @pre 0 <= hash < tableSize */ protected int indexOf(Object key, int hash) { Vector v = table[hash]; return v.indexOf(new Association(key)); } /** * Returns the value associated with key, or null (if not found). * @param key the key to be searched on * @return value of the stored Association with matching key * @pre key is not null * @post this Hashtable is not modified (the matching Association * is not removed, just accessed) */ public Object get(Object key) { Association current; int hash = locate(key); // which vector to look in int index = indexOf(key,hash); // location in that vector if(index < 0) return null; else { current = (Association)table[hash].elementAt(index); return (current.getValue()); } } /** * Returns true if an item with this same key exists in the hashtable. * @param key the key to be searched on * @return true iff an Association with matching key is found * @pre key is not null */ public boolean contains(Object key) { int hash = locate(key); Association current; // if key is in table, it is in vector table[hash] boolean found = false; for(int i=0; i<table[hash].size(); i++) { current = (Association)table[hash].elementAt(i); if(current.getKey().equals(key)) { found = true; break; } } return found; } /** * Inserts an Association. * @param key the key to be searched on * @param value the associated value for key * @pre key is not null * @post if an equivalent Association is not found in the table, * the given key-value pair is added to the appropriate vector * and size is incremented */ public void insert(Object key, Object value) { int hash = locate(key); // which vector to look in int index = indexOf(key,hash); // location in that vector if(index < 0) // if not already in table... { table[hash].add(new Association(key,value)); size++; } } /** * Removes an Association. * @param key the key to be searched on * @return the associated value for key, or null if not found * @pre key is not null * @post if found, the equivalent Association is removed from the * table and size is decremented */ public Object remove(Object key) { int hash = locate(key); // which vector to look in int index = indexOf(key,hash); // location in that vector if(index < 0) // if not in table... return null; size--; // else, decrement size & return value return ((Association)table[hash].remove(index)).getValue(); } /** * True if no Associations are stored. * @return size == 0 */ public boolean isEmpty() { return size == 0; } /** * Pretty-prints the hash table information. * @post Reports tableSize and load factor, and for each stored * Association prints the hash value, the index relative to the * vector in which the Association is stored, and the key-value * pair. */ public void printTable() { System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"); System.out.println("tableSize = " + tableSize); System.out.println("size = " + size); System.out.println("load factor = " + this.loadFactor()); System.out.println("KEY-VALUE PAIRS IN TABLE:"); for(int i=0; i<tableSize; i++) for(int j=0; j<table[i].size(); j++) System.out.println("hash = " +i+", index = " +j+", pair = " + table[i].elementAt(j)); System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%"); } // ** TEST METHOD ** public static void main(String[] args) { // create a hashtable Hashtable t = new Hashtable(19); // store associations in Hashtable t.insert("zero",new Integer(0)); t.insert("one",new Integer(1)); t.insert("two",new Integer(2)); t.insert("three",new Integer(3)); t.insert("four",new Integer(4)); t.insert("five",new Integer(5)); t.insert("six",new Integer(6)); t.insert("seven",new Integer(7)); t.insert("eight",new Integer(8)); t.insert("nine",new Integer(9)); t.insert("ten",new Integer(10)); // print table t.printTable(); // remove two items & print again t.remove("ten"); t.remove("nine"); t.printTable(); // test contains System.out.println("Does table contain \"eleven\"? " + t.contains("eleven")); System.out.println("Does table contain \"five\"? " + t.contains("five")); // try adding item with duplicate key t.insert("seven", new Integer(20)); t.printTable(); // try removing item which isn't there t.remove("cat"); t.printTable(); // try get method System.out.println("The value associated with \"two\" is: " + t.get("two")); System.out.println("The value associated with \"cat\" is: " + t.get("cat")); } }