A hash set puzzler

[d0ngd0ng]

An interesting problem at here http://www.jroller.com/eu/entry/a_hash_set_puzzler.

I it's impossible to 'get bar instance from the original HashSet
collection without iterating trough all elements'.

Anynoe have a good solution for it?

Thanks.

 

[Andrew Thompson]

d0ngd0ng wrote:
...

Anynoe have a good solution for it?

You say that 'like you are a programmer'.

Why not prove that by providing your 'bad' solution
in the form of an SSCCE*. I am quite confident a
number of people will be happy to help you optimize
it to a 'good' solution.

"..you no one will spoil the fun. "

--
Andrew Thompson
http://www.physci.org/

Message posted via JavaKB.com
http://www.javakb.com/Uwe/Forums.aspx/java-general/200712/1

 

[Andrew Thompson]

Andrew Thompson wrote:
..

...in the form of an SSCCE*.

* <http://www.physci.org/codes/sscce.html>

 

[Robert Klemme]

An interesting problem at here http://www.jroller.com/eu/entry/a_hash_set_puzzler.

I it's impossible to 'get bar instance from the original HashSet
collection without iterating trough all elements'.

Anynoe have a good solution for it?

Where is the point in getting an element from a collection if you have
it already? If you created a set that implements equivalence based on
hash code and .equals() but you wanted a set that implements equivalence
as identity you have built the wrong set.

Cheers

robert

 

[Patricia Shanahan]

An interesting problem at here http://www.jroller.com/eu/entry/a_hash_set_puzzler.

I it's impossible to 'get bar instance from the original HashSet
collection without iterating trough all elements'.

Anynoe have a good solution for it?

As the question is written, there is a trivial solution - if you want
the object referenced by bar, use bar.

There is a more interesting question lurking here: How to find out if
the object referenced by foo is in the HashSet, given the HashSet
contains an object that is equal to it.

Of course, if this question matters, the foo class was badly designed.
It should have used Object's equals and hashCode.

Patricia

 

[d0ngd0ng]

I'm sorry,I made a mistake.

http://www.jroller.com/eu/entry/a_hash_set_puzzler,this blog is not
mine,I just see it and find it's interesting.

I think it's impossible to sovle this problem without iterate all
elements.

So I hope to get some opions at here

Ugly,I use reflection to "get bar instance from the original HashSet
collection".


Object foo $B!a(B a_instance;
HashSet set = new HashSet();
Field mapField = set.getClass().getField("map");
mapField.setAccessible(true);
HashMap map = (HashMap)mapField.get(set);
Method getEntry = map.getClass().getMethod("getEntry",new Class[]
{Object.class});
getEntry.setAccssible(true);
Map.Entry entry = (Map.Entry)getEntry.invoke(map,new Object[]{foo});
Object bar = entry.getKey();

Because the HashSet use HashMap to implement the "Set",so I can get
the inner map object and then fetch the Map.Entry with the key foo.

It's ugly,but the solution get the bar instance without iterate all
elements.

How do you think about it?

d0ngd0ng

 

[Patricia Shanahan]

I'm sorry,I made a mistake.

http://www.jroller.com/eu/entry/a_hash_set_puzzler,this blog is not
mine,I just see it and find it's interesting.

I think it's impossible to sovle this problem without iterate all
elements.

So I hope to get some opions at here

Ugly,I use reflection to "get bar instance from the original HashSet
collection". ....
How do you think about it?

You don't need reflection to do this, if you allow implicit loops.

Patricia

 

[d0ngd0ng]

It's very cool,the best answer was given by the author,

as follow:
final Object[] foo = new Object[]{null};
set.contains(new Object() {
public int hashCode() {
return bar.hashCode();
}
public boolean equals(Object other) {
return bar.equals(foo[0]=other));
}
});
foo[0];

Please visit http://www.jroller.com/eu/entry/a_hash_set_puzzler to get
the detail.

Thanks all of you.

 

[Lew]

You don't need reflection to do this, if you allow implicit loops.

