Using java Language Problem: Change the HMap class so that, import java.util.Iterator; public class HMap implements MapInterface { 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> 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 entry = new MapEntry(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> { // 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 next() // Returns the next entry in the iteration. // Throws NoSuchElementExcep
tion – 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> iterator() { // Returns a snapshot Iterator over this map. // Remove is not supported and throws UnsupportedOperationException. return new MapIterator(); } } public class HMapDriver { public static void main(String[] args) { boolean result; HMap test; test = new HMap(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(); */ 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 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 m : test) System.out.println(m + “n”); System.out.println(4); } } public class MapEntry { 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; } } import java.util.Iterator; public interface MapInterface extends Iterable> { 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. }