import java.util.*; public class HashMap implements Map { public HashEntry[] bucket; // The hash table (buckets) public int capacity; // capacity == bucket.length public int NItems; // NItems = # entries in hash table public int MAD_p; public int MAD_a; public int MAD_b; public int index_for_key; public HashEntry AVAILABLE = new HashEntry(null, null); // Special entry to // mark deleted entries /* =============================================================== General Constructor: initialize prime number p Create an array (bucket) of given size =============================================================== */ public HashMap(int p, int MapArraySize) { capacity = MapArraySize; bucket = new HashEntry[ capacity ]; // Java can't create gen arrays easily NItems = 0; java.util.Random rand = new java.util.Random(); MAD_p = p; // Prime number in MAD MAD_a = rand.nextInt(MAD_p-1) + 1; // Multiplier in MAD MAD_b = rand.nextInt(MAD_p); // Shift amount in MAD } /* =============================================================== Common Constructor: pick the default prime number 109345121 Create an array (bucket) of given size =============================================================== */ public HashMap(int MapArraySize) { this( 109345121, MapArraySize ); // Calls general constructor } public HashMap() { this( 109345121, 1000 ); // Default array size = 1000 } /* ****************************************************************** Map methods ****************************************************************** */ public int size() { return( NItems ); } public boolean isEmpty() { return( NItems == 0 ); } /* =============================================================== Hash function: 1. uses the Hash Code inside the K class 2. uses the MAD compression function hash index = [ (a*HashCode + b) % p ] % N =============================================================== */ public int hashValue(K key) { int x = key.hashCode(); // K has a built-in hashCode() !!! return (int) ((Math.abs(x*MAD_a + MAD_b) % MAD_p) % capacity); } /* ==================================================================== findEntry(key): find index of the array for given key Return value: 1 ==> key is found in the hash table Set index_for_key such that: Entry[index_for_key].key == key 0 ==> key is NOT found Entry[index_for_key] is where you can STORE the key ==================================================================== */ public int findEntry(K key) { int i; int start; if ( key == null ) { index_for_key = -1; // Error return ( -1 ); // Not found } i = hashValue(key); // Start location to look for key start = i; // Remember the start location (to detect end) index_for_key = -1; // Flag "no hole found" condition. do { HashEntry e; e = bucket[i]; if ( e != null ) { // Bucket contains something // Possibilities: // 1. special EMPTY marker --> remember FIRST marker and // go to next entry // 2. contains the search key --> return FOUND // 3. contains some other key --> go to next entry if (e == AVAILABLE) { // entry in bucket was deleted if ( index_for_key < 0 ) index_for_key = i; // remember the FIRST available slot } else if ( key.equals(e.getKey()) ) // we have found our key { index_for_key = i; return 1; // key found } i = (i + 1) % capacity; // Check the next slot... if any } else { /* -------------------------------------------------- Bucket contains NULL: chain is broken We know the key is not in hash table -------------------------------------------------- */ if ( index_for_key < 0 ) // Did we found an EMPTY marker ? index_for_key = i; // No --> insert key here if needed return(0); // Return "not found" indication } } while (i != start); // Stop when you wrap around return 0; // Not found } public V get(K k) { int found = findEntry(k); // Find the array index for the key k // If found > 0, index_for_key is the index if ( found > 0 ) { return bucket[index_for_key].getValue(); // return value } else { return null; // Key not found } } public V put (K key, V value) { int found = findEntry(key); //find the appropriate spot for this entry if ( found > 0 ) // key found { V oldValue = bucket[index_for_key].setValue(value);// set new value return ( oldValue ); // Return old value } /* ======================================================= NEW: Keep occupance (load factor) of array below 50% ======================================================= */ if (NItems >= capacity/2) { rehash(); // rehash to keep the load factor <= 0.5 found = findEntry(key); // find the appropriate spot for this entry // We must do it again, because hash method has // changed !!! } /* =================================================== Insert (key, value) in bucket[index_for_key] =================================================== */ bucket[index_for_key] = new HashEntry(key, value); // Insert it NItems++; return null; // there was no previous value } /* ************************************************************** rehash(): increase the hash table size ************************************************************** */ public void rehash() { HashEntry[] old = bucket; // Old contains the original entries capacity = 2*capacity; bucket = new HashEntry[capacity]; // new bucket is twice as big System.out.println("Rehash: increase hash table size to: " + capacity); System.out.println("Rehash the entries into the new hash table...."); java.util.Random rand = new java.util.Random(); MAD_a = rand.nextInt(MAD_p-1) + 1; // new hash scaling factor MAD_b = rand.nextInt(MAD_p); // new hash shifting factor for (int i=0; i e; e = old[i]; // Process old entry i if ( (e != null) && (e != AVAILABLE) ) { // e contains a non-empty entry findEntry(e.getKey()); // Find index for the key bucket[index_for_key] = e; // Insert in new bucket } } System.out.println("Done !"); } public V remove (K key) { int found = findEntry(key); // find this key first if ( found == 0 ) return null; // nothing to remove V toReturn = bucket[index_for_key].getValue(); // Remember old value bucket[index_for_key] = AVAILABLE; // mark this slot as deactivated NItems--; return toReturn; // Return old value } /* ======================================================= Value-added methods... I will only implement keySet() I will omit values() and entrySet(), they are similar ======================================================= */ public Collection keySet() { LinkedList r = new LinkedList(); // One of the classes that implements // "Iterable" is LinkedList for (int i = 0; i < bucket.length; i++) { HashEntry e; e = bucket[i]; if ((e != null) && (e != AVAILABLE)) { // e is a valid entry r.add( e.getKey() ); } } return(r); } public Collection values() { LinkedList r = new LinkedList(); // One of the classes that implements // "Iterable" is LinkedList for (int i = 0; i < bucket.length; i++) { HashEntry e; e = bucket[i]; if ((e != null) && (e != AVAILABLE)) { // e is a valid entry r.add( e.getValue() ); } } return(r); } public Collection> entrySet() { LinkedList> r = new LinkedList>(); // One of the classes that implements // "Iterable" is LinkedList for (int i = 0; i < bucket.length; i++) { HashEntry e; e = bucket[i]; if ((e != null) && (e != AVAILABLE)) { // e is a valid entry r.add( e ); } } return(r); } public String toString() { String output = "{"; for (int i = 0; i < bucket.length; i++) { HashEntry e; e = bucket[i]; if ((e != null) ) { // e is a valid entry if ( e == AVAILABLE ) output = output + "(*,*) "; else output = output + e + " "; } } output += "}"; return output; } }