[liquidlithium_R]

no code necessary, i just need the general idea, i was thinking i could just keep track of the data going into the hash table via a linked list, but i was wondering if that would be counter productive or not

[salindor]

Not the most effecient code, but hashtable has an getElements() method. Can't remmeber off the top of my head, but I am sure you can look at the api in www.javasoft.com

Then you can store it in an array, and java has a sort method. using the Arrays class.

This post has been edited by salindor: 16 November 2006 - 07:14 PM

[liquidlithium_R]

thanks, but what i forgot to say was that i am using java bot i am not using any of its included packages, all the code i am writing myself so i wanted to find out if there was some method that i can use to either sort the elements of a hash table(also wrote my own hash table code, using an array), if not then would keeping track of the data in a linked list be efficient or would there be a better way

[William_Wilson]

linked list is not likely the best way, to be honest an array is implemented (or atleast it was) by a linked list anyway.

i believe the best way would be to allow all types of objets and provide an iterface which requires a method to be overriden which determines the comparative order of 2 or more items. Then your sorting code would only need to rely on this code being correct. Which would be implemented on a case by case basis, pending the objects stored in the hash table.

[liquidlithium_R]

i dont quite understand exactly what you're saying, is it that basically the data should be inserted in the hash table in sorted order ,,,but that would over complicate the hash function and searching the hash table would be impossible, that is if that is what you're saying...ps i aint no expert, still learning to program, currently learning data structures,, llists, heaps, graphs etc.

[salindor]

Not exactly sure why java would implement an array as a linkedlist (and if it is true, that would cause some major speed degradation with all the memory jumps, something interesting to look up in the future) but, anyhow...

I didn't realize you were creating your own class structure.

This simplist method then would proably look like this (looks alot like my original suggestion):

//fist write a sorting routine, so you can use it later

Object ret[] = new ret[size];
//fill out array with all elements in hash table
//run quicksort or mergesort on array

this is a routine for how information on the quicksort, which I was told in general is the fastest sorting routine avaible.
http://en.wikipedia.org/wiki/Quicksort

if for some reason you implemented using a linkedlist, or linkedlists are easier for you, then the following might be recommended (merge sort). In general slower than quicksort, but there are cases where it is faster
http://en.wikipedia....wiki/Merge_sort

don't forget to implement the comparable interface, then you can ensure it even makes sense to sort the objects your trying to compare.

[salindor]

William_Wilson, on 16 Nov, 2006 - 07:41 PM, said:

linked list is not likely the best way, to be honest an array is implemented (or atleast it was) by a linked list anyway.

i believe the best way would be to allow all types of objets and provide an iterface which requires a method to be overriden which determines the comparative order of 2 or more items. Then your sorting code would only need to rely on this code being correct. Which would be implemented on a case by case basis, pending the objects stored in the hash table.

Ahhh, walk away from the computer then understand what you are saying.

Linkedlist have the properties that you can insert or remove elements for 'free' but have increased search time. So wilson was suggestion, that if you implement your hashtable as a linkedlist, then you could easily autosort it based on the comparable interface.

However, if you choose to implement it in this fashion, there is no point to a hashtable, as the whole point of a hashtable is a lookup time of 1 (supposing there are no hash collisions).

Also, it should be noted that there are different implementations of java. I have personally used two, sun's and jrocket.

Performing a quick comparision between linkedlists and arrays, arrays are definetly faster, on creating arrays and linkedlists of the size 2^21 in size, arrays are about 8-9 times faster in creation time.
Take timestamp,
create a linkedlist of appropriate size with a unique object in each postion,
set linkedlist variable to null
run garbage collection,
take timestamp
create array of appropraite size
fill out every value with teh same unique object set
set array to null
run garbage collection
take timestamp

of course I didn't do a random access test, which is where arrays really beat the crap out of linkedlist.

[liquidlithium_R]

thanks, u've been very helpful, i think i've got it now, thanks alot