I'm suppoed to insert each word from a text file (a "dictionary") into a Table ADT, and implement the Table ADT with a hash table.
I want to use a linked list with the Table ADT. So how would I go about this? I'm guessing I need to create the linked list (node) class, add all the words into the linked list... and then what? I understand hashing, but I just don't understand tables and how to implement them.
> It was not specified. However, knowning my prof and
> our previous assignments, I'm almost 100% certain
> that we need to write our own Hashtable class.
It's hard to advice you without knowing the exact requirements.
I mean, do you need to create your own class which mimics the behavior of some sort of map/table structure (a value connected to a unique key) or do you have to implement your own hash-table with certain operation performances normally asociated with a classic hash-table? If the latter is not the case, why call it a hash-table then?
And can you make use of the java.util.LinkedList or do you have to implement that class yourself too?
> We only need to create the Table ADT and insert data
> (words) into it. No other manipulations are needed.
> But I'm just lost as to how to do this. Do I insert
> the words into a linked list? If so, what am I
> supposed to do after I've inserted everything into a
> LL..
Ok, you're only mimicking the behavior.
Create a class named MyTable:public class MyTable {
private LinkedList words;
public MyTable() {
// your code
}
public void insert(String word) {
// your code
}
// other methods
}
This class holds, as you can see, a LinkedList which you will be filling with WordOccurrence objects. A WordOccurrence object will look like this:public class WordOccurrence {
private String word;
private int occurrence;
public WordOccurrence(String word) {
// your code
}
// the rest of your methods here
}
Before your insert something in your MyTable class, just check your LinkedList if the word is already in it, if it is, increate the occurrence with one.
Good luck.
> Ah I see. So I will have a Table class, and
> LinkedList class. The insert method in MyTable will
> insert a word into a specific position in the Linked
> List, right? And to determine which position to
> insert the word into the Linked List, I use a hash
> algorithm, right?
No. Just give every unique word a separate entry in your linked-list to create a table/map-like ADT.
If you want to learn how a hashtable works internally, I suggest reading a datastructures book or Google for a tutorial. That's not suitable to explain step by step on a public forum.
> I don't quite get how a Table differs from the LL.
> I've inserted the words into the LL, so how do I
> implement this LL into a Table ADT?
Here's a small start:public class MyTable {
private MyLinkedList words;
public MyTable() {
words = new MyLinkedList();
}
public void insert(String word) {
WordOccurrence newWord = new WordOccurrence(word);
if(words.contains(newWord)) { // If the word already exists in your word-list
WordOccurrence existingWord = ... // Get the reference of that existing word
existingWord.increase();// Increase the occurrence of the existing word
}
else { // The new word does not exist in your word-list yet
words.add(newWord);// Add it to your word-list
}
}
public static void main(String[] args) {
MyTable table = new MyTable();
table.insert("Dog");// this should trigger the else-statement in the insert() method
table.insert("House"); // this should trigger the else-statement in the insert() method as well
table.insert("Dog");// ! this should trigger the if-statement in the insert() method
}
}
Your table should now have a linked list which looks like this:+-++-+
| Dog || House |
|| --> || --> end of your list
|2||1|
+-++-+
> What is the WordOccurrence class that "gets the
> reference of that existing word"?
See reply 9 for the class.
Let's say you only added 1 Dog and after that 1 House .
The list in your table class now looks like this:+-++-+
| Dog || House |
|| --> || --> end of your list
|1||1|
+-++-+
The next time you want to add the word Dog, using your insert method, the contains-method from your list class will return true. This means there is already a word Dog in the list. So we want to get the object (the WordOccurrence object) which holds the word Dog and increase it's occurrence with 1. You should be able to get a certain node in your list with some sort of a get-method from your LinkedList class.
After that your list looks like this:+-++-+
| Dog || House |
|| --> || --> end of your list
|2||1|
+-++-+
This is the best I can explain things on a public forum (without just making your homework).
If you are still unable to make some progress, I suggest teaming up with some class mates and/or ask the prof for clarification.
Good luck.
