WebSVN – programming – Diff – /cs241/p1/HashTable.java

 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);}
+        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); }
+        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.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);
+        int h=hash(key); //hash the key
-        for (int i=0; i<entries.length; i++) {
+        for (int i=0; i<entries.length; i++) { //run once for each place in the Table
-            int j = nextProbe(h,i);
+            int j = nextProbe(h,i); //get the [first, next] place to try putting the value
-            Entry entry=entries[j];
+            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) {
+	    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);
+        int h=hash(key); //hash the key
-        for (int i=0; i<entries.length; i++) {
+        for (int i=0; i<entries.length; i++) { //run once for every place in the table
-            int j = nextProbe(h,i);
+            int j = nextProbe(h,i); //find the [first, next] place to put the value
             Entry entry=entries[j];
-            if (entry==null) break;
+            if (entry==null) break; //break out of the loop, since the key was not found
-            if (entry==NIL) continue;
+            if (entry==NIL) continue; //keep going, since we found a NIL
-            if (entry.key.equals(key)) {
+            if (entry.key.equals(key)) { //we found the key we are looking for...
-                Object oldValue=entry.value;
+                Object oldValue=entry.value; //save value to return
-                entries[j] = NIL;
+                entries[j] = NIL; //replace the value with a NIL
-                --size;
+                --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
+    }
+    //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];

Subversion Repositories programming

(root)/cs241/p1/HashTable.java @ 7 – Rev 6 → 7