HashTable/LinkedList question

[vtsmokey88]

The program is suppose to run through a list of strings. The stings are then put through a hash function (which works fine) and then "hashed" (for lack of a better word). The index is suppose to be an array of linked Lists to handle collision problems.

I guess the first question is, what is suppose to be the keys and values? Is the hash function output the keys, or the indexes in the array list; same goes for values. (I've looked through forums and tutorials but nothing really worked)

My understanding is that the output from the function is put in the index of the output modulo the size of the list. H(input) = output, then LinkedList[output] = output...but I'm confused if the hashtable should be hash.put(linkedList[output], output) or some other variation.

Basically, I'm just not sure how to connect the dots between needing the linked list for collisions and hashtable for the keys and values.

My Driver Class:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.*;
public class Driver {

	private Hashtable<LinkedList<?>, Integer> hash;
	private File fFile;
	private LinkedList[] list; 
	private int count;  
	
	public Driver(String info){
		hash = new Hashtable<LinkedList<?>, Integer>();
		fFile = new File(info);
	}
	
	public static void main(String[] args) throws IOException {
		Driver d = new Driver("WordData.txt");
		d.processLineByLine();
	}
	
	public final void processLineByLine() throws FileNotFoundException {
		Scanner scanner = new Scanner(fFile);
		list = new LinkedList[222888];
		for(int i =0; i < llist.length; i++){
			list[i] = new LinkedList();
		}
		try {
			//first use a Scanner to get each line
			while (scanner.hasNextLine()) {
				String s = scanner.nextLine();
				int index = (int) (Hasher.sum(s) % 222888);
				
				hash.put(list[(int) Hasher.sum(s)], index);
				System.out.println(hash.keySet() + "\t" + index);
			}
		}
		finally {
			//ensure the underlying stream is always closed
			scanner.close();
		}		
	}	
}

As you can see I'm kinda confused about what should go into the hashtable. Everything else in the program works and does what it's suppose to. I just need help with this part.

The output right now is
[] 673
[] 1123
[] 689

The brackets being what l[(int)Hasher.sum(s)] produces and the numbers being what index produces. Also, Hasher is an outside class that has all my working hash functions.

Any help would be appreciated.

[BestJewSinceJC]

http://en.wikipedia.org/wiki/Hash_table

The linked list is only needed because if the hash function maps multiple keys to the same index, and you don't have some mechanism for letting two things go there, you're screwed.

After you read the wikipedia page above, you'll have a decent idea of what is going on, I think. If not, after you read that link, try to follow this example of why I used a hash table in a project:

I wanted to implement a tic tac toe game where the computer at first guessed randomly, but then got smarter and smarter the more times it played. Obviously, then, it needs some way to remember what its good moves are and what its bad moves are. So I created a few things:

1) A "snapshot" which consisted of a picture of what the board looked like on a particular turn, and whether the computer won or lost that game. This snapshot basically consisted of a series of X, O, and _ for each square of the board. As you can see, that makes my keys unique, because each turn has a different representation of X's and O's and _'s. My Snapshot Object also contained the # wins, # losses, and # ties that resulted after that Snapshot.

2. A hash function that took my snapshot sequence of X's O's and _'s and converted that to an index within a reasonable range. Then, I stored the Snapshot in the hash table.

So as I hope you see, what I was doing was actually useful because I was (after each turn during the game) looking at the board, generating a Snapshot, then using the hash function to generate an index and see if I had ever seen this particular game board before. If I hadn't seen it before, I'd add it to the hash table. Otherwise, after the game, I'd update the wins/losses/ties associated with each snapshot in the hash table (that I saw again that game).

So basically, my keys were the XOXOXO_XO (which was always a string 9 long because there's 9 tic tac toe squares). My values were the Snapshots themselves, which held extra information about the game board other than what piece were on it. (The extra info it held, among other things, was the wins/losses/ties).

So hopefully that example helps you to see why a hash table can be useful. In your case if you want to hash "John Smith" and then unhash "John Smith" later, I really don't see how that helps you at all.

[BestJewSinceJC]

Sorry, that was probably too complicated...

As another example, lets say you have an Address Book. The address book, for each entry, contains the person's name, their phone number, and their other information. Now you could use their name as the key and their Address Book entry as the value. So any time you want to know what John Smith's phone number is, you can look it up quickly by hashing John Smith, going to that index of the hash table, and checking for his address book entry.

[vtsmokey88]

I get that I need to put the keys and values into the hash table but I'm wondering how it looks.

I have a long list of strings(the strings are words in a dictionary)

My hash function takes each string and adds the ascii values into a number.

The linked list is suppose to handle the numbers that repeat since it means there was a collision.

I, then, have to add up how many linked lists have each number of collisions(2 in the linked list means there was one collision, I assume).

So, from the example provided, I get that the Strings are the keys, and the hashfunction output is the values. But where does the linkedList come in. The way I have in the code wont let me set anything into an index unless it's of type linkedList. So, list[some output value] = output value. Say's that it's expecting type linkedlist, and i couldn't cast it to accept that.

[vtsmokey88]

would a LinkedHashMap from the java standard library work better then trying to implement a separate linked list from the hashtable?

[yokartik]

Regarding the BestJew's implementation;

You are saying that you stored the "snapshot" of the board after each turn along with the wins,loses and ties values. My question is let's say you are at
- - x
0 - -
x - - this turn.
Now how are you going to store this one, you do not have any win and lose values since you are not done with the game yet. At this point how will the computer determine which move to make?