AppletTalk.com Java discussions newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  hashCode Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next          AppletTalk.com Forum Index -> Java Language Programming View previous topic :: View next topic   Author Message Arne Vajhøj Guest Posted: Sun Aug 12, 2012 4:58 pm    Post subject: Re: hashCode To: Eric Sosman From: =?UTF-8?B?QXJuZSBWYWpow7hq?= <arne (AT) vajhoej (DOT) dk> On 8/11/2012 10:43 PM, Eric Sosman wrote: Quote: The O.P. asked whether it would "be potentially better" if Object's hashCode() returned a constant. He did *not* ask whether such an implementation would be correct; he only asked if it would "be potentially better." Upon prompting he explained what he meant by "better," and in light of that explanation the answer to his original question is NO. Discussions about "Oh, but it's CORRECT" are just red herrings; it's still not "better." The original questions were: #Is it always technically correct to override the hashCode function #like so: # # @Override # public int hashCode() { # return 1; # } For which the answer is YES. Per documentation. But with really poor performance in many relevant cases. #Would it be potentially better if that was Object's implementation? Which was clarified to: #Better in the sense that you would never HAVE to override hashCode. For which the answer is also YES. Per the previous. But with the same performance note. And a big sigh because it seems to want to broaden bad performance from a single class to the entire programming style (multiple classes). Arne --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Lew Guest Posted: Sun Aug 12, 2012 4:58 pm    Post subject: Re: hashCode To: =?UTF-8?B?QXJuZSBWYWpow7hq?= From: Lew <noone (AT) lewscanon (DOT) com> Arne Vajh-,j wrote: Quote: Lew wrote: Jan Burse wrote: Maybe it would make sense to spell out what the contract for hashCode() is. Well the contract is simply, the following invariant should hold: /* invariant that should hold */ if a.equals(b) then a.hashCode()==b.hashCode() True, but if you read the specification for 'hashCode()' fully, that is not the entire contract, only the compiler-enforceable part of it. The entire specification requires that as much as feasible, the 'Object' implementation distinguish distinct instances, and that the method generally support 'HashMap', which promises O(1) 'get()' and 'put()' with a "proper" (i.e., compliant) 'hashCode()'. Two wrong statements. It says that the method is defined to support HashMap And HashMap does not guarantee O(1) with a correct hashCode - it guarantee that for one that return good distributed values. Granted. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Patricia Shanahan Guest Posted: Sun Aug 12, 2012 4:58 pm    Post subject: Re: hashCode To: Joshua Cranmer From: Patricia Shanahan <pats (AT) acm (DOT) org> On 8/12/2012 9:23 AM, Joshua Cranmer wrote: Quote: On 8/10/2012 6:22 PM, bob smith wrote: Better in the sense that you would never HAVE to override hashCode. Now, there are cases where you HAVE to override it, or your code is very broken. Returning a constant hash code is correct in the same sense that answering "yes" to the question "Can you tell me the correct way to do this?" would be--syntactically and semantically correct, but completely contrary to the actual intent of the question. The point of the hash code is to provide a cheap way to quickly distinguish inputs (in the sense that Pr(a.hashCode() == b.hashCode() and !a.equals(b)) should be as small as possible [1]). A constant-value hash completely negates the purpose of the hash code, and this renders the hashCode again completely unusable for anything that actually wants to use it. In the default case, a.hashCode() == b.hashCode() only when a == b (this definitely holds true with 32-bit machines and I'm pretty sure it still holds true with 64-bit machines, but I'd have to reverify the JVM source code to be certain). It is thus correct so long as identity equals is correct. It is also potentially correct in a limited set of cases where a.equals(b) and a != b. In all of these cases, it would not only be correct but also extremely useful, having pretty strong guarantees about the distribution of hash values. [1] Actually, for good performance, hash codes should go one step further and make slightly stronger guarantees about independence with respect to the size of the hash table. But I digress. I think there are two reasonably usable ways of handling this issue. One is the current arrangement, in which every class has a hashCode that is expected to be usable for selecting a hash table bucket. Keeping hashCode as an Object method but making it useless for bucket selection unless overridden would not be a good alternative. A more reasonable alternative would be to have hashCode as the only member of a HashKey interface that would be implemented by every class whose objects are intended to be suitable for use as has keys. Those objects that have a hashCode would still have to have a usable one, but some classes would not implement HashKey and not have a hashCode at all. Patricia --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Eric Sosman Guest Posted: Sun Aug 12, 2012 6:00 pm    Post subject: Re: hashCode To: Patricia Shanahan From: Eric Sosman <esosman@ieee-dot-org.invalid> On 8/12/2012 12:40 PM, Patricia Shanahan wrote: Quote: [...] I think there are two reasonably usable ways of handling this issue. One is the current arrangement, in which every class has a hashCode that is expected to be usable for selecting a hash table bucket. Keeping hashCode as an Object method but making it useless for bucket selection unless overridden would not be a good alternative. A more reasonable alternative would be to have hashCode as the only member of a HashKey interface that would be implemented by every class whose objects are intended to be suitable for use as has keys. Those objects that have a hashCode would still have to have a usable one, but some classes would not implement HashKey and not have a hashCode at all. Ugh. So if J. Random Programmer is too lazy or unimaginative to write hashCode(), that means I can't use his class as a HashMap key, or even put instances in a HashSet? Ugh, again. (And, no: I don't think a HashCalculator interface along the lines of Comparable would save the day.) -- Eric Sosman esosman@ieee-dot-org.invalid --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Patricia Shanahan Guest Posted: Sun Aug 12, 2012 6:00 pm    Post subject: Re: hashCode To: Eric Sosman From: Patricia Shanahan <pats (AT) acm (DOT) org> On 8/12/2012 10:59 AM, Eric Sosman wrote: Quote: On 8/12/2012 12:40 PM, Patricia Shanahan wrote: [...] I think there are two reasonably usable ways of handling this issue. One is the current arrangement, in which every class has a hashCode that is expected to be usable for selecting a hash table bucket. Keeping hashCode as an Object method but making it useless for bucket selection unless overridden would not be a good alternative. A more reasonable alternative would be to have hashCode as the only member of a HashKey interface that would be implemented by every class whose objects are intended to be suitable for use as has keys. Those objects that have a hashCode would still have to have a usable one, but some classes would not implement HashKey and not have a hashCode at all. Ugh. So if J. Random Programmer is too lazy or unimaginative to write hashCode(), that means I can't use his class as a HashMap key, or even put instances in a HashSet? Ugh, again. (And, no: I don't think a HashCalculator interface along the lines of Comparable would save the day.) I'm not saying that it would be better than the current situation, just better than having hashCode implementations that appear to be there, but in practice must not be used for hash bucket selection. Patricia --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Arne Vajhøj Guest Posted: Sun Aug 12, 2012 6:53 pm    Post subject: Re: hashCode On 8/12/2012 12:46 AM, Lew wrote: Quote: Arne Vajhøj wrote: The original questions were: #Is it always technically correct to override the hashCode function #like so: # # @Override # public int hashCode() { # return 1; # } For which the answer is YES. Per documentation. But with really poor performance in many relevant cases. #Would it be potentially better if that was Object's implementation? Which was clarified to: #Better in the sense that you would never HAVE to override hashCode. For which the answer is also YES. Per the previous. No, that's not true. Value-equality maps, for example, would not work if you didn't override 'hashCode()' in the key type to match value equality on the keys. That was almost exactly what I answered in my first answer to the original poster. Then I read it as "would it be better if my class used Object's implementation". But after reading the clarification then I think it should be read as "would it be better if Object used the implementation shown". Very different question! Arne Back to top Arne Vajhøj Guest Posted: Sun Aug 12, 2012 6:59 pm    Post subject: Re: hashCode On 8/12/2012 11:06 AM, Robert Klemme wrote: Quote: On 11.08.2012 01:27, Arne Vajhøj wrote: On 8/10/2012 6:22 PM, bob smith wrote: On Friday, August 10, 2012 11:34:28 AM UTC-5, Eric Sosman wrote: On 8/10/2012 11:47 AM, bob smith wrote: Is it always technically correct to override the hashCode function like so: @Override public int hashCode() { return 1; } Would it be potentially better if that was Object's implementation? Define "better." Better in the sense that you would never HAVE to override hashCode. Now, there are cases where you HAVE to override it, or your code is very broken. It is not broken. It will perform poorly in many cases. Well, I would go as far as to say that it will perform poorly in all cases where hashCode() is actually needed More or less. Quote: - and that makes it broken. This thread started about whether it is correct. The term correct has a very specific meaning in programming and that always return 1 code is correct. Now you talk about broken. If broken means not good, then you are right. If broken means not correct, then you are wrong. I suspect that broken is not very well defined. Quote: The whole idea of hashing is based on the fact that the hash code _somehow_ represents the item to be hashed. If all items have the same constant hash code there is no point in hashing at all. So while it does work, it does not work as intended. It disable the entire hashing functionality and a HashMap get characteristics of ArrayList. But the code should actually work. Arne Back to top Arne Vajhøj Guest Posted: Sun Aug 12, 2012 7:00 pm    Post subject: Re: hashCode On 8/12/2012 12:46 AM, Lew wrote: Quote: Arne Vajhøj wrote: But with the same performance note. And a big sigh because it seems to want to broaden bad performance from a single class to the entire programming style (multiple classes). Overriding 'hashCode()' is done for functional reasons, not performance reasons. If you fail to override the method, you'll get incorrect behavior, for example failing to find a collection member that is actually present. Correct. But the return constant is a special case. It functions as it should but performs very poorly. Arne Back to top Arne Vajhøj Guest Posted: Sun Aug 12, 2012 7:02 pm    Post subject: Re: hashCode On 8/12/2012 12:40 PM, Patricia Shanahan wrote: Quote: Keeping hashCode as an Object method but making it useless for bucket selection unless overridden would not be a good alternative. A more reasonable alternative would be to have hashCode as the only member of a HashKey interface that would be implemented by every class whose objects are intended to be suitable for use as has keys. Those objects that have a hashCode would still have to have a usable one, but some classes would not implement HashKey and not have a hashCode at all. That would avoid using the hash for classes where it does not make much sense. I like it. Given that there is a gazillion lines of code out there that stores Object, then it can not be changed. Arne Back to top Arne Vajhøj Guest Posted: Sun Aug 12, 2012 7:11 pm    Post subject: Re: hashCode On 8/12/2012 2:27 PM, Lew wrote: Quote: Even for cases where one predicts the use will not require one or another of the consistency practices, it is harmless to enforce them. There are four methods a type might use to represent equality or identity and deviations therefrom: 'equals()' of course, and 'hashCode()', 'compareTo()', and 'toString()'. There may be external 'Comparator's on that type. All these methods on or of a type, where they exist, should be consistent, absent an overwhelming and sound reason not to be. Should you design anything that violates the consistency rule, then please do both Javadoc and code-comment it properly. I agree. (well toString is not high on my priority list for what needs to behave certain ways, but ...) To make it easier to get them consistent, then I think it would be nice with syntactic sugar. Like: public class Data { @ValueId private int iv; @ValueId private String sv; // the rest of the class } which would cause the compiler to emit equals and hashCode methods that are test of the @ValueId fields are equal and creates a "decent" hash. public class Data implements Comparable<Data> { @ValueId private int iv; @ValueId private String sv; // the rest of the class } could cause the compiler to output a compareTo as well. It is invisible code, but we already got that with the default constructor. And it will help make those methods consistent. Of course explicit override should still be possible. Arne Back to top Robert Klemme Guest Posted: Mon Aug 13, 2012 3:17 pm    Post subject: Re: hashCode On 12.08.2012 22:59, Arne Vajhøj wrote: Quote: On 8/12/2012 11:06 AM, Robert Klemme wrote: On 11.08.2012 01:27, Arne Vajhøj wrote: On 8/10/2012 6:22 PM, bob smith wrote: On Friday, August 10, 2012 11:34:28 AM UTC-5, Eric Sosman wrote: On 8/10/2012 11:47 AM, bob smith wrote: Is it always technically correct to override the hashCode function like so: @Override public int hashCode() { return 1; } Would it be potentially better if that was Object's implementation? Define "better." Better in the sense that you would never HAVE to override hashCode. Now, there are cases where you HAVE to override it, or your code is very broken. It is not broken. It will perform poorly in many cases. Well, I would go as far as to say that it will perform poorly in all cases where hashCode() is actually needed More or less. - and that makes it broken. This thread started about whether it is correct. The term correct has a very specific meaning in programming and that always return 1 code is correct. Now you talk about broken. Actually it wasn't me who brought up the term. :-) Quote: If broken means not good, then you are right. If broken means not correct, then you are wrong. I suspect that broken is not very well defined. Right. :-) Quote: The whole idea of hashing is based on the fact that the hash code _somehow_ represents the item to be hashed. If all items have the same constant hash code there is no point in hashing at all. So while it does work, it does not work as intended. It disable the entire hashing functionality and a HashMap get characteristics of ArrayList. An ArrayList allows multiple occurrences of the same instance - and does not store key value pairs. That won't be the case with HashMap as equals() (if properly implemented) will prevent that (albeit slowly, or more correct: slower than with a proper implementation of hashCode()). Also, a HashMap will degenerate more to a LinkedList via the chaining of a bucket's entries. Quote: But the code should actually work. Yes, sort of - depending on whether O(1) is a requirement or not. Still, the idea to implement hashCode() in Object in a way to return a constant to avoid necessity of overriding it is crazy - especially since you then cannot efficiently use Object as hash key - which you can today. Kind regards robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/ Back to top Lew Guest Posted: Mon Aug 13, 2012 5:38 pm    Post subject: Re: hashCode To: =?UTF-8?B?QXJuZSBWYWpow7hq?= From: "Lew" <lew@1:261/38.remove-nlb-this> To: =?UTF-8?B?QXJuZSBWYWpow7hq?= From: "Lew" <lew@1:261/38.remove-m2z-this> To: =?UTF-8?B?QXJuZSBWYWpow7hq?= From: Lew <noone (AT) lewscanon (DOT) com> Arne Vajh-,j wrote: Quote: Lew wrote: Jan Burse wrote: Maybe it would make sense to spell out what the contract for hashCode() is. Well the contract is simply, the following invariant should hold: /* invariant that should hold */ if a.equals(b) then a.hashCode()==b.hashCode() True, but if you read the specification for 'hashCode()' fully, that is not the entire contract, only the compiler-enforceable part of it. The entire specification requires that as much as feasible, the 'Object' implementation distinguish distinct instances, and that the method generally support 'HashMap', which promises O(1) 'get()' and 'put()' with a "proper" (i.e., compliant) 'hashCode()'. Two wrong statements. It says that the method is defined to support HashMap And HashMap does not guarantee O(1) with a correct hashCode - it guarantee that for one that return good distributed values. Granted. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg -+- BBBS/Li6 v4.10 Dada-1 + Origin: Prism bbs (1:261/3 -+- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 -+- BBBS/Li6 v4.10 Dada-1 + Origin: Prism bbs (1:261/3 -+- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Arne Vajhøj Guest Posted: Mon Aug 13, 2012 5:38 pm    Post subject: Re: hashCode To: Lew From: "=?UTF-8?B?QXJuZSBWYWpow7hq?=" <=?utf-8?b?qxjuzsbwywpow7hq?=@1:261/38.rem ove-nlb-this> To: Lew From: =?UTF-8?B?QXJuZSBWYWpow7hq?= <arne (AT) vajhoej (DOT) dk> On 8/12/2012 12:46 AM, Lew wrote: Quote: Arne Vajh-,j wrote: The original questions were: #Is it always technically correct to override the hashCode function #like so: # # @Override # public int hashCode() { # return 1; # } For which the answer is YES. Per documentation. But with really poor performance in many relevant cases. #Would it be potentially better if that was Object's implementation? Which was clarified to: #Better in the sense that you would never HAVE to override hashCode. For which the answer is also YES. Per the previous. No, that's not true. Value-equality maps, for example, would not work if you didn't override 'hashCode()' in the key type to match value equality on the keys. That was almost exactly what I answered in my first answer to the original poster. Then I read it as "would it be better if my class used Object's implementation". But after reading the clarification then I think it should be read as "would it be better if Object used the implementation shown". Very different question! Arne -+- BBBS/Li6 v4.10 Dada-1 + Origin: Prism bbs (1:261/3 -+- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Arne Vajhøj Guest Posted: Mon Aug 13, 2012 5:38 pm    Post subject: Re: hashCode To: Robert Klemme From: "Arne Vajhoj" <arne.vajhoj@1:261/38.remove-nlb-this> To: Robert Klemme From: Arne Vajhoj <arne (AT) vajhoej (DOT) dk> On 8/12/2012 11:06 AM, Robert Klemme wrote: Quote: On 11.08.2012 01:27, Arne Vajhoj wrote: On 8/10/2012 6:22 PM, bob smith wrote: On Friday, August 10, 2012 11:34:28 AM UTC-5, Eric Sosman wrote: On 8/10/2012 11:47 AM, bob smith wrote: Is it always technically correct to override the hashCode function like so: @Override public int hashCode() { return 1; } Would it be potentially better if that was Object's implementation? Define "better." Better in the sense that you would never HAVE to override hashCode. Now, there are cases where you HAVE to override it, or your code is very broken. It is not broken. It will perform poorly in many cases. Well, I would go as far as to say that it will perform poorly in all cases where hashCode() is actually needed More or less. Quote: - and that makes it broken. This thread started about whether it is correct. The term correct has a very specific meaning in programming and that always return 1 code is correct. Now you talk about broken. If broken means not good, then you are right. If broken means not correct, then you are wrong. I suspect that broken is not very well defined. Quote: The whole idea of hashing is based on the fact that the hash code _somehow_ represents the item to be hashed. If all items have the same constant hash code there is no point in hashing at all. So while it does work, it does not work as intended. It disable the entire hashing functionality and a HashMap get characteristics of ArrayList. But the code should actually work. Arne -+- BBBS/Li6 v4.10 Dada-1 + Origin: Prism bbs (1:261/3 -+- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Jan Burse Guest Posted: Mon Aug 13, 2012 5:38 pm    Post subject: Re: hashCode To: Jan Burse From: "Jan Burse" <jan.burse@1:261/38.remove-nlb-this> To: Jan Burse From: "Jan Burse" <jan.burse@1:261/38.remove-m2z-this> To: Jan Burse From: Jan Burse <janburse (AT) fastmail (DOT) fm> Jan Burse schrieb: Quote: Maybe it would make sense to spell out what the contract for hashCode() is. Those who are interested can read the original text. It is found here: http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hashCode%28%29 --------------------------------------------------------------- "If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result." That is: /* invariant that should hold */ if a.equals(b) then a.hashCode()==b.hashCode() ---------------------------------------------------------------- "It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables." That is: /* not implied and thus not required by the invariant */ if a.hashCode()==b.hashCode() then a.equals(b) It is also quite unlikely that a hashCode() would satisfy the later, although the closer it comes to the later, the better it works for HashMap, etc.. ---------------------------------------------------------------- There is no reference to Comparable and the compareTo. If I am not using HashMap or HashSet in my application, and still override equals, I do not need to implement hashCode(). I could for example use TreeMap or TreeSet and implement the Comparable interface. There is a reference to equals() back from Comparable though. http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html Bye -+- BBBS/Li6 v4.10 Dada-1 + Origin: Prism bbs (1:261/3 -+- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 -+- BBBS/Li6 v4.10 Dada-1 + Origin: Prism bbs (1:261/3 -+- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/3 --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24 Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         AppletTalk.com Forum Index -> Java Language Programming All times are GMT Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next Page 5 of 9   Jump to: Select a forum Java Newsgroups----------------Java DiscussionsWeb-based java games comp.lang.java 3D Graphics API's for Java Java: Support and criticism Java System Announcements comp.lang.java.api JavaBeans Java and CORBA Java and Databases comp.lang.java.developer Java GUI Toolkits Java Help comp.lang.java.javascript JVM, native methods and hardware comp.lang.java.misc Java Language Programming Security and Java comp.lang.java.setup Java Software Tools comp.lang.java.tech ibm.software.java.linux  Non-English Java Newsgroups----------------Java Language (German)Language Java (Français)Java (Italian)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.