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

[Harald Kirsch]

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().

 

[Michael Borgwardt]

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.

 

[Paul Lutus]

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.

 

[Eric Sosman]

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.

 

[Harald Kirsch]

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.