f



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

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().
0
pifpafpuf (198)
8/26/2004 3:44:14 PM
comp.lang.java.programmer 52714 articles. 1 followers. Post Follow

4 Replies
1724 Views

Similar Articles

[PageSpeed] 9

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.
0
brazil (1213)
8/26/2004 3:51:00 PM
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

0
nospam248 (2592)
8/26/2004 4:18:13 PM
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@sun.com

0
Eric.Sosman (4552)
8/26/2004 6:34:33 PM
Eric Sosman <Eric.Sosman@sun.com> wrote in message news:<412E2D39.1090608@sun.com>...
> 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.
0
pifpafpuf (198)
8/31/2004 10:40:36 AM
Reply: