HashTable help with 3 differnt HashType!! java! package hw5; public class HashTa
ID: 3866099 • Letter: H
Question
HashTable help with 3 differnt HashType!! java!
package hw5;
public class HashTable implements IHashTable {
//You will need a HashTable of LinkedLists.
public enum HashType {
ONE,
TWO,
THREE
}
private int nelems; //Number of element stored in the hash table
private int expand; //Number of times that the table has been expanded
private int collision; //Number of collisions since last expansion
private String statsFileName; //FilePath for the file to write statistics upon every rehash
private boolean printStats = false; //Boolean to decide whether to write statistics to file or not after rehashing
private HashType type;
//You are allowed to add more :)
/**
* Constructor for hash table
*
* @param size Initial dimensions of the hash table
* @param type Specified hash function
*/
public HashTable(int size, HashType type) {
//Initialize
}
/**
* Constructor for hash table
*
* @param size Initial dimensions of the hash table
* @param type Specified hash function
* @param fileName path to write file statistics
*/
public HashTable(int size, HashType type, String fileName) {
//Set printStats to true and statsFileName to fileName
}
@Override
public boolean insert(String value) {
return false; //TODO
}
@Override
public boolean delete(String value) {
return false; //TODO
}
@Override
public boolean contains(String value) {
return false; //TODO
}
@Override
public void printTable() {
//TODO
}
@Override
public int getSize() {
return 0; //TODO
}
/**
* This is a wrapper method to allow you to swap hash functions without
* cluttering up your other code.
*
* @param value String to hash
* @return Hash value based upon the enum
*/
protected int hash(String value) {
//replace the specified return statements with calls to your hash
// functions, passing through the string to hash
switch (type) {
case ONE:
return 0; //first function here, ex: FVN1A(value);
case TWO:
return 0; //second hash
case THREE:
return 0; //third hash
default:
return 0;
}
}
//TODO - Helper methods can make your code more efficient and look neater.
//We expect AT LEAST the following helper methods in your code
//rehash() to expand and rehash the items into the table when load factor goes over the threshold.
//printStatistics() to print the statistics after each expansion. This method will be called from insert/rehash only if printStats=true
}
here are the three hashtypes I'm using.
/** Hash Function 1 **/
private int hashFun1(String key){
int hashVal = 0;
int pow27 = 1;
for(int j = key.length()-1; j >= 0; j-- ){
int letter = key.charAt(j) - 96;
hashVal += pow27 * letter;
pow27 *= 27;
}
return hashVal % hashtable.length;
}
/** Hash function 2 **/
private int hashFun2(String key){
int hashVal = key.charAt(0) - 96;
for (int j =1; j<key.length()-1; j++){
int letter = key.charAt(j) - 96;
hashVal = hashVal*27+letter;
}
return hashVal % hashtable.length;
}
/** Hash Function 3**/
private int hasFun3(String key){
int hashVal = 0;
for(int j=0; j<key.length(); j++){
int letter = key.charAt(j) - 96;
hashVal = (hashVal*27+letter) % hashtable.length;
}
return hashVal;
}
and then the normal one Or default,
private int hashFun(String key,int hashSize) {
int hashValue = 0;
for(int i=0;i<key.length();i++) {
int letter = key.charAt(i);
hashValue = (hashValue*27 + letter)%hashSize;
return hashValue;
}
Here is more descrption about the keeping stasts method and hashtable
Please show a screen shot of your output.
Thanks you!
Part 1 Hash Table (50 points) In this part, you will implement a basic Hash Table. We have provided you with an interface and starter code that implements that interface. Fill in the blanks to complete given methods. Implementation Details You will be implementing the IHashTable interface, as additional required private helper methods. See method descriptions for details. The benefits of a hash table are a result of the ability to hash a value and then immediately locate its position if there are no collisions, or vastly narrow down the search space if there are. As such, you shouldn't need to search through the entire table to find an element for your contains() and delete() methods. Your hash table will be used exclusively to store strings, as this is the type of hash table that would be used to store a dictionary of words for uses such as spell check. To resolve collisions, use will be using separate chaining. One way of implementing this would be to have your backing storage be an array of LinkedLists. Then you would simply add to the LinkedList at the specified index when inserting elements into your hash table. The performance of hash tables degrades if there are too many collisions. As such, you will keep track of the load factor of the table (the ratio of the size of the table to the number of elements) and once this value exceeds %, you must double the size of the table and rehash all of the values. You will be implementing a private helper method rehash() to accomplish this. You will be implementing three different hash functions. You must implement a rolling hash using Horner's Method, as well as two other hash functions of your choosing. A list of possible hash functions are provided in the starter files, but feel free to use other hash functions as well. Remember, at the minimum your hash functions must be deterministic, although your goal is for them to be uniform and fast. You will later compare the performance of the hash functions and record your results in HW5.txt. You must actually implement the algorithms in your HashTable class. If you use String.hashCode(), you not receive any credit for this assignment.Explanation / Answer
HashTable.java
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
@SuppressWarnings("unused")
public class HashTable implements IHashTable {
// You will need a HashTable of LinkedLists.
private LinkedList<String>[] table;
private int nelems; // Number of element stored in the hash table
private int expand; // Number of times that the table has been expanded
private int collision; // Number of collisions since last expansion
private String statsFileName; // FilePath for the file to write statistics
// upon every rehash
private boolean printStats = false; // Boolean to decide whether to write
// statistics to file or not after
// rehashing
private int longChain;
private static final int WORD_WIDTH = 32;
private static final int CRC_HASH_SHIFT = 5;
private static final double LOAD_FACTOR = ((double) 2 / 3);
private static final int DOUBLE = 2;
// You are allowed to add more :)
/**
* Constructor for hash table
*
* @param Initial
* size of the hash table
*/
@SuppressWarnings("unchecked")
public HashTable(int size) {
table = new LinkedList[size];
for (int i = 0; i < size; i++)
table[i] = new LinkedList<String>();
}
/**
* Constructor for hash table
*
* @param Initial
* size of the hash table
* @param FileFileReade
* path to write statistics
*/
@SuppressWarnings("unchecked")
public HashTable(int size, String fileName) {
table = new LinkedList[size];
statsFileName = fileName;
printStats = true;
for (int i = 0; i < size; i++)
table[i] = new LinkedList<String>();
// Set printStats to true and statsFileName to fileName
}
/**
* Inserts the given element in the hash table
*
* @param value
* @throws NullPointerException
* if value is null
* @return boolean Success of insertion
*/
@Override
public boolean insert(String value) {
if (value == null)
throw new NullPointerException();
else {
int h1 = hash(value);
if (!table[h1].contains(value)) {
rehash();
// checking for collisions
if ((table[h1].size() != 0))
collision++;
table[h1].add(value);
if (table[h1].size() > longChain)
longChain = table[h1].size();
nelems++;
return true;
} else
return false;
}
}
/**
* Deletes the element from the hash table
*
* @param value
* @throws NullPointerException
* if value is null
* @return boolean Success of deletion
*/
@Override
public boolean delete(String value) {
if (value == null)
throw new NullPointerException();
else {
int h1 = hash(value);
if (!table[h1].contains(value)) {
return false;
} else {
table[h1].remove(value);
nelems--;
return true;
}
}
}
/**
* Checks if the hash table has the given value
*
* @param value
* @throws NullPointerException
* if value is null
* @return boolean Success of insertion
*/
@Override
public boolean contains(String value) {
if (value == null)
throw new NullPointerException();
else {
int h1 = hash(value);
return table[h1].contains(value);
}
}
/**
* Prints the table on stdout
*/
@Override
public void printTable() {
for (int i = 0; i < table.length; i++) {
System.out.print("" + i + ": ");
if (table[i] == null || table[i].size() == 0) {
System.out.println("");
} else {
for (int j = 0; j < table[i].size(); j++) {
// if the last element in the list
if (j == table[i].size() - 1)
System.out.print(table[i].get(j));
else
System.out.print(table[i].get(j) + ", ");
}
System.out.println("");
}
}
}
/**
* Returns the number of elements in the hash table
*/
@Override
public int getSize() {
return nelems;
}
/**
* Generates a hash code for the given key
*
* @param key
* @return int
*/
private int hash(String key) {
int hashValue = 0;
for (int i = 0; i < key.length(); i++) {
int letter = key.charAt(i);
int leftShiftedValue = hashValue << CRC_HASH_SHIFT;
int rightShiftedValue = hashValue >>> (WORD_WIDTH - CRC_HASH_SHIFT);
hashValue = ((leftShiftedValue | rightShiftedValue) ^ letter);
}
return Math.abs(hashValue) % table.length;
}
/**
* Resizes the hash table if load factor is crossed and reinserts every
* element
*/
@SuppressWarnings("unchecked")
private void rehash() {
double lFact = ((double) nelems / table.length);
// check the need to rehash
if (lFact > LOAD_FACTOR || nelems == table.length) {
expand++;
if (printStats)
printStatistics(statsFileName, lFact);
collision = 0;
longChain = 0;
Iterator<String> iter;
LinkedList<String>[] oldTable = table;
table = new LinkedList[rehashSize(oldTable.length * DOUBLE)];
// instantiating all the linked lists
for (int i = 0; i < table.length; i++)
table[i] = new LinkedList<String>();
// copying to new table
for (int i = 0; i < oldTable.length; i++) {
if (oldTable[i] != null) {
iter = oldTable[i].iterator();
while (iter.hasNext()) {
insert(iter.next());
--nelems; // to counter the unrequired
// increase in elements
}
}
}
}
}
/**
* Determines the new size of the hash table Finds a prime size to decrease
* collisions
*
* @param num
* @return int size of the table
*/
private int rehashSize(int num) {
while (true) {
num++;
if (num > 2 && num % 2 == 0) {
continue;
}
int top = (int) Math.sqrt(num) + 1;
int i;
for (i = 3; i < top; i += 2) {
if (num % i == 0) {
break;
}
}
// To check if the loop was broken
if (i < top)
continue;
else {
return num;
}
}
}
/**
* Writes the statistics to a text file
*
* @param filename
* @param lFact
*/
private void printStatistics(String filename, double lFact) {
// To truncate the double values to 2 spaces
DecimalFormat df = new DecimalFormat("##.##");
try (FileWriter fw = new FileWriter(filename, true);
BufferedWriter bw = new BufferedWriter(fw);)
{
bw.write("" + expand + " resizes, load factor " + df.format(lFact)
+ ", " + collision + " collisions, " + "longest chain "
+ longChain + "ratio " + ((double) collision) / nelems
+ " ");
} catch (Exception e) {
// If file not found
}
}
}
IHashTable.java
public interface IHashTable {
/** Insert the string value into the hash table
*
* @param value value to insert
* @throws NullPointerException if value is null
* @return true if the value was inserted, false if the value was already present
*/
boolean insert(String value);
/** Delete the given value from the hash table
*
* @param value value to delete
* @throws NullPointerException if value is null
* @return true if the value was deleted, false if the value was not found
*/
boolean delete(String value);
/** Check if the given value is present in the hash table
*
* @param value value to look up
* @throws NullPointerException if value is null
* @return true if the value was found, false if the value was not found
*/
boolean contains(String value);
/** Print the contents of the hash table. Print nothing if table is empty
*
* Example output for this function:
*
* 0:
* 1:
* 2: marina, fifty
* 3: table
* 4:
*
*/
void printTable();
/**
* Return the number of elements currently stored in the hashtable
* @return nelems
*/
int getSize();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.