A HashSet, being a Set, will contain exactly one instance, 'barprime', of an
element that equals() 'bar'. No iteration needed.

The problem as stated on the website is goofy. The solution posted there is
goofier still.

Since there can only be one instance, 'barprime', in the Set that equals(bar),
the problem reduces to determination of whether 'barprime == bar'. There are
three ways to do this. Don't override Object.equals(), as Patricia suggested.
Canonicalize all insertions into the HashSet() so only one representative of
the equivalence class is allowed in. Use a java.util.IdentityHashMap<K, V>,
or implement an IdentitySet<K> backed by such.

I don't count the trivial way of having 'bar' around for comparison after the
retrieval. Robert Klemme brought this up already.

 

[d0ngd0ng]

The solution of the problem is elegant,and it's a good idea.

I think it's possible to happen in real development requirement.

 

[Michael Jung]

The solution of the problem is elegant,and it's a good idea.
I think it's possible to happen in real development requirement.

The solution has its elegance but not as solution to the stated
problem. As it is, it comes close to side-effect programming and it
should be carefully examined, whether such a solution is chosen.

A better problem might be obtaining a (member) property from an item
in set of which you have the reference (or equivalence class) only.
In that case overloading the equality method to retrieve that property
has some merit.

Michael

 

[Lasse Reichstein Nielsen]

The solution of the problem is elegant,and it's a good idea.

I think it's possible to happen in real development requirement.

I hope not. I wouldn't let it past a commit-check where I work,
and would seriously scold the person who did it. "Naughty, nauthty,
naughty coder!".

The "solution" depends on an implementation specific choice made by
the writer of HashSet that is not reflected in the Set interface or
HashSet documentation (namely that it uses the equals method on the
parameter to compare, not the one on the object already in the
set). This could change in the next update of the JRE without breaking
anything but this fragile example of how *not* to code things.

And it uses side effects in a method traditionally expected not to
have any.

This is "Programming by conincidence" at its best. "See, it works,
so it must be good", without considering how easily it may break.

It's a hack to avoid rewriting the existing code to support the
operations needed. If you need a way to extract the member of the
equivalence class that is in the collection, given an equivalent value
that is not in it, you should use a different data structure that
supports, and reflects that it supports, that operation.
E.g., a Map with each entry having key and value equal.
You can work with its keyset if you need a set.

And it must be your own code we are talking about, where you have
created the HashSet, if you know it is a HashSet. Other people's code
should expose the collection as just a Set.

/L

 

[Patricia Shanahan]

I hope not. I wouldn't let it past a commit-check where I work,
and would seriously scold the person who did it. "Naughty, nauthty,
naughty coder!".

The "solution" depends on an implementation specific choice made by
the writer of HashSet that is not reflected in the Set interface or
HashSet documentation (namely that it uses the equals method on the
parameter to compare, not the one on the object already in the
set). This could change in the next update of the JRE without breaking
anything but this fragile example of how *not* to code things.

The Set API documentation does say:

"boolean contains(Object o)

Returns true if this set contains the specified element. More formally,
returns true if and only if this set contains an element e such that
(o==null ? e==null : o.equals(e))."

However, the Object API documentation requires equals to be symmetric
for non-null references, so arguably a Set implementation class could
assume that e.equals(o) gives the same result.

It's a hack to avoid rewriting the existing code to support the
operations needed. If you need a way to extract the member of the
equivalence class that is in the collection, given an equivalent value
that is not in it, you should use a different data structure that
supports, and reflects that it supports, that operation.
E.g., a Map with each entry having key and value equal.
You can work with its keyset if you need a set.

More basically, if you care which of several equal objects you are
dealing with, maybe equals was defined incorrectly.

Patricia

 

[Lasse Reichstein Nielsen]

The Set API documentation does say:

"boolean contains(Object o)

Returns true if this set contains the specified element. More formally,
returns true if and only if this set contains an element e such that
(o==null ? e==null : o.equals(e))."

However, the Object API documentation requires equals to be symmetric
for non-null references, so arguably a Set implementation class could
assume that e.equals(o) gives the same result.

