Here is the link to the list that will be needed for the program https://www-cs-
ID: 3915180 • Letter: H
Question
Here is the link to the list that will be needed for the program
https://www-cs-faculty.stanford.edu/~knuth/sgb-words.txt
Description: We will be hashing objects into hash sets with 2 different sizes and using 3 different hash functions: Array sizes: 5749, 2857 Hash functions: x (xmod n+1 (xmod n Note: Use separate chaining to handle collisions We will be using the Stanford Graph Base that contains a list of the 5757 five-letter words in English. Here is a link: https /wwwcs faculty stanford.eduleknuthisgh-words.axt Complete the following steps for each word in the file: 1. Compute the hash code of the word. 2. Compute the index, i, where the word would be placed in the array. 3. Add 1 to xi] to keep up with the number of times a word hashes to location i. . When you have read the file completely, compute and print the following statistics for each unique hash set: . The number of empty positions (buckets) in the array 2. The maximum number stored in a single array location (the longest bucket chain). 3. The average of all non-zero array entries (the average bucket chain length). . Given the above results, which hash function and array size would you recommend.Explanation / Answer
Ans Given By:
public class tester {
public static void main(String[] args) {
String FILENAME = "words.txt";
int x[] = new int[5749];
BufferedReader br = null;
FileReader fr = null;
try {
fr = new FileReader(FILENAME);
br = new BufferedReader(fr);
String word;
while ((word = br.readLine()) != null) {
int hash = word.hashCode();
if(hash < 0)
hash = -1 * hash;
int i = hash % 5748;
x[i] ++;
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (br != null)
br.close();
if (fr != null)
fr.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
int numEmpty = 0;
int maxNum = 0;
double avg = 0;
for(int i=0; i<x.length; i++) {
if(x[i] == 0)
numEmpty ++;
if(x[i] > maxNum)
maxNum = x[i];
avg += x[i];
}
System.out.println("number of empty positions = " + numEmpty);
System.out.println("maxinum number stored in a single array location = " + maxNum);
System.out.println("average of non-zero entries = " + avg/(x.length - numEmpty));
Number Of Empty Positions = 2074
Max Num Store In a Single Arrey Location = 6
Avg Of Non Zero Entires = 1.5665306122448979