Results 1 to 6 of 6

Thread: HashSets

  1. #1
    DavidG24 is offline Member
    Join Date
    Apr 2009
    Posts
    49
    Rep Power
    0

    Default HashSets

    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
    Last edited by DavidG24; 04-19-2009 at 04:10 PM.

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    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.

  3. #3
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    6

    Default

    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:

    Java Code:
    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:

    Java Code:
    List<String> l = new ArrayList<String>(hs);
    Collections.sort(l);
    for (String s : l) {
      // pull out strings in sorted order
    }
    Last edited by neilcoffey; 04-19-2009 at 05:59 PM. Reason: added exp of TreeSet

  4. #4
    DavidG24 is offline Member
    Join Date
    Apr 2009
    Posts
    49
    Rep Power
    0

    Default

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

  5. #5
    neilcoffey is offline Senior Member
    Join Date
    Nov 2008
    Posts
    286
    Rep Power
    6

    Default

    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.

  6. #6
    DavidG24 is offline Member
    Join Date
    Apr 2009
    Posts
    49
    Rep Power
    0

    Default

    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

Similar Threads

  1. how does the remove method work for sets and hashsets
    By haridharna in forum Advanced Java
    Replies: 4
    Last Post: 08-06-2007, 01:48 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
  •