CIS 256 (JAVA - DATA STRUCTURE) Programming Project 1 (Hash Tables) For this pro
ID: 3805120 • Letter: C
Question
CIS 256 (JAVA - DATA STRUCTURE)
Programming Project 1 (Hash Tables)
For this programming project, you will be implementing a spelling checker. The spelling checker will accept words from a dictionary and a document and then output the words in the document that are not in the dictionary. You should store the words in the dictionary in a hash table and your program should output statistics about the hash table’s performance. The instructions are as follows:
1. Implement the separate chaining HashTable template class. You should use your HashTable class to store the words (i.e. strings) in the dictionary. Use one the hash function explained in your textbook.
2. Add a new method to the HashTable class called printStats() that prints the minimum, maximum, and mean chain length for all the chains in the hash table.
3. Use included dictionary and document files
4. You may assume that the dictionary file always have the filename dictionary.txt and the document file always have the filename document.txt. 5. Save the dictionary and document files in the same directory as your executable code.
6. The dictionary file contains one word per line, and the first line will be the number of words in the file. The words are all in lowercase.
7. The document file contains lowercase words separated by spaces or new lines.
8. Your program should work with any dictionary and document files that comply with the above constraints.
9. Provide a main program. Your main program should do the following:
(a) Create a hash table whose size is equal to the number of words in the dictionary.
(b) Read the words from the dictionary and store each one in the hash table.
(c) Output the statistics (i.e. minimum, maximum, and mean chain length) of the hash table after all words in the dictionary has been stored in the hash table.
(d) Read the words from the document and output each word that is NOT in the dictionary.
The following are the additional instructions for this programming project:
This programming project is to be done individually.
Create a readme.txt le that describes exactly how to compile and execute your program.
Collect your source codes, readme le, and other les needed to compile and execute your program into one ZIP le called YourFirstName_YourLastName_prog3.zip. Please DO NOT include any executable les in your ZIP le.
Make sure you follow good object-oriented programming approach, good coding style, and proper documentation.
The grading for this programming project will be based not only on the correctness of the program, but also on the program’s overall design, coding style, and documentation.
-----------------------------------------------------------------------------------------------------
document.txt
emma woodhouse handsome clever and rich with a comfortable home
and happy disposition seemed to unite some of the best blessings
of existence and had lived nearly twenty one years in the world
with very little to distress or vex her
she was the youngest of the two daughters of a most affectionate
indulgent father and had in consequence of her sister's marriage
been mistress of his house from a very early period her mother
had died too long ago for her to have more than an indistinct
remembrance of her caresses and her place had been supplied
by an excellent woman as governess who had fallen little short
of a mother in affection
the wedding was very much like other weddings where the parties
have no taste for finery or parade and mrs elton from the
particulars detailed by her husband thought it all extremely shabby
and very inferior to her own very little white satin very few
lace veils a most pitiful business selina would stare when she
heard of it but in spite of these deficiencies the wishes
the hopes the confidence the predictions of the small band
of true friends who witnessed the ceremony were fully answered
in the perfect happiness of the union
-------------------------------------------------------------------------------------------------------------------
There is dictionary file as well but its too large to attach!
Explanation / Answer
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class SpellChecker {
private HashTable dictionary;
private List<String> document;
public static void main(String args[]) throws IOException {
new SpellChecker();
}
public SpellChecker() throws IOException {
readWordsIntoDict("/home/zubair/Desktop/dictionary.txt");
readWordsFromDocument("/home/zubair/Desktop/document.txt");
dictionary.printStats();
findOutMissingWords();
}
public void findOutMissingWords() {
List<String> missingWords = new ArrayList<>();
for (String word : document) {
if (!dictionary.doesExists(word)) {
missingWords.add(word);
}
}
System.out.println("Missing words are : [" + missingWords + "]");
}
public void readWordsFromDocument(String filePath) throws IOException {
BufferedReader bufferedInput = new BufferedReader(new FileReader(filePath));
document = new ArrayList<String>();
/*
* read each line from file and
* add every word in it to the existing list
*/
String inputLine;
inputLine = bufferedInput.readLine();
while ((inputLine = bufferedInput.readLine()) != null) {
String splittedString[] = inputLine.split("\s+");
for (String word : splittedString) {
document.add(word.trim());
}
}
bufferedInput.close();
}
public void readWordsIntoDict(String filePath) throws IOException {
List<String> resultList = new ArrayList<String>();
BufferedReader bufferedInput = new BufferedReader(new FileReader(filePath));
/*
* Read the words from the file into a list
*/
int numOfWords = Integer.parseInt(bufferedInput.readLine());
String inputLine;
for (int i=0; i<numOfWords; i++) {
if ((inputLine = bufferedInput.readLine()) != null) {
resultList.add(inputLine.trim());
}
}
bufferedInput.close();
/*
* Add the read words into a dictionary
*/
dictionary = new HashTable(numOfWords);
for (String word : resultList) {
dictionary.add(word);
}
}
}
class HashTable {
private Map<Integer, List<String>> hashTable = new HashMap<>();
private int capacity;
/**
* Initializing the hash table
*/
HashTable(int capacity) {
this.capacity = capacity;
for (int i=0; i<capacity; i++) {
hashTable.put(i, null);
}
}
/**
* Adds a given value to the hash table
*
* @param value
*/
public void add(String value) {
/*
* Compute Hash Key
* */
Integer hashKey = getHash(value);
List<String> chain = hashTable.get(hashKey);
if (chain == null) {
chain = new ArrayList<String>();
hashTable.put(hashKey, chain);
}
if (!chain.contains(value)) {
chain.add(value);
}
}
/**
* Returns whether a given word exists in the hash table
* @param value
* @return
*/
public boolean doesExists(String value) {
/*
* Compute Hash Key
* */
Integer hashKey = getHash(value);
/*
* See if the table contains the key, if yes, then parse
* the chain and see if the word exists
* */
if (hashTable.containsKey(hashKey)) {
List<String> chain = hashTable.get(hashKey);
if (chain == null) {
return false;
}
for (String word : chain) {
if (word.equalsIgnoreCase(value)) {
return true;
}
}
}
return false;
}
/**
* TODO : Use your own hash function implemention
*
*/
public Integer getHash(String value) {
int hashKey = 7;
for (int i = 0; i < value.length(); i++) {
hashKey = hashKey*31 + value.charAt(i);
}
return hashKey%capacity;
}
/**
* Prints the hash table statistics
* i.e., mean, max and min chain lengths
*/
public void printStats() {
System.out.println(System.lineSeparator());
System.out.println("Hash Table Statistics ");
System.out.println("Minimum Chain Length is : "+getMinChainLength());
System.out.println("Maximum Chain Length is : "+getMaxChainLength());
System.out.println("Average Chain Length is : "+getAverageChainLength());
System.out.println(System.lineSeparator());
}
private double getMinChainLength() {
double minLength = Double.MAX_VALUE;
for (Entry<Integer, List<String>> entry : hashTable.entrySet()) {
if (entry.getValue() != null && entry.getValue().size() < minLength) {
minLength = entry.getValue().size();
}
}
return minLength;
}
private double getMaxChainLength() {
double maxLength = Double.MIN_VALUE;
for (Entry<Integer, List<String>> entry : hashTable.entrySet()) {
if (entry.getValue() != null && entry.getValue().size() > maxLength) {
maxLength = entry.getValue().size();
}
}
return maxLength;
}
private double getAverageChainLength() {
double averageLength = 0.0;
for (Entry<Integer, List<String>> entry : hashTable.entrySet()) {
if (entry.getValue() != null) {
averageLength += entry.getValue().size();
}
}
if (capacity == 0) {
return -1;
}
return averageLength/capacity;
}
}