Maximizing efficiency with sets and lists

[salmontres]

Hi guys,

I want to store objects in a collection with very fast lookups but that maintains some sort of queue order. (Theoretically, I may be storing about 300 million members in the collection.) I read into the LinkedHashSet in Java, but I didn't know if in creating the double linked list for the structure, performance would suffer.

Have you guys used the LinkedHashSet? Is it much slower than the HashSet in lookups? If it is, would it be easier to create to objects (a HashSet and a LinkedList) to store my information?

Last question, how do I mark a thread as solved? I've received great help from some of my other questions, I leave reputation marks, but I don't see any way to close or mark the thread as solved.

[doWhile]

I would recommend reviewing the API which might answer your questions more thoroughly
LinkedHashSet (Java Platform SE 6)

Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list

I would presume the last sentence refers to the add/remove (and other) methods, but doesn't apply to the contains method which should be independent of the internal LinkedList (and in fact, LinkedHashSet extends HashSet and doesn't override the contains method)

[salmontres]

You're correct on all points, doWhile. This is the exact information I was looking for. Thanks!

Another question came up, which I couldn't find in the reading. Although the LinkedHashSet has predictable ordering, I couldn't find a method which simply lets me remove the last element. Right now, I'm iterating through the entire list with an iterator, and when (iter.hasNext() == false), I simply do iter.remove(). (Which takes care of the last element.)

Did I miss something? How can I remove the last element of the set, without knowing explicitly the last element, nor iterating through the entire list every time? (If possible.)