I stand corrected. The documentation does say something. But as you
point out, it needen't be the actual implementation.

More basically, if you care which of several equal objects you are
dealing with, maybe equals was defined incorrectly.

A much better point. Overriding equals should be done with extreme
care, and only if you really mean it.

/L

 

[Lew]

I hope not. I wouldn't let it past a commit-check where I work,
and would seriously scold the person who did it. "Naughty, nauthty,
naughty coder!".

The "solution" depends on an implementation specific choice made by
the writer of HashSet that is not reflected in the Set interface or
HashSet documentation (namely that it uses the equals method on the
parameter to compare, not the one on the object already in the
set). This could change in the next update of the JRE without breaking
anything but this fragile example of how *not* to code things.

And the so-called "solution" isn't even legal Java. Even translating it into
something compilable it remains a pile of --- something smelly.

 

[Patricia Shanahan]

And the so-called "solution" isn't even legal Java. Even translating it
into something compilable it remains a pile of --- something smelly.

Indeed. I have used the idea to produce the following version, which
compiles, with one warning suppression, and works. I still think that
any program that needs this is in *urgent* need of refactoring.

import java.util.HashSet;
import java.util.Set;

public class HashSetEntryFinder<T> {
public static void main(String[] args) {
Set<String> s = new HashSet<String>();
String foo = "aaa";
String bar = new String(foo);
System.out.println("Is foo equal to bar? "
+ foo.equals(bar));
System.out.println("Is foo identical to bar? "
+ (foo == bar));
s.add("xxx");
s.add(bar);
s.add("yyy");
s.add("zzz");
String barCandidate = new HashSetEntryFinder<String>().get(s, foo);
System.out.println("Is barCandidate identical to bar? "
+ (barCandidate == bar));
}


private T result = null;

private T key;

private int hash;

@SuppressWarnings("unchecked")
public boolean equals(Object o){
if(key.equals(o)){
result = (T)o;
return true;
}else{
return false;
}
}

public int hashCode(){
return hash;
}

public T get(Set<T> s, T key) {
result = null;
this.key = key;
hash = key.hashCode();
s.contains(this);
return result;
}
}

 

[d0ngd0ng]

Thanks all of you about my question.
I just think the solution is smarter and eleganter than what I have
thought.
But to admit that this is a good technique, is not it?
Although it in the development of the value is not high, but I think
at least it told us a new 'hacking techniques'.

d0ngd0ng

 

[Patricia Shanahan]

Thanks all of you about my question.
I just think the solution is smarter and eleganter than what I have
thought.
But to admit that this is a good technique, is not it?

It is an extremely bad, crude, inelegant and nasty technique. As
written, it has several bugs. Even in a cleaned-up form it breaks the
equals contract, one of the most important and pervasive contracts in
the whole of the Java API, twice over by making equals asymmetric and
non-reflexive.

It is also a way to avoid facing the real problem. If you are ever even
tempted to consider using this, please, please find the bug in the
design and fix it instead.

Patricia

 

[d0ngd0ng]

It is an extremely bad, crude, inelegant and nasty technique. As
written, it has several bugs. Even in a cleaned-up form it breaks the
equals contract, one of the most important and pervasive contracts in
the whole of the Java API, twice over by making equals asymmetric and
non-reflexive.

It is also a way to avoid facing the real problem. If you are ever even
tempted to consider using this, please, please find the bug in the
design and fix it instead.

Patricia

Although it in the development of the value is not high, but I think
at least it told us a new 'hacking techniques'.

If you face a large legacy systems, you need to deal with similar
problems, in such circumstances this technique is not there to help?
At least in some occasions, it is useful.Right?

d0ngd0ng

 

[Daniel Pitts]

An interesting problem at here http://www.jroller.com/eu/entry/a_hash_set_puzzler.

I it's impossible to 'get bar instance from the original HashSet
collection without iterating trough all elements'.

Anynoe have a good solution for it?

Thanks.

HashSet does *not* have a lookup method. Set itself does *not* have a
lookup method... If you need to get a specific instance, based on a
"key", use a Map instead.