This discussion is archived
1 2 Previous Next 19 Replies Latest reply: Oct 28, 2012 6:09 PM by EJP RSS

Table ADT with a Hash Table

807599 Newbie
Currently Being Moderated
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.
  • 1. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    You don't need a LinkedList, only the Hashtable will do.
    Have a look at the API docs of the Hashtable:
    http://java.sun.com/j2se/1.5.0/docs/api/java/util/Hashtable.html
    There's even s code example there how to use a Hashtable.

    Good luck.
  • 2. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    In class we learnt that a Table ADT is implemented using an array, tree or linked list...
  • 3. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    In class we learnt that a Table ADT is implemented
    using an array, tree or linked list...
    Do you have to write your own Hashtable class, or can you use the one from the java.util package?
  • 4. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    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.
  • 5. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    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?
  • 6. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    We have always implemented our own Linked list class. We have never really used any of the built-in Java Classes.
  • 7. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    We have always implemented our own Linked list class.
    We have never really used any of the built-in Java
    Classes.
    Ok, that answers my third question...
  • 8. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    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..
  • 9. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    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.
  • 10. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    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?
  • 11. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    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.
  • 12. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    I appreciate your help. It's got me going in the right direction.
  • 13. Re: Table ADT with a Hash Table
    800282 Newbie
    Currently Being Moderated
    I appreciate your help. It's got me going in the
    right direction.
    You're welcome.
    If you run into problems implementing it, post back here.
  • 14. Re: Table ADT with a Hash Table
    807599 Newbie
    Currently Being Moderated
    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?
1 2 Previous Next