HashSets

[DavidG24]

hey guys,

just a very basic question, am I correct in stating that HashSets have the following features
(1) Are Not Indexed
(2) Can not be Sorted
(3) Do Not allow Duplicates

??

Cheers,

David

[Fubarable]

Those aren't limitations; they're features. There are many types of maps which I invite you to study, many which allow sorting and such.

[neilcoffey]

Well, I'd say hashing is a kind of indexing system-- I supposed it depends a bit on your definition.

The basic HashSet cannot be sorted in situ. But of course, it's easy to get the contents of the set sorted at the moment when you need that. For example:

HashSet<String> hs = ...
TreeSet<String> ts = new TreeSet<String>(hs);
for (String s : ts) {
  // pull out strings in sorted order
}

In case you've not come across it, a TreeSet is a type of set that keeps its elements sorted (you could also just have a TreeSet to start with). Or you could copy the contents of your set to a list and sort that:

List<String> l = new ArrayList<String>(hs);
Collections.sort(l);
for (String s : l) {
  // pull out strings in sorted order
}

[DavidG24]

[SOLVED]
Thanks Neil, Yeah I have explored all the concrete Set types, I'm learning collections from a textbook/online tuts and just wanted to make sure that I had my facts straight.
Just out of curiosity, and of course this depends on the application, would you say implementing a Sorting method on a LinkedHashSet would be more efficient then using a TreeSet, i.e. if the application only required you to Sort them at certain times (not every time an object is added) it would reduce the Memory and overall time for the application?

I only ask as the Java API specifies that both the HashSet and LinkedHashSet have constant time i.e. 0(n) for searching/removing etc (LinkedHashSet being slightly slower), however the TreeSet has O(log(n))
which are you would know,
O(log(n)) > 0(n) for all n.

[neilcoffey]

Yes, in general, if you need to sort rarely, then it can be better performance-wise to just do the occasional sort when you need it. However, where the "cut off point" for your particular application will obviously depend, and in such situations it's usually better to profile and find out if the sorting is actually causing you a problem.

Note that in some applications, reliable throughput is more important than raw speed. Consider a busy server that has various threads continually updating some map/structure that it occasionally needs to sort for logging/auditing purposes. With the sort-on-demand approach, you may have to lock the entire structure while you make the copy for sorting, and that may have an undesirable effect on the other threads that are continually updating that structure. With the sort-on-modification approach, you generally don't have to lock the entire structure during modifications, and pretty much don't have to lock the structure at all to read it in sorted order (since it's already sorted). In other words, it's sometimes better to have a structure that's slightly slower to access but doesn't have any operations that lock the entire structure (look at ConcurrentSkipListSet), than to have one with some very fast operations but occasional slow, blocking ones.

[DavidG24]

Neil,

Thanks again, I certainly see how it would definately be more useful for the situation you have posed.
Once again, thanks for your assistance.
Now I'm onto Lists!
David