java.lang.Set with elements of type java.lang.Set

Discussion in 'Java' started by Harald Kirsch, Aug 26, 2004.

  1. Roughly I do something along the lines of:

    Set set = new HashSet();
    Set elem = new HashSet();
    set.add(elem);

    // now we change the elem and add it again to the set
    elem.add(some object here);
    set.add(elem);

    I found out the hard way that 'set' may now contain
    'elem' either once or twice, the reason being that
    'elem.add()' changes the hashCode of elem such that
    it is not noticed that it is in 'set' already on the
    2nd 'set.add()'.

    Question: What I would actually want is an

    IdentityHashSet() set = new IdentityHashSet()

    but this does not seem to exist (what a shame). Any
    idea how to get the required effect with minimal coding?
    Would it be worth to define the element type myself as
    a subclass of HashSet, overriding the hashCode() with
    System.identityHashCode()?


    Comments?
    Harald.

    Remark: I am obviously using HashSet in the wrong way, but
    on the other hand, the behaviour is a bit dubios. Alas I
    would not know how to improve the HashSet implementation
    without forcing an equals() on every element during .add().
     
    Harald Kirsch, Aug 26, 2004
    #1
    1. Advertising

  2. Harald Kirsch wrote:
    > Question: What I would actually want is an
    >
    > IdentityHashSet() set = new IdentityHashSet()
    >
    > but this does not seem to exist (what a shame). Any
    > idea how to get the required effect with minimal coding?


    Use for the outer Set an IdentityHashMap with null values.

    HashSet is just a thin wrapper around a regular
    HashMap either, to hide the values.
     
    Michael Borgwardt, Aug 26, 2004
    #2
    1. Advertising

  3. Harald Kirsch

    Paul Lutus Guest

    Harald Kirsch wrote:

    > Roughly I do something along the lines of:
    >
    > Set set = new HashSet();
    > Set elem = new HashSet();
    > set.add(elem);
    >
    > // now we change the elem and add it again to the set
    > elem.add(some object here);
    > set.add(elem);
    >
    > I found out the hard way that 'set' may now contain
    > 'elem' either once or twice, the reason being that
    > 'elem.add()' changes the hashCode of elem such that
    > it is not noticed that it is in 'set' already on the
    > 2nd 'set.add()'.


    The problem is that you are adding the same object twice. This prevents a
    valid hashcode from being generated. You need to create a new object, and
    add that.
    >
    > Question: What I would actually want is an
    >
    > IdentityHashSet() set = new IdentityHashSet()


    What you want to do is clone the original object, make the desired change to
    the clone, than add the clone to the set. You may have to explicitly clone
    the object by copying all its contents, or there may be some more efficient
    way. But the success of the clone operation will be signaled by the fact
    (among others) that the clone is distinct from the original in the set you
    add it to.


    BTW, why are you trying to do this? There may be a more efficient way to
    accomplish your goal.

    --
    Paul Lutus
    http://www.arachnoid.com
     
    Paul Lutus, Aug 26, 2004
    #3
  4. Harald Kirsch

    Eric Sosman Guest

    Harald Kirsch wrote:
    > Roughly I do something along the lines of:
    >
    > Set set = new HashSet();
    > Set elem = new HashSet();
    > set.add(elem);
    >
    > // now we change the elem and add it again to the set
    > elem.add(some object here);
    > set.add(elem);
    > [...]
    > Comments?


    In addition to what others have mentioned, let me
    draw your attention to this warning from the Javadoc
    for the Set interface:

    "Note: Great care must be exercised if mutable
    objects are used as set elements. The behavior
    of a set is not specified if the value of an
    object is changed in a manner that affects equals
    comparisons while the object is an element in the
    set. [...]"

    In short, your trouble begins at elem.add(), because
    it changes the value of `elem' while `elem' is contained
    in `set'. Once `elem' has changed, `set' can no longer
    be relied upon to do anything sensible, whether or not
    you attempt to add `elem' a second time.

    --
     
    Eric Sosman, Aug 26, 2004
    #4
  5. Eric Sosman <> wrote in message news:<>...
    > Harald Kirsch wrote:
    > > Roughly I do something along the lines of:
    > >
    > > Set set = new HashSet();
    > > Set elem = new HashSet();
    > > set.add(elem);
    > >
    > > // now we change the elem and add it again to the set
    > > elem.add(some object here);
    > > set.add(elem);
    > > [...]
    > > Comments?

    >
    > In addition to what others have mentioned, let me
    > draw your attention to this warning from the Javadoc
    > for the Set interface:
    >
    > "Note: Great care must be exercised if mutable
    > objects are used as set elements. The behavior
    > of a set is not specified if the value of an
    > object is changed in a manner that affects equals
    > comparisons while the object is an element in the
    > set. [...]"


    Thanks for pointing this out. In a way I was looking for
    such a comment, because it seems to be inevitable. I guess
    I missed it in the Set docs since I thought it would
    be a problem of the implementation. Thinking about it,
    I realize that an implementation which does not have
    this "problem" would be very slow, being forced to
    probe all its elements on insertions and deletions.

    Harald.
     
    Harald Kirsch, Aug 31, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page