convert linked list to Hash table

[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?

[Norm]

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.

[nspils]

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?

[mohit]

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

[nspils]

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].

[sjalle]

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).

[nspils]

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.

[sjalle]

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).