Write a Java program to demonstrate using hash tables. Doing more file processin
ID: 3532901 • Letter: W
Question
Write a Java program to demonstrate using hash tables. Doing more file processing, you will read in a dictionary file, dictionary.txt, and use its contents to spell check a file, checkme, that is provided on the command line.
This project is not an in-depth, comprehensive program in the nature of root words, tense, plurals or endings. Rather many words of varying form (plurals, possessives) will be provided in the dictionary file.
You will need to create two Java files: Project6.java and StringHash.java.
Given:
Create a StringHash class. Here is some code to get you started:
You will need to create a constructor and a Node inner-class similar to the Linked-List topic.
Create the following methods in a newly created StringHash class:
public boolean hasWord(String word);
public void add(String word);
Now create a Project class for testing the StringHash class. This class will also have your main() method. Use the following in the Project6 class:
Note: this is from the Short-Circuit discussion.
The remainder of this work should be done in the Project6 class.
Your input file will be given on the command line. The dictionary file should be hard coded as dictionary.txt.
Read the dictionary file into the hash table using the add() method. Use the hashValue() method to find the appropriate bucket for a given word. Once a bucket is found add the word to the list for that bucket. An ordered list is not needed here as a linear search of the bucket list should not be too expensive due to the hash.
*NOTE*: You must either lower case or upper case the words as they are entered into the hash table.
Lookups will be consistent later as hasWord() must do the same when you request a word lookup.
After the hash table is populated with the dictionary words, open the file to be spell checked and read words from the file one at a time. Check the word against the hash table using hasWord().
Display to standard output those words that are not spelled correctly or do not appear in the hash table. Your output should look like:
A few additional notes to make life easier:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class StringHash { Node[] buckets; private int BUCKETS; private int MULT; public int hashValue(String s) { int h; int x, l = s.length(); h = 0; for ( x =0; x < l; x++ ) h = h * MULT + s.charAt(x); if ( h < 0 ) h = -h; return (h % BUCKETS); }
Explanation / Answer
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.io.StreamTokenizer;
public class Project6
{
static StringHash obj;
public static void main(String args[])
{
obj=new StringHash();
try
{
FileReader fr=new FileReader("dictionary.txt");
BufferedReader br=new BufferedReader(fr);
String word;
while((word=br.readLine())!=null)
{
word=Project6.removeNonLetDig(word);
obj.add(word);
}
br.close();
fr.close();
}catch(FileNotFoundException ex)
{
ex.printStackTrace();
}
catch(IOException ex)
{
ex.printStackTrace();
}
try
{
FileReader fr=new FileReader(args[0]);
BufferedReader br=new BufferedReader(fr);
String line;
String word[];
while((line=br.readLine())!=null)
{
word=line.split(" ");
for(int i=0;i<word.length;i++)
{
if(!obj.hasWord(word[i]))
System.out.println(word[i]);
}
}
// Project6.wReader(fr);
}catch(FileNotFoundException ex)
{
ex.printStackTrace();
}
catch(IOException ex)
{
ex.printStackTrace();
}
}
public static String removeNonLetDig(String s)
{
int b = 0, e = s.length()-1;
// Trim from the beginning
while (b <= e && !Character.isLetterOrDigit(s.charAt(b)))
b++;
// Trim from the end
while (e >= b && !Character.isLetterOrDigit(s.charAt(e)))
e--;
if (b <= e)
return s.substring(b,e + 1);
else
return null;
}
}
class StringHash
{
class Node
{
String word;
Node next;
Node()
{
word="";
next=null;
}
Node( String word,Node next)
{
this.word=word;
this.next=next;
}
public void setWord(String word)
{
this.word=word;
}
public void setNext(Node next)
{
this.next=next;
}
public String getWord()
{
return word;
}
public Node getNext()
{
return next;
}
}
Node[] buckets;
private int BUCKETS;
private int MULT;
StringHash()
{
MULT= 31;
BUCKETS=4093;
buckets=new Node[BUCKETS];
for(int i=0;i<4093;i++)
buckets[i]=null;
}
public int hashValue(String s)
{
int h;
int x, l = s.length();
h = 0;
for ( x =0; x < l; x++ )
h = h * MULT + s.charAt(x);
if ( h < 0 )
h = -h;
return (h % BUCKETS);
}
public void add(String word)
{
int hValue=hashValue(word);
Node temp=buckets[hValue];
if(temp==null)
{
temp=new Node(word,null);
buckets[hValue]=temp;
}
else
{
while(temp.next!=null)
temp=temp.next;
temp.next=new Node(word,null);
}
}
public boolean hasWord(String word)
{
int hValue=hashValue(word);
Node temp=buckets[hValue];
while(temp!=null)
{
if(temp.word.equalsIgnoreCase(word))
return true;
temp=temp.next;
}
return false;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.