Using java Language
Problem:
Change the HMap class so that,
- It includes a toString method that prints out the entire contents of the internal array, showing the array index along with its contents.
- It uses quadratic probing.
- It provides a working remove method, using an additional boolean value associated with each hash table slot to track removal.
- Instead of probing it uses buckets of linked lists of MapEntry objects
// HMap.java
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 (a)
public String toString() {
return “”;
}
// Homework Problem (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 (d), change Linear Probing and Quadratic Probing to
// buckets of linked lists
// Note, to implement problem (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 (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();
}
}
//HMapDriver.java
public class HMapDriver {
public static void main(String[] args) {
boolean result;
HMap<String, String> test;
test = new HMap<String, String>(10, 0.75);
/*
* String s = null; test.put(s,”value”); test.put(“s”,null);
* System.out.println(“Expect ‘null’:t” + test.get(“s”));
* System.out.println(“Expect ‘true’:t” + test.contains(“s”)); test =
new
* ArrayListMap<String, String>();
*/
System.out.println(“Expect ‘true’:t” + test.isEmpty());
System.out.println(“Expect ‘0’:t” + test.size());
System.out.println(“Expect ‘null’:t” + test.put(“1”, “One”));
System.out.println(“Expect ‘false’:t” + test.isEmpty());
System.out.println(“Expect ‘1’:t” + test.size());
System.out.println(“Expect ‘One’:t” + test.put(“1”, “One”));
System.out.println(“Expect ‘false’:t” + test.isEmpty());
System.out.println(“Expect ‘1’:t” + test.size());
test.put(“2”, “Two”);
test.put(“3”, “Three”);
test.put(“4”, “Four”);
test.put(“5”, “Five”);
System.out.println(“Expect ‘5’:t” + test.size());
System.out.println(“Expect ‘Three’:t” + test.put(“3”, “Three XXX”));
System.out.println(“Expect ‘Three XXX’:t” + test.put(“3”, “Three”));
System.out.println(“Expect ‘5’:t” + test.size());
System.out.println(“Expect ‘true’:t” + test.contains(“5”));
System.out.println(“Expect ‘false’:t” + test.contains(“6”));
System.out.println(test);
test.put(“d”, “d”);
System.out.println(test);
System.out.println(“Expect ‘true’:t” + test.contains(“d”));
System.out.println(“Expect ‘false’:t” + test.contains(“e”));
System.out.println(“Expect ‘One’:t” + test.get(“1”));
System.out.println(“Expect ‘One’:t” + test.get(“1”));
System.out.println(“Expect ‘Two’:t” + test.get(“2”));
System.out.println(“Expect ‘Three’:t” + test.get(“3”));
System.out.println(“Expect ‘Four’:t” + test.get(“4”));
System.out.println(“Expect ‘Five’:t” + test.get(“5”));
System.out.println(“Expect ‘null’:t” + test.get(“6”));
test.put(“e”, “e”);
System.out.println(test);
System.out.println(“nThe Map is:n”);
for (MapEntry<String, String> m : test)
System.out.println(m + “n”);
System.out.println(1);
test.put(“f”, “f”);
System.out.println(2);
System.out.println(test);
System.out.println(3);
System.out.println(“nThe Map is:n”);
for (MapEntry<String, String> m : test)
System.out.println(m + “n”);
System.out.println(4);
}
}
//MapEntry.java:
public class MapEntry<K, V> {
protected K key;
protected V value;
MapEntry(K k, V v) {
key = k;
value = v;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V v) {
value = v;
}
@Override
public String toString()
// Returns a string representing this MapEntry.
{
return “Key : ” + key + “nValue: ” + value;
}
}
//MapInterface.java
import java.util.Iterator;
public interface MapInterface<K, V> extends Iterable<MapEntry<K, V>> {
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.
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.
V remove(K k);
// If an entry in this map with key k exists then the entry is removed
// from the map and the value associated with that entry is returned;
// otherwise null is returned.
//
// Optional. Throws UnsupportedOperationException if not supported.
boolean contains(K k);
// Returns true if an entry in this map with key k exists;
// Returns false otherwise.
boolean isEmpty();
// Returns true if this map is empty; otherwise, returns false.
boolean isFull();
// Returns true if this map is full; otherwise, returns false.
int size();
// Returns the number of entries in this map.
}
