Hash Tables

In class we implemented a hash table for a set, with the buckets consisting of linked chains of nodes. Add the following method to the file:

boolean remove (T item);

Then test your code using HashSets. The output should look like this:

0 c Q

1 I m

2 e

3 f

4 C y U

5 z D V

6 E i W

7 j F

8 b P

Does the set contain 'e'? yes

Does the set contain 'a'? no

After removing e, c, y, W, and y:

0 Q

1 I m

2

3 f

4 C U

5 z D V

6 E i

7 j F

8 b P

/* * interface for a set * * unordered collection, no duplicates allowed */ public interface Set { /* * adds item to set if not already present * * returns true if item successfully added, false if not * */ boolean add (T item); T remove(); boolean remove (T item); T get(); boolean contains (T item); int size(); String toString(); } 

/* * driver program for testing LinkedHashSet */ public class HashSets { public static void main (String [] args) { Set letters = new HashSet< >(); char [] toAdd = {'C', 'b', 'c', 'Q', 'z', 'D', 'E', 'P', 'j', 'F', 'E', 'I', 'y', 'f', 'i', 'U', 'V', 'm', 'e', 'W'}; for (int i = 0; i < toAdd.length; i++) { letters.add(toAdd[i]); } System.out.println(" " + letters); System.out.println("Does the set contain 'e'? " + (letters.contains('e') ? "yes" : "no")); System.out.println("Does the set contain 'a'? " + (letters.contains('a') ? "yes" : "no")); System.out.println("After removing e, c, y, W, and y: "); letters.remove('e'); letters.remove('c'); letters.remove('y'); letters.remove('W'); letters.remove('y'); System.out.println(letters); } } 

