Java

Driver:

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(" The Map is: "); for (MapEntry m: test) System.out.println(m + " ");

System.out.println(1); test.put("f","f"); System.out.println(2); System.out.println(test); System.out.println(3); System.out.println(" The Map is: "); for (MapEntry m: test) System.out.println(m + " "); System.out.println(4);

} }

Main Code:

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

MapEntry entry = new MapEntry(k, v); 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 { 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; } }

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(); }

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 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. "); 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. "); } }

public Iterator> iterator() // Returns a snapshot Iterator over this map. // Remove is not supported and throws UnsupportedOperationException.

{ return new MapIterator(); } }

1) Insert 10 random employees into a HMap of size 10. 2) Print the HMap after each insertion. 3) Compute the time required to put each employee. 4) Compute the load ratio after each insertion. 5) Compute the total time required to insert all 10 items into the HMap given the following load factors: 0.50, 0.75, 0.90. 6) Implement and test the remove method for the HMap class 7) Compute the total time required to remove all 10 items from the HMap created in step 5). 8) Write a report of your findings in the comment area at the top of your HMapDriver program. 1) Insert 10 random employees into a HMap of size 10. 2) Print the HMap after each insertion. 3) Compute the time required to put each employee. 4) Compute the load ratio after each insertion. 5) Compute the total time required to insert all 10 items into the HMap given the following load factors: 0.50, 0.75, 0.90. 6) Implement and test the remove method for the HMap class 7) Compute the total time required to remove all 10 items from the HMap created in step 5). 8) Write a report of your findings in the comment area at the top of your HMapDriver program