 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / December 2007A hash set puzzler
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. ... >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. :-)"  SignatureAndrew Thompson http://www.physci.org/ .. >...in the form of an SSCCE*. * <http://www.physci.org/codes/sscce.html> SignatureAndrew Thompson http://www.physci.org/ > 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 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 ＝ 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 > > An interesting problem at herehttp://www.jroller.com/eu/entry/a_hash_set_puzzler. > [quoted text clipped - 11 lines] > > robert > I'm sorry,I made a mistake. > [quoted text clipped - 8 lines] > 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 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. > > I'm sorry,I made a mistake. > [quoted text clipped - 14 lines] > > Patricia d0ngd0ng wrote: >> I think it's impossible to sovle this problem without iterate all >> elements. [quoted text clipped - 3 lines] >> Ugly,I use reflection to "get bar instance from the original HashSet >> collection". > 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. SignatureLew The solution of the problem is elegant,and it's a good idea. I think it's possible to happen in real development requirement. :) > d0ngd0ng wrote: > >> I think it's impossible to sovle this problem without iterate all [quoted text clipped - 24 lines] > -- > Lew > 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 > 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 SignatureLasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.' >> The solution of the problem is elegant,and it's a good idea. >> [quoted text clipped - 10 lines] > 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 [quoted text clipped - 3 lines] > 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 > The Set API documentation does say: > [quoted text clipped - 7 lines] > 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 SignatureLasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.' >> The solution of the problem is elegant,and it's a good idea. >> [quoted text clipped - 10 lines] > 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. SignatureLew >>> The solution of the problem is elegant,and it's a good idea. >>> [quoted text clipped - 12 lines] > 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; } } 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 > 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 > 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 [quoted text clipped - 7 lines] > > 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 >> 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 [quoted text clipped - 16 lines] > > d0ngd0ng This is exactly how legacy systems become unmaintainable! If you keep-up the work to maintain the legacy system, it will not become legacy. If you add fragile hacks like you've suggested, it becomes legacy MUCH quicker. SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> d0ngd0ng, You keep asking the same question and getting the same answer. 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. :) Lasse Reichstein Nielsen: > 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!". Lew: > The problem as stated on the website is goofy. > The solution posted there is goofier still. Patricia Shanahan: > More basically, if you care which of several equal objects you are > dealing with, maybe equals was defined incorrectly. d0ngd0ng: >> 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? Patricia Shanahan: > 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 [quoted text clipped - 5 lines] > tempted to consider using this, please, please find the bug in the > design and fix it instead. d0ngd0ng: >> 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? > This is exactly how legacy systems become unmaintainable! If you > keep-up the work to maintain the legacy system, it will not become legacy. > > If you add fragile hacks like you've suggested, it becomes legacy MUCH > quicker. In other words, no, the technique in question is a very, very bad idea. It is wrong to do that thing there. No matter how many times you ask if it's a good idea, it will remain a bad idea. SignatureLew > d0ngd0ng, > [quoted text clipped - 59 lines] > -- > Lew I have to say that I have been speechless, re-find it an interesting topic. Thank you ：） > In other words, no, the technique in question is a very, very bad idea. It is > wrong to do that thing there. No matter how many times you ask if it's a good > idea, it will remain a bad idea. Well, sometimes even strange things happen - like with this mathematician at the university who found an epsilon which was so small that it became negative when divided by two. ;-) Cheers robert >> 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 [quoted text clipped - 14 lines] > problems, in such circumstances this technique is not there to help? > At least in some occasions, it is useful.Right? I'd have to be pretty desperate to use something as fragile as an equals that does not follow the contract specified in Object. I have trouble seeing a situation in which this would work but one could not build a more appropriate data structure in which the required operation would be natural. For example, one could have a map with the exact object as value, and use its keySet for the Set operations. However, the whole situation seems very artificial to me, because it depends on both wanting to have a set containing at most one element from each equals equivalence class, and yet caring which of the equal objects is in the set. Patricia > 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 problem itself is artificial and the solution is inelegant because it adds complexity by using the wrong tools for the job. It really should be a Map instead of a Set, since Map is designed for look-up, and Set is designed for containment/iteration only. SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> > 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 > An interesting problem at here http://www.jroller.com/eu/entry/a_hash_set_puzzler. > [quoted text clipped - 4 lines] > > 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. SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.