Implement the following informational routines in the template code given below
ID: 3768297 • Letter: I
Question
Implement the following informational routines in the template code given below (In bolded parts).
(1) public int getEmptyBucketCount() //returns the number of empty buckets.
(2) public int getLongestCollisionIndex() //returns the index of the bucket with the most collisions.
(3) public String getWordListAtLongestCollisionIndex() //returns the set of strings located at the LongestCollissionIndex (see above). return the concatenated set of strings in the bucket with spaces in between each string.
(4) public int getLongestConsecutiveEmptyBuckets() //returns the size of the largest contiguous block of empty buckets.
(5) public int getLargestClusterSize() //returns the size of largest contiguous block of buckets that are NOT empty.
(6) public void purgeLLHashTable() //empties the HashTable.
TEMPLATE:
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;
/**
* This file defines a simple HashTable class. Keys and values in the table are of
* type String. Keys cannot be null. The table increases in size if it
* becomes more than 3/4 full.
* */
public class LLHashTable {
/**
* A ListNode holds a (key,value) pair.
*/
private static class ListNode {
String key;
String value;
ListNode next; // Pointer to next node in the list;
// A null marks the end of the list.
}
private ListNode[] table; // The hash table, represented as
// an array of linked lists.
private int count; // The number of (key,value) pairs in the
// hash table.
public int getArraySize()
{
return table.length;
}
public LLHashTable() {
table = new ListNode[512];
}
public LLHashTable(int initialSize) {
if (initialSize <= 0)
throw new IllegalArgumentException("Table size can't be negative.");
table = new ListNode[initialSize];
}
/**
* NOTE: This method is NOT usually part of a hash table.
* Feel free to use it for testing your class however. This
* lists the (key,value) pairs in each location of the table.
*/
void dumpKeyValuePairs() {
System.out.println();
for (int i = 0; i < table.length; i++) {
// Print out the location number and the list of
// key/value pairs in this location.
System.out.print(i + ":");
ListNode list = table[i]; // For traversing linked list number i.
while (list != null) {
System.out.print(" (" + list.key + "," + list.value + ")");
list = list.next;
}
System.out.println();
}
}
/**
* Associate the specified value with the specified key.
* Precondition: The key is not null.
*/
public void put(String key, String value) {
assert key != null : "The key must be non-null";
int bucket = hash(key); // Hash the key
ListNode list = table[bucket];
while (list != null) {
// Search the nodes in the list, to see if the key already exists.
if (list.key.equals(key))
break;
list = list.next;
}
// At this point, either list is null, or list.key.equals(key).
if (list != null) {
// Since list is not null, we have found the key.
// Just change the associated value.
list.value = value;
}
else {
// Since list == null, the key is not already in the list.
// Add a new node at the head of the list to contain the
// new key and its associated value.
if (count >= 0.75*table.length) {
// The table is becoming too full. Increase its size
// before adding the new node.
resize();
bucket = hash(key); // Recompute hash code, since it
// depends on the table size.
System.out.println("Just resized, the total number of buckets is now " + getArraySize());
}
ListNode newNode = new ListNode();
newNode.key = key;
newNode.value = value;
newNode.next = table[bucket];
table[bucket] = newNode;
count++; // Count the newly added key.
}
}
/**
* Retrieve the value associated with the specified key in the table,
* if there is any. If not, the value null will be returned.
* @param key The key whose associated value we want to find
* @return the associated value, or null if there is no associated value
*/
public String get(String key) {
int bucket = hash(key); // At what location should the key be?
ListNode list = table[bucket]; // For traversing the list.
//REMAINDER OF SOLUTION HERE.
return null; //note: depending on how you implement this, you may want to keep this as an ending return value
}
public int getEmptyBucketCount()
{
//returns the number of empty buckets.
return -1; //comment out before submitting.
}
public int getLongestCollisionIndex()
{
//returns the index of the bucket with the most collisions.
return -1;
}
public String getWordListAtLongestCollisionIndex()
{
//returns the set of strings located at the LongestCollissionIndex (see above).
//return the concatenated set of strings in the bucket with spaces in between each string.
return null;
}
public int getLongestConsecutiveEmptyBuckets()
{
//returns the longest contiguous block of empty buckets.
return -1;
}
public int getLargestClusterSize()
{
//returns the longest contiguous block of used buckets.
return -1;
}
public void purgeLLHashTable()
{
//Empties all of the contents in the HashTable
}
/**
* Remove the key and its associated value from the table,
* if the key occurs in the table. If it does not occur,
* then nothing is done.
*/
public void remove(String key) {
int bucket = hash(key); // At what location should the key be?
if (table[bucket] == null) {
// There are no keys in that location, so key does not
// occur in the table. There is nothing to do, so return.
return;
}
if (table[bucket].key.equals(key)) {
// If the key is the first node on the list, then
// table[bucket] must be changed to eliminate the
// first node from the list.
table[bucket] = table[bucket].next;
count--; // Remove new number of items in the table.
return;
}
// We have to remove a node from somewhere in the middle
// of the list, or at the end. Use a pointer to traverse
// the list, looking for a node that contains the
// specified key, and remove it if it is found.
ListNode prev = table[bucket]; // The node that precedes
// curr in the list. Prev.next
// is always equal to curr.
ListNode curr = prev.next; // For traversing the list,
// starting from the second node.
while (curr != null && ! curr.key.equals(key)) {
curr = curr.next;
prev = curr;
}
// If we get to this point, then either curr is null,
// or curr.key is equal to key. In the latter case,
// we have to remove curr from the list. Do this
// by making prev.next point to the node after curr,
// instead of to curr. If curr is null, it means that
// the key was not found in the table, so there is nothing
// to do.
if (curr != null) {
prev.next = curr.next;
count--; // Record new number of items in the table.
}
}
/**
* Test whether the specified key has an associated value in the table.
* @param key The key that we want to search for.
* @return true if the key exists in the table, false if not
*/
public boolean containsKey(String key) {
int bucket = hash(key);
ListNode list = table[bucket];
while (list != null)
{
if (list.key.equals(key))
return true;
list = list.next;
}
return false;
}
//returns true if HashTable contains the specified key.
/**
* Return the number of key/value pairs in the table.
*/
public int size() {
return count; //we were smart enough to track count as we've been adding/removing. Just return it.
}
/**
* Compute a hash code for the key; key cannot be null.
* The hash code depends on the size of the table as
* well as on the value returned by key.hashCode().
*/
private int hash(Object key) {
return (Math.abs(key.hashCode())) % table.length;
}
/**
* Double the size of the table, AND Redistribute the
* key/value pairs to their proper locations in the
* new table.
*/
private void resize() {
ListNode[] newtable = new ListNode[table.length*2];
for (int i = 0; i < table.length; i++)
{
ListNode list = table[i];
while (list != null)
{
ListNode next = list.next;
int hash = (Math.abs(list.key.hashCode())) % newtable.length;
list.next = newtable[hash];
newtable[hash] = list;
list = next;
}
}
//REMAINDER OF SOLUTION HERE.
table = newtable; // Replace the table with the new table.
} // end resize()
public static void main(String[] args) throws FileNotFoundException{
LLHashTable table = new LLHashTable(1024); // Initial size of table is 1024
File file = new File("dictionary.txt");
System.out.println(file.exists());
// read in dictionary of words
Scanner scanFile = new Scanner(new FileReader(file));
String theWord;
while (scanFile.hasNext()){
theWord = scanFile.next();
table.put(theWord, theWord); //put(..) calls the class' built in hash function. Don't hash here.
} //in this simplistic example, we hash theWord, then store the actual word using its own hashed value as the key.
scanFile.close();
System.out.println("Successfully loaded " + table.count + " words into our hashed table.");
System.out.println("The number of empty buckets = " + table.getEmptyBucketCount());
System.out.println("The index of the longest LinkedList (Collisions) is : " + table.getLongestCollisionIndex() );
System.out.println("The list of words at this index is: " + table.getWordListAtLongestCollisionIndex());
System.out.println("The largest block of empty buckets is: " + table.getLongestConsecutiveEmptyBuckets());
System.out.println("The largest cluster of data has " + table.getLargestClusterSize() + " contiguous non empty buckets");
System.out.println("The number of total buckets in the HashTable is " + table.getArraySize());
System.out.println("Purging data from the Hash Table");
table.purgeLLHashTable();
System.out.println("The number of empty buckets = " + table.getEmptyBucketCount());
}
}
Explanation / Answer
Here you go buddy:
package chegg_split;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.lang.management.GarbageCollectorMXBean;
import java.util.ArrayList;
import java.util.Scanner;
/**
* This file defines a simple HashTable class. Keys and values in the table are of
* type String. Keys cannot be null. The table increases in size if it
* becomes more than 3/4 full.
* */
public class LLHashTable {
/**
* A ListNode holds a (key,value) pair.
*/
private static class ListNode {
String key;
String value;
ListNode next; // Pointer to next node in the list;
// A null marks the end of the list.
}
private ListNode[] table; // The hash table, represented as
// an array of linked lists.
private int count; // The number of (key,value) pairs in the
// hash table.
public int getArraySize()
{
return table.length;
}
public LLHashTable() {
table = new ListNode[512];
}
public LLHashTable(int initialSize) {
if (initialSize <= 0)
throw new IllegalArgumentException("Table size can't be negative.");
table = new ListNode[initialSize];
}
/**
* NOTE: This method is NOT usually part of a hash table.
* Feel free to use it for testing your class however. This
* lists the (key,value) pairs in each location of the table.
*/
void dumpKeyValuePairs() {
System.out.println();
for (int i = 0; i < table.length; i++) {
// Print out the location number and the list of
// key/value pairs in this location.
System.out.print(i + ":");
ListNode list = table[i]; // For traversing linked list number i.
while (list != null) {
System.out.print(" (" + list.key + "," + list.value + ")");
list = list.next;
}
System.out.println();
}
}
/**
* Associate the specified value with the specified key.
* Precondition: The key is not null.
*/
public void put(String key, String value) {
assert key != null : "The key must be non-null";
int bucket = hash(key); // Hash the key
ListNode list = table[bucket];
while (list != null) {
// Search the nodes in the list, to see if the key already exists.
if (list.key.equals(key))
break;
list = list.next;
}
// At this point, either list is null, or list.key.equals(key).
if (list != null) {
// Since list is not null, we have found the key.
// Just change the associated value.
list.value = value;
}
else {
// Since list == null, the key is not already in the list.
// Add a new node at the head of the list to contain the
// new key and its associated value.
if (count >= 0.75*table.length) {
// The table is becoming too full. Increase its size
// before adding the new node.
resize();
bucket = hash(key); // Recompute hash code, since it
// depends on the table size.
System.out.println("Just resized, the total number of buckets is now " + getArraySize());
}
ListNode newNode = new ListNode();
newNode.key = key;
newNode.value = value;
newNode.next = table[bucket];
table[bucket] = newNode;
count++; // Count the newly added key.
}
}
/**
* Retrieve the value associated with the specified key in the table,
* if there is any. If not, the value null will be returned.
* @param key The key whose associated value we want to find
* @return the associated value, or null if there is no associated value
*/
public String get(String key) {
int bucket = hash(key); // At what location should the key be?
ListNode list = table[bucket]; // For traversing the list.
//REMAINDER OF SOLUTION HERE.
return null; //note: depending on how you implement this, you may want to keep this as an ending return value
}
public int getEmptyBucketCount()
{
//returns the number of empty buckets.
int size = getArraySize();
int count = 0;
for (int i = 0; i < size; i++)
{
if (table[i] == null)
{
count++;
}
}
return count;
//return -1; //comment out before submitting.
}
public int getLongestCollisionIndex()
{
//returns the index of the bucket with the most collisions.
int size = getArraySize();
int maxLength = 0;
int maxLengthIndex = 0;
int length = 0;
for (int i = 0; i < size; i++)
{
ListNode list = table[i];
if (list == null)
continue;
while (list.next != null)
{
length++;
if (length > maxLength)
{
maxLength = length;
maxLengthIndex = i;
}
list = list.next;
}
length = 0;
}
return maxLengthIndex;
}
public String getWordListAtLongestCollisionIndex()
{
//returns the set of strings located at the LongestCollissionIndex (see above).
//return the concatenated set of strings in the bucket with spaces in between each string.
StringBuilder str = new StringBuilder();
int maxLengthIndex = getLargestClusterSize();
ListNode list = table[maxLengthIndex];
while (list.next != null)
{
str.append(list.value);
str.append(" ");
list = list.next;
}
String wordList = str.toString();
return wordList;
}
public int getLongestConsecutiveEmptyBuckets()
{
//returns the longest contiguous block of empty buckets.
int longestEmptyBuckets = 0;
int emptyBuckets = 1;
int size = getArraySize();
int count = 0;
for (int i = 0; i < size-1; i++)
{
for (int j = 1; j < size; j++)
{
if (table[j] == null && table[i]==null)
{
emptyBuckets++;
if (emptyBuckets > longestEmptyBuckets)
{
longestEmptyBuckets = emptyBuckets;
}
}
}
emptyBuckets = 1;
}
return longestEmptyBuckets;
}
public int getLargestClusterSize()
{
//returns the longest contiguous block of used buckets.
int longestNonEmptyBuckets = 0;
int nonEmptyBuckets = 1;
int size = getArraySize();
int count = 0;
for (int i = 0; i < size-1; i++)
{
for (int j = 1; j < size; j++)
{
if (table[j] != null && table[i]!=null)
{
nonEmptyBuckets++;
if (nonEmptyBuckets > longestNonEmptyBuckets)
{
longestNonEmptyBuckets = nonEmptyBuckets;
}
}
}
nonEmptyBuckets = 1;
}
return longestNonEmptyBuckets;
}
public void purgeLLHashTable()
{
//Empties all of the contents in the HashTable
int size = table.length;
for (int i = 0; i < size; i++)
{
ListNode list = table[i];
while (list.next != null)
{
remove(list.key);
list = list.next;
}
}
}
/**
* Remove the key and its associated value from the table,
* if the key occurs in the table. If it does not occur,
* then nothing is done.
*/
public void remove(String key) {
int bucket = hash(key); // At what location should the key be?
if (table[bucket] == null) {
// There are no keys in that location, so key does not
// occur in the table. There is nothing to do, so return.
return;
}
if (table[bucket].key.equals(key)) {
// If the key is the first node on the list, then
// table[bucket] must be changed to eliminate the
// first node from the list.
table[bucket] = table[bucket].next;
count--; // Remove new number of items in the table.
return;
}
// We have to remove a node from somewhere in the middle
// of the list, or at the end. Use a pointer to traverse
// the list, looking for a node that contains the
// specified key, and remove it if it is found.
ListNode prev = table[bucket]; // The node that precedes
// curr in the list. Prev.next
// is always equal to curr.
ListNode curr = prev.next; // For traversing the list,
// starting from the second node.
while (curr != null && ! curr.key.equals(key)) {
curr = curr.next;
prev = curr;
}
// If we get to this point, then either curr is null,
// or curr.key is equal to key. In the latter case,
// we have to remove curr from the list. Do this
// by making prev.next point to the node after curr,
// instead of to curr. If curr is null, it means that
// the key was not found in the table, so there is nothing
// to do.
if (curr != null) {
prev.next = curr.next;
count--; // Record new number of items in the table.
}
}
/**
* Test whether the specified key has an associated value in the table.
* @param key The key that we want to search for.
* @return true if the key exists in the table, false if not
*/
public boolean containsKey(String key) {
int bucket = hash(key);
ListNode list = table[bucket];
while (list != null)
{
if (list.key.equals(key))
return true;
list = list.next;
}
return false;
}
//returns true if HashTable contains the specified key.
/**
* Return the number of key/value pairs in the table.
*/
public int size() {
return count; //we were smart enough to track count as we've been adding/removing. Just return it.
}
/**
* Compute a hash code for the key; key cannot be null.
* The hash code depends on the size of the table as
* well as on the value returned by key.hashCode().
*/
private int hash(Object key) {
return (Math.abs(key.hashCode())) % table.length;
}
/**
* Double the size of the table, AND Redistribute the
* key/value pairs to their proper locations in the
* new table.
*/
private void resize() {
ListNode[] newtable = new ListNode[table.length*2];
for (int i = 0; i < table.length; i++)
{
ListNode list = table[i];
while (list != null)
{
ListNode next = list.next;
int hash = (Math.abs(list.key.hashCode())) % newtable.length;
list.next = newtable[hash];
newtable[hash] = list;
list = next;
}
}
//REMAINDER OF SOLUTION HERE.
table = newtable; // Replace the table with the new table.
} // end resize()
public static void main(String[] args) throws FileNotFoundException{
LLHashTable table = new LLHashTable(1024); // Initial size of table is 1024
File file = new File("dictionary.txt");
System.out.println(file.exists());
// read in dictionary of words
Scanner scanFile = new Scanner(new FileReader(file));
String theWord;
while (scanFile.hasNext()){
theWord = scanFile.next();
table.put(theWord, theWord); //put(..) calls the class' built in hash function. Don't hash here.
} //in this simplistic example, we hash theWord, then store the actual word using its own hashed value as the key.
scanFile.close();
System.out.println("Successfully loaded " + table.count + " words into our hashed table.");
System.out.println("The number of empty buckets = " + table.getEmptyBucketCount());
System.out.println("The index of the longest LinkedList (Collisions) is : " + table.getLongestCollisionIndex() );
System.out.println("The list of words at this index is: " + table.getWordListAtLongestCollisionIndex());
System.out.println("The largest block of empty buckets is: " + table.getLongestConsecutiveEmptyBuckets());
System.out.println("The largest cluster of data has " + table.getLargestClusterSize() + " contiguous non empty buckets");
System.out.println("The number of total buckets in the HashTable is " + table.getArraySize());
System.out.println("Purging data from the Hash Table");
table.purgeLLHashTable();
System.out.println("The number of empty buckets = " + table.getEmptyBucketCount());
}
}