Java programming homework
//--------------------------------------------------------------------------- // HMap.java by Dale/Joyce/Weems Chapter 8 // // Implements a map using an array-based hash table, linear probing collision // resolution. // // The remove operation is not supported. Invoking it will result in the // unchecked UnsupportedOperationException being thrown. // // A map provides (K = key, V = value) pairs, mapping the key onto the value. // Keys are unique. Keys cannot be null. // // Methods throw IllegalArgumentException if passed a null key argument. // // Values can be null, so a null value returned by put or get does // not necessarily mean that an entry did not exist. //---------------------------------------------------------------------------
import java.util.Iterator;
public class HMap<K, V> implements MapInterface<K, V> { protected MapEntry[] map;
protected final int DEFCAP = 1000; // default capacity protected final double DEFLOAD = 0.75; // default load
protected int origCap; // original capacity protected int currCap; // current capacity protected double load;
protected int numPairs = 0; // number of pairs in this map
public HMap() { map = new MapEntry[DEFCAP]; origCap = DEFCAP; currCap = DEFCAP; load = DEFLOAD;
}
public HMap(int initCap, double initLoad) { map = new MapEntry[initCap]; origCap = initCap; currCap = initCap; load = initLoad;
}
private void enlarge() { // Increments the capacity of the map by an amount // equal to the original capacity. // create a snapshot iterator of the map and save current size Iterator<MapEntry<K, V>> i = iterator(); int count = numPairs;
// create the larger array and reset variables map = new MapEntry[currCap + origCap]; currCap = currCap + origCap; numPairs = 0;
// put the contents of the current map into the larger array
MapEntry entry;
for (int n = 1; n <= count; n++) { entry = i.next(); this.put((K) entry.getKey(), (V) entry.getValue());
} }
// Homework Problem 28(a) public String toString() {
return ""; }
// Homework Problem 28(b), change Linear Probing to Quadratic Probing public V put(K k, V v) {
// If an entry in this map with key k already exists then the value // associated with that entry is replaced by value v and the original // value is returned; otherwise, adds the (k, v) pair to the map and // returns null. if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
MapEntry<K, V> entry = new MapEntry<K, V>(k, v);
int location = Math.abs(k.hashCode()) % currCap;
// Linear Probing while ((map[location] != null) && !(map[location].getKey().equals(k)))
location = (location + 1) % currCap;
if (map[location] == null) { // k was not in map map[location] = entry; numPairs++;
if ((float) numPairs / currCap > load) enlarge();
return null; } else { // k already in map
V temp = (V) map[location].getValue(); map[location] = entry;
return temp; }
}
// Homework Problem 28(d), change Linear Probing and Quadratic Probing to // buckets of linked lists // Note, to implement problem 28(d), comment out Linear/Quadratic Probing
above, // and uncomment Buckets of Linked Lists below.
// public V put(K k, V v) { // // return null; // } //
public V get(K k) {
// If an entry in this map with a key k exists then the value associated
// with that entry is returned; otherwise null is returned. if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
int location = Math.abs(k.hashCode()) % currCap;
while ((map[location] != null) && !(map[location].getKey().equals(k))) location = (location + 1) % currCap;
if (map[location] == null) // k was not in map return null;
else // k in map return (V) map[location].getValue();
}
// Homework Problem 28(c) public V remove(K k) {
// Throws UnsupportedOperationException. throw new UnsupportedOperationException("HMap does not allow remove.");
}
public boolean contains(K k) { // Returns true if an entry in this map with key k exists; // Returns false otherwise. if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
int location = Math.abs(k.hashCode()) % currCap;
while (map[location] != null) if (map[location].getKey().equals(k))
return true; else
location = (location + 1) % currCap;
// if get this far then no current entry is associated with k return false;
}
public boolean isEmpty() { // Returns true if this map is empty; otherwise, returns false. return (numPairs == 0);
}
public boolean isFull() { // Returns true if this map is full; otherwise, returns false. return false; // An HMap is never full
}
public int size() { // Returns the number of entries in this map. return numPairs;
}
private class MapIterator implements Iterator<MapEntry<K, V>> {
// Provides a snapshot Iterator over this map. // Remove is not supported and throws UnsupportedOperationException. int listSize = size(); private MapEntry[] list = new MapEntry[listSize]; private int previousPos = -1; // previous position returned from list
public MapIterator() { int next = -1; for (int i = 0; i < listSize; i++) {
next++; while (map[next] == null)
next++; list[i] = map[next];
} }
public boolean hasNext() // Returns true if the iteration has more entries; otherwise returns
false. {
return (previousPos < (listSize - 1)); }
public MapEntry<K, V> next() // Returns the next entry in the iteration. // Throws NoSuchElementException - if the iteration has no more entries {
if (!hasNext()) throw new IndexOutOfBoundsException("illegal invocation of
next " + " in HMap iterator.\n"); previousPos++; return list[previousPos];
}
public void remove() // Throws UnsupportedOperationException. // Not supported. Removal from snapshot iteration is meaningless. {
throw new UnsupportedOperationException("Unsupported remove attempted on " + "HMap iterator.\n");
} }
public Iterator<MapEntry<K, V>> iterator() { // Returns a snapshot Iterator over this map. // Remove is not supported and throws UnsupportedOperationException. return new MapIterator();
} }