/* * implements a hash table using chains of nodes for the buckets */ public class HashSet implements Set { private class Node { private T data; private Node next; public Node(T item) { data = item; next = null; } public String toString() { return "" + data; } } public static final int DEFAULT_CAPACITY = 9; private Node[] hashtable; private int size; private int items; public HashSet () { this(DEFAULT_CAPACITY); } @SuppressWarnings("unchecked") public HashSet (int capacity) { hashtable = (Node[]) new HashSet.Node[capacity]; size = capacity; items = 0; } public boolean add (T item) { checkForNull(item); int index = getIndex(item); Node current = hashtable[index]; if (current == null) { hashtable[index] = new Node(item); items++; return true; } while (current.next!= null) { if (current.data.equals(item)) { return false; } current = current.next; } if (current.data.equals(item)) { return false; } current.next = new Node(item); items++; return true; } public boolean remove (T item) { // to be implemented return false; } public T remove () { return null; } public T get() { boolean filled = false; int random = 0; while (!filled) { random = (int)(Math.random() * items); if (hashtable[random] != null) { filled = true; } } return hashtable[random].data; } public boolean contains(T item) { int index = getIndex(item); Node current = hashtable[index]; if (current == null) { return false; } while (current.next != null) { if (current.data.equals(item)) { return true; } current = current.next; } if (current.data.equals(item)) { return true; } return false; } public int size() { return size; } public String toString() { if (size == 0) { return "[]"; } String h = ""; for (int i = 0; i < size; i++) { Node current = hashtable[i]; if (current == null) h+= i + "\t" + " " + " "; else { h+= i + "\t" + current + " "; while (current.next != null) { current = current.next; h+= current + " "; } h+= " "; } } return h; } private void checkForNull(T item) { if (item == null) { throw new IllegalArgumentException("null not a possible value!"); } } private int getIndex(T item) { int index = item.hashCode() % size; if (index < 0) { index += size; } return index; } } 

Next, revise your implementation of Seuss.java so that instead of using a list-based set, it uses a hash set. Call the new file Seuss3, and use a hash set of size 20 to store the words. Your output should look like this:

0 ham them here car me

1 the

2 eggs tree

17 a may if

18 dark

19 you green box be

Finally write a program Spell.java that generates a list of misspelled words for a given text. To do this, create a hash set with 1000 buckets, and load the words from dictionary.txt (dictionary text file containing all words in english language, which is too big to include in this post) into it. Then check each word in the file test.txt against it. Any word not in the dictionary should be considered misspelled and written to the output file, misspelled.txt. Your program should return the following results:

noow

broawn

sdog

//smalldictionary.txt

aid all brown come dog for fox good is jumps lazy men now of over party quick the time to 

//test.txt

Noow is the time for all good men to come to the aid of the party. The quick broawn fox jumps over the lazy sdog!!!! 

As with the Seuss programs (using the text from Green Eggs and Ham), you will want to remove punctuation and capitalization before checking if a word is in the dictionary.

//greenEggs.txt

I am Sam I am Sam Sam I am

That Sam I am! That Sam I am! I do not like that Sam I am!

Do you like green eggs and ham?

I do not like them, Sam I am. I do not like green eggs and ham.

Would you like them here or there?

I would not like them here or there. I would not like them anywhere. I do not like green eggs and ham. I do not like them, Sam I am.

Would you like them in a house? Would you like them with a mouse?

I do not like them in a house. I do not like them with a mouse. I do not like them here or there. I do not like them anywhere. I do not like green eggs and ham. I do not like them, Sam I am.

Would you eat them in a box? Would you eat them with a fox?

Not in a box. Not with a fox. Not in a house. Not with a mouse. I would not eat them here or there. I would not eat them anywhere. I would not eat green eggs and ham. I do not like them, Sam I am.

Would you? Could you? In a car? Eat them! Eat them! Here they are.

I would not, could not, in a car.

You may like them. You will see. You may like them in a tree!

I would not, could not in a tree. Not in a car! You let me be!

I do not like them in a box. I do not like them with a fox. I do not like them in a house. I do not like them with a mouse. I do not like them here or there. I do not like them anywhere. I do not like green eggs and ham. I do not like them, Sam I am.

A train! A train! A train! A train! Could you, would you, on a train?

Not on a train! Not in a tree! Not in a car! Sam! Let me be!

I would not, could not, in a box. I could not, would not, with a fox. I will not eat them with a mouse. I will not eat them in a house. i will not eat them here or there. I will not eat them anywhere. I do not eat green eggs and ham. I do not like them, Sam I am.

Say! In the dark? Here in the dark! Would you, could you, in the dark?

I would not, could not, in the dark.

Would you, could you, in the rain?

I would not, could not, in the rain. Not in the dark. Not on a train. Not in a car. Not in a tree. I do not like them, Sam, you see. Not in a house. Not in a box. Not with a mouse. Not with a fox. I will not eat them here or there. I do not like them anywhere!

You do not like green eggs and ham?

I do not like them, Sam I am.

Could you, would you with a goat?

I would not, could not, with a goat!

Would you, could you, on a boat?

I could not, would not, on a boat. I will not, will not, with a goat. I will not eat them in the rain. I will not eat them on a train. Not in the dark! Not in a tree! Not in a car! You let me be! I do not like them in a box. I do not like them with a fox. I will not eat them in a house. I do not like them with a mouse. I do not like them here or there. I do not like them ANYWHERE

I do not like green eggs and ham!

I do not like them, Sam I am.

You do not like them. So you say. Try them! Try them! And you may. Try them and you may, I say.

Sam! If you will let me be, I will try them. You will see.

Say! I like green eggs and ham! I do! I like them, Sam I am! And I would eat them in a boat. And I would eat them with a goat...

And I will eat them in the rain. And in the dark. And on a train. And in a car. And in a tree. They are so good, so good, you see!

So I will eat them in a box. And I will eat them with a fox. And I will eat them in a house. And I will eat them with a mouse. And I will eat them here and there. Say! I will eat them ANYWHERE!

I do so like green eggs and ham! Thank you! Thank you, Sam I am!

//HashSet implementation of the following code, this code is from a Map implementation

import java.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

public class Suess2 {

// returns a string retaining only characters and converting to lower case

// all punctuation are removed

public static String removePunc(String s) {

String result = "";

s = s.toLowerCase();

for (int i = 0; i < s.length(); i++) {

char ch = s.charAt(i);

if (isLetter(ch))

result += ch;

}

return result;

}

public static boolean isLetter(char ch) {

if (ch >= 'a' && ch <= 'z')

return true;

else if (ch >= 'A' && ch <= 'Z')

return true;

else

return false;

}

public static void main(String[] args) {

String filename = "greenEggs.txt";

try {

Scanner inFile = new Scanner(new File(filename));

String word;

Map map = new HashMap();

while (inFile.hasNext()) {

word = inFile.next();

word = removePunc(word);

if (map.containsKey(word))

{

int value = map.get(word).intValue();

map.put(word, value + 1);

}

else

map.put(word, 1);

}

inFile.close();

// write the set contents to a file

PrintWriter pw = new PrintWriter(new File("words.txt"));

pw.write(map.toString());

pw.close();

System.out.println("Saved the words in map to file words.txt ");

System.out.println(map.toString());

} catch (FileNotFoundException e) {

System.out.println(e.getMessage());

}

}

}

If you need to debug your program, use smallDictionary.txt (above), which contains just the twenty words in the test.txt (above) file, change the hash table size to 5, and print it out so that you can see what it looks like internally