convert linked list to Hash table


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 8 of 8

Thread: convert linked list to Hash table

Hybrid View

  1. #1
    Join Date
    Oct 2005
    Posts
    1

    convert linked list to Hash table

    Hi, can someone help me? I have a program that uses Linked List data structure, and I want to convert it to Hash table. Its a very basic java program I created. can anyone help?

  2. #2
    Join Date
    Jul 2005
    Location
    SW MO, USA
    Posts
    299
    First question is: What is the key and what is the value of an entry in the Linked List? You'll need to define these to put the list into a hashtable.

    Then look at the Hashtable methods such as put and get.

  3. #3
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You would accomplish this by walking through your list, run your hash function on the item in the node, place it in your table, and then move to the next node in your list. You then can work from your hash table to do any of your look-ups ...

    Have you determined your hash function? Do you know the size of your table? Have you decided on your procedure for handling collisions?

  4. #4
    Join Date
    Oct 2005
    Posts
    40
    Quote Originally Posted by fscdta05
    Hi, can someone help me? I have a program that uses Linked List data structure, and I want to convert it to Hash table. Its a very basic java program I created. can anyone help?
    Hi,

    Two things,

    1) It will be helpful if you can post your program here and more importantly
    2) What benefit are you getting by making this conversion?

    Regards,
    Mohit

  5. #5
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    It's not my program, but ...

    Other than being a programming exercise, there are benefits you have to using a linked list to just store stuff (ArrayList) because all you're doing is adding an item at the end or the front or wherever your "add" iterator may be when you aren't sorting, and for all of its easy way to address by index, etc., and drawbacks to using a linked list, such as searching and retrieval, for which it is very slow. Therefore, why not use a linked list for the "collection building" and "holding" phase of your program, then transfer the information to a hash table when you switch over to a find and retrieve phase of the program [since building a hash table is relatively time consuming and expensive, you don't want to do it unless you need to and as infrequently as necessary].

  6. #6
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560
    Just a note: If the objects stored in a collection that implements the List interface
    implement the boolean equals(Object ob) method you can do lookups using the
    int indexOf(Object ob) method defined for List. I haven't clocked it though, for
    comparing the retrieval speed to a Hashtable but I recon you will
    need a rather monstrous collection to detect any difference (if any).
    eschew obfuscation

  7. #7
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You know the "big O" of lookups in these two structures: the theoretical "close to 1" for a Hashtable which is appropriately designed with very few collisions, while for lookups in a linked list structure it is "n" - the number of elements in the list. But I expect that your practical evalaution is what we see ... there isn't much difference.

  8. #8
    Join Date
    Nov 2004
    Location
    Norway
    Posts
    1,560
    I mean, if you plan to store list elements in a hashtable and not loose any of them,
    then you must rule out the possibility of duplicate keys. So, if you don't want the
    hashtable to overwrite entries, ending up with fewer elements in the hashtable than in
    the list, you must design it so no element in the list equals another.

    As for speed, I tested an array of 10,000,000 elements, containing random
    integers in the range 1-2000. The process of finding the most frequent integer value
    (using a hashtable) took appr. 0.015 sec.

    What I mean is that the discussion of execution speed is purely an academical one, if
    the problem doesn't involve intense processing of huge collections, like for
    seismic processing (in Schlumberger we used a connection machine for that).
    eschew obfuscation

Similar Threads

  1. Replies: 2
    Last Post: 08-23-2002, 05:22 AM
  2. Linked dBase Table in Access2000
    By Jeff Moore in forum VB Classic
    Replies: 2
    Last Post: 06-06-2002, 07:44 PM
  3. Replies: 1
    Last Post: 11-18-2001, 10:32 PM
  4. List Table and Field names of database
    By julie in forum VB Classic
    Replies: 4
    Last Post: 11-17-2000, 09:28 AM
  5. Multi-row calculations
    By Bob Hines in forum Database
    Replies: 7
    Last Post: 04-27-2000, 12:14 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center