JAVA PLEASE

Exercise 1

Download OurHashMap.java and HashMapExample.java

Implement the method printBucketDistribution() in OurHashMap so that it prints the size of each linked-list. Then modify HashMapExample so that you try different numbers of buckets

How many buckets are needed to ensure that each list has at most one element?

Write the written part of this question in a text file and submit with your code.

OurHashMap.java

public class OurHashMap {

int numBuckets = 100; // Initial number of buckets.

OurLinkedListMap[] table; // The hashtable.

int numItems; // Keep track of number of items added.

// Constructor.

public OurHashMap (int numBuckets)

{

this.numBuckets = numBuckets;

table = new OurLinkedListMap [numBuckets];

numItems = 0;

}

public void add (KeyValuePair kvp)

{

if ( contains (kvp.key) ) {

return;

}

// Compute hashcode and therefore, which table entry (list).

int entry = Math.abs(kvp.key.hashCode()) % numBuckets;

// If there's no list there, make one.

if (table[entry] == null) {

table[entry] = new OurLinkedListMap ();

}

// Add to list.

table[entry].add (kvp);

numItems ++;

}

public boolean contains (String key)

{

// Compute table entry using hash function.

int entry = Math.abs(key.hashCode()) % numBuckets;

if (table[entry] == null) {

return false;

}

// Use the contains() method of the list.

return table[entry].contains (key);

}

public KeyValuePair getKeyValuePair (String key)

{

// Similar to contains.

int entry = Math.abs(key.hashCode()) % numBuckets;

if (table[entry] == null) {

return null;

}

return table[entry].getKeyValuePair (key);

}

public KeyValuePair[] getAllKeyValuePairs ()

{

if (numItems == 0) {

return null;

}

KeyValuePair[] allPairs = new KeyValuePair [numItems];

int count = 0;

for (int entry=0; entry

if (table[entry] == null) {

continue;

}

KeyValuePair[] bucketPairs = table[entry].getAllKeyValuePairs();

for (int i=0; i

allPairs[count] = bucketPairs[i];

count ++;

}

}

return allPairs;

}

public void printBucketDistribution ()

{

System.out.println ("Bucket distribution: ");

// INSERT YOUR CODE HERE.

}

}

HashMapExample.java

class TribeInfo {

String name;

int fierceness;

String planet;

public TribeInfo (String name, int fierceness, String planet)

{

this.name = name;

this.fierceness = fierceness;

this.planet = planet;

}

public String toString ()

{

return "Tribe: " + name + " from planet " + planet + " rating=" + fierceness;

}

} //end-TribeInfo

public class HashMapExample {

public static void main (String[] argv)

{

// Create an instance with 10 buckets.

OurHashMap map = new OurHashMap (10);

// Put some key-value pairs inside.

TribeInfo info = new TribeInfo ("Ewok", 3, "Endor");

KeyValuePair kvp = new KeyValuePair ("Ewok", info);

map.add (kvp);

info = new TribeInfo ("Aqualish", 6, "Ando");

kvp = new KeyValuePair (info.name, info);

map.add (kvp);

// This is more compact: create the instance in the method argument list.

info = new TribeInfo ("Gungan", 2, "Naboo");

map.add ( new KeyValuePair (info.name, info) );

info = new TribeInfo ("Amanin", 8, "Maridun");

map.add ( new KeyValuePair (info.name, info) );

info = new TribeInfo ("Jawa", 6, "Tatooine");

map.add ( new KeyValuePair (info.name, info) );

info = new TribeInfo ("Hutt", 7, "Varl");

map.add ( new KeyValuePair (info.name, info) );

// A little harder to read, but even more compact:

map.add ( new KeyValuePair ("Cerean", new TribeInfo ("Cerean", 4, "Cerea") ) );

KeyValuePair kvpResult = map.getKeyValuePair ("Hutt");

System.out.println ("Info for Hutt: " + kvpResult);

map.printBucketDistribution ();

}

}