Java programming homework | Computer Science homework help

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.

}







Calculate Your Essay Price
(550 words)

Approximate price: $22

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency
Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

Money-back guarantee

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read more

Zero-plagiarism guarantee

Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read more

Free-revision policy

Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read more

Privacy policy

Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read more

Fair-cooperation guarantee

By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more

New Year Offers! Enjoy 10% OFF this January using the coupon code: best10