Using java Language

 

Problem:

Change the HMap class so that,

1. It includes a toString method that prints out the entire contents of the internal array, showing the array index along with its contents.
2. It uses quadratic probing.
3. It provides a working remove method, using an additional boolean value associated with each hash table slot to track removal.
4. 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.

}