Question
I have to use the linkedlist iterator to figure out if the word is already in my hash table. I have most of the code
I have to use the linkedlist iterator to figure out if the word is already in my hash table. I have most of the code below but some of it shows errors. I am trying to use LinkedLists to store any collisions of already posted words. I have my hash code that I am using below as well. I also have to keep track of where at in the linked list the word is, which is what the variable steps is counting. If the word is already in my list then I just add one to the occurence and not add the word again. I just need help with figuring out how to implement this and display the results into an excel sheet.
// A node of chains
class HashNode
{
Key word;
int occurences;
int steps;
// Reference to next node
HashNode next;
// Constructor
public HashNode(Key word)
{
this.word = word;
int occurrences = 0;
int steps = 0;
}
}
// Class to represent entire hash table
class hashTable
{
// listPointers is used to store array of chains
private LinkedList listPointers;
// Current capacity of array list
private int maxSize;
// Current size of array list
private int size;
// Constructor (Initializes capacity, size and
// empty chains.
public hashTable(int x)
{
listPointers = new LinkedList();
maxSize = x;
size = 0;
// Create empty chains
for (int i = 0; i
listPointers.add(null);
}
public int size() {
return size;
}
// This implements hash function to find index
// for a word
private int hashIndex(Key word)
{
int hashCode = Math.abs(word.hashCode()%maxSize);
return hashCode;
}
// Adds a word value pair to hash
public void add(Key word)
{
int stepsNeeded =0;
// Find head of chain for given word
int sizeIndex = hashIndex(word);
HashNode head = listPointers.get(sizeIndex);
// Check if word is already present
while (head != null)
{
stepsNeeded++;
if (head.word.equals(word))
{
head.steps = stepsNeeded;
head.occurences = head.occurences+1;
return;
}
head = head.next;
}
// Insert word in chain
size++;
head = listPointers.get(sizeIndex);
HashNode newNode = new HashNode(word);
newNode.next = head;
listPointers.set(sizeIndex, newNode);
}
public void get(Key key) {
// Find head of chain for given key
int listPointersIndex = hashIndex(key);
HashNode head = listPointers.get(listPointersIndex);
// Search key in chain
while (head != null)
{
if (head.word.equals(key)){
System.out.println("Occurences:" + head.occurences + " Steps:" + head.steps);
return;
}
head = head.next;
}
// If key not found
head = null;
System.out.println("Not Occurred Yet.");
}
// Driver method to test hashTable class
public static void main(String[] args)
{
hashTable hash500 = new hashTable(500);
hashTable hash1000 = new hashTable(1000);
hashTable hash2000 = new hashTable(2000);
File fileName = new File("Stuff.txt");
Scanner fileIn;
String word;
try{
fileIn = new Scanner(new FileInputStream(fileName));
while(fileIn.hasNext()){
word = fileIn.next();
hash500.add(word);
hash1000.add(word);
hash2000.add(word);
}
System.out.println(hash500.size());
System.out.println(hash500.size());
System.out.println(hash1000.size());
System.out.println(hash2000.size());
fileIn.close();
}catch(FileNotFoundException e){
System.err.println("File '" + fileName + "' was not found...");
}
}
}
The Java String class implements a hash function. For any String, the command myString.hashcodel) hashes the string and returns a value. The hash may be negative, so for this assignment it's better to use the absolute value of the hash. Convert all letters to lowercase so that different capitalizations hash to the same value Your program should create hash tables of various sizes: 500, 2000, 5000 slots. The hash table should use a linked list in each slot to keep track of the words that hash to that slot. It should read each word in the novel, then search for or insert the word in the hash table based on the hash function: Math.abs(myString.hashcode()%tablesize) The program should use LinkedLists to store collisions. You do not need to write your own linked list. When adding an item to the list, use an Iterator or ListIterator to determine whether the word is already in the table. Doing this will enable you to keep track of the number of steps required to look up and add the word. Your program should keep track of the number of occurrences of each word, and the number of steps it took to find or insert the word. Number of steps is based on the position of the word in the linked list. If the word is first, it took 1 step to find. If the word is second, it took 2 steps to find, etc. The program should print a file that contains each word, the number of occurrences of that word, and the number of steps it took to find the word. Make the file a CSV so that you can read it in Excel. Use Excel to calculate statistics such as the total number of words, the total number of occurrences, total steps, and average steps per word. Make a chart that plots the average number of steps against the size of the hash table. In this project, only one algorithm is used, so there is no need for an interface, however, you must still use good object-orient design principles. You should create a class that holds a word, its number of occurrences, and the total number of steps to record those occurrences. You should create a second class that has the hash table as an instance variable, and contains a method to add items to the hash table. Your main() method should be in a third separate class. The Java String class implements a hash function. For any String, the command myString.hashcodel) hashes the string and returns a value. The hash may be negative, so for this assignment it's better to use the absolute value of the hash. Convert all letters to lowercase so that different capitalizations hash to the same value Your program should create hash tables of various sizes: 500, 2000, 5000 slots. The hash table should use a linked list in each slot to keep track of the words that hash to that slot. It should read each word in the novel, then search for or insert the word in the hash table based on the hash function: Math.abs(myString.hashcode()%tablesize) The program should use LinkedLists to store collisions. You do not need to write your own linked list. When adding an item to the list, use an Iterator or ListIterator to determine whether the word is already in the table. Doing this will enable you to keep track of the number of steps required to look up and add the word. Your program should keep track of the number of occurrences of each word, and the number of steps it took to find or insert the word. Number of steps is based on the position of the word in the linked list. If the word is first, it took 1 step to find. If the word is second, it took 2 steps to find, etc. The program should print a file that contains each word, the number of occurrences of that word, and the number of steps it took to find the word. Make the file a CSV so that you can read it in Excel. Use Excel to calculate statistics such as the total number of words, the total number of occurrences, total steps, and average steps per word. Make a chart that plots the average number of steps against the size of the hash table. In this project, only one algorithm is used, so there is no need for an interface, however, you must still use good object-orient design principles. You should create a class that holds a word, its number of occurrences, and the total number of steps to record those occurrences. You should create a second class that has the hash table as an instance variable, and contains a method to add items to the hash table. Your main() method should be in a third separate classStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started