JAVA PLEASE Exercise 1 Download OurHashMap.java and HashMapExample.java Implemen
ID: 3712355 • Letter: J
Question
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<numBuckets; entry++) {
if (table[entry] == null) {
continue;
}
KeyValuePair[] bucketPairs = table[entry].getAllKeyValuePairs();
for (int i=0; i<bucketPairs.length; 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 ();
}
}
Explanation / Answer
//KeyValuePair.java
public class KeyValuePair {
String key;
TribeInfo value;
public KeyValuePair(String name, TribeInfo info) {
this.key = name;
this.value = info;
}
@Override
public String toString() {
return " [" + key + ", " + value + "] ";
}
}
//OurLinkedListMap.java
import java.util.ArrayList;
public class OurLinkedListMap {
ArrayList<KeyValuePair> list;
public OurLinkedListMap() {
list = new ArrayList<KeyValuePair>();
}
public void add(KeyValuePair kvp) {
list.add(kvp);
}
public boolean contains(String key) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(key)) {
return true;
}
}
return false;
}
public KeyValuePair getKeyValuePair(String key) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).key.equals(key)) {
return list.get(i);
}
}
return null;
}
public KeyValuePair[] getAllKeyValuePairs() {
KeyValuePair[] allPairs = new KeyValuePair[list.size()];
int i = 0;
for (KeyValuePair keyValuePair : list) {
allPairs[i] = keyValuePair;
i++;
}
return allPairs;
}
}
//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 ();
}
}
//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 < numBuckets; entry++) {
if (table[entry] == null) {
continue;
}
KeyValuePair[] bucketPairs = table[entry].getAllKeyValuePairs();
for (int i = 0; i < bucketPairs.length; i++) {
allPairs[count] = bucketPairs[i];
count++;
}
}
return allPairs;
}
public void printBucketDistribution() {
System.out.println("Bucket distribution: ");
// INSERT YOUR CODE HERE.
if (numItems == 0) {
return;
}
for (int entry = 0; entry < numBuckets; entry++) {
if (table[entry] == null) {
System.out.println(entry + "=> Empty");
continue;
}
System.out.print(entry + "=> ");
KeyValuePair[] bucketPairs = table[entry].getAllKeyValuePairs();
for (int i = 0; i < bucketPairs.length; i++) {
if (i != 0) {
System.out.print(",");
}
System.out.print(bucketPairs[i]);
}
System.out.println();
}
}
}
Console Ouput:
Info for Hutt: [Hutt, Tribe: Hutt from planet Varl rating=7]
Bucket distribution:
0=> [Cerean, Tribe: Cerean from planet Cerea rating=4]
1=> [Hutt, Tribe: Hutt from planet Varl rating=7]
2=> [Aqualish, Tribe: Aqualish from planet Ando rating=6]
3=> Empty
4=> Empty
5=> Empty
6=> [Ewok, Tribe: Ewok from planet Endor rating=3] , [Amanin, Tribe: Amanin from planet Maridun rating=8]
7=> [Jawa, Tribe: Jawa from planet Tatooine rating=6]
8=> [Gungan, Tribe: Gungan from planet Naboo rating=2]
9=> Empty
Number of buckets required is same as the number of items that need to be inserted into map
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.