Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #17838 > unrolled thread

Re: hashCode

Back to article view | Back to comp.lang.java.programmer

Contents

  Re: hashCode "Lew" <lew@1:261/38.remove-odu-this> - 2012-08-13 19:38 +0000
    Re: hashCode "Arne Vajhøj" <������
høj@1:261/38.remove-odu-this> - 2012-08-13 19:38 +0000

#17838 — Re: hashCode

  To: Eric Sosman
From: "Lew" <lew@1:261/38.remove-nlb-this>

  To: Eric Sosman
From: "Lew" <lew@1:261/38.remove-m2z-this>

  To: Eric Sosman
From: Lew <noone@lewscanon.com>

Eric Sosman wrote:
>      Okay: Then returning a constant 1 (or 42 or 0 or whatever)
> would in fact satisfy the letter of the law regarding hashCode():

Not if you consider all aspects of what the Javadocs promise.

See my post upthread.

> Whenever x.equals(y) is true, x.hashCode() == y.hashCode().  In
> your example this would be trivially true because x,y,z,... all
> have the same hashCode() value, whether they're equal or not --
> You have lived up to the letter of the law.

No, because the law requires that the method support 'HashMap', which in turn 
calls for "properly" hashed objects.

>      Of course, such a hashCode() would make all those hash-based
> containers pretty much useless: They would work in the sense that
> they would get the Right Answer, but they'd be abominably slow,

Indeed.

> with expected performance of O(N) instead of O(1).  See
> <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/>
> for a survey of some denial-of-service attacks that work by driving
> hash tables from O(1) to O(N), resulting in catastrophic failure
> of the attacked system.
>
>      In other words, the letter of the law on hashCode() is a bare
> minimum that guarantees correct functioning, but it is not enough
> to guarantee usability.  Why isn't the law more specific?  Because

Actually, if you consider all that the Javadocs tell you, this "letter of the 
law" to which you refer is like saying the sequence "ABC" constitutes all of 
"the ABCs".

> nobody knows how to write "hashCode() must be correct *and* usable"
> in terms that would cover all the classes all the Java programmers
> have dreamed up and will dream up.  Your hashCode() meets the bare
> minimum requirement, but is not "usable."  The actual hashCode()
> provided by Object also meets the bare minimum requirement, and *is*
> usable as it stands, until (and unless; you don't HAVE to) you
> choose to implement other equals() semantics, and a hashCode() to
> match them.

As Arne states, "correct" means "fulfills the specification". The specification 
for Java API methods is the standard Javadocs, which do impose performance 
considerations on 'hashCode()'.

One understands that the spec isn't always fully enforceable by the compiler. 
[1] It is correct that the compiler will allow 'return 1;'. It is not correct 
that that fulfills the specification.

[1] Doesn't one?

--
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/38)
-+- 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/38)
-+- 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/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [next] | [standalone]

#17842

  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?=" <=?utf-8?b?qxjuzsbwywpow7hq?=@1:261/38.rem
ove-m2z-this>

  To: Lew
From: =?UTF-8?B?QXJuZSBWYWpow7hq?= <arne@vajhoej.dk>

On 8/11/2012 7:29 PM, Lew wrote:
> Eric Sosman wrote:
>>      Okay: Then returning a constant 1 (or 42 or 0 or whatever)
>> would in fact satisfy the letter of the law regarding hashCode():
>
> Not if you consider all aspects of what the Javadocs promise.
>
> See my post upthread.
>
>> Whenever x.equals(y) is true, x.hashCode() == y.hashCode().  In
>> your example this would be trivially true because x,y,z,... all
>> have the same hashCode() value, whether they're equal or not --
>> You have lived up to the letter of the law.
>
> No, because the law requires that the method support 'HashMap', which in
> turn calls for "properly" hashed objects.
>
>>      Of course, such a hashCode() would make all those hash-based
>> containers pretty much useless: They would work in the sense that
>> they would get the Right Answer, but they'd be abominably slow,
>
> Indeed.
>
>> with expected performance of O(N) instead of O(1).  See
>> <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/>
>> for a survey of some denial-of-service attacks that work by driving
>> hash tables from O(1) to O(N), resulting in catastrophic failure
>> of the attacked system.
>>
>>      In other words, the letter of the law on hashCode() is a bare
>> minimum that guarantees correct functioning, but it is not enough
>> to guarantee usability.  Why isn't the law more specific?  Because
>
> Actually, if you consider all that the Javadocs tell you, this "letter
> of the law" to which you refer is like saying the sequence "ABC"
> constitutes all of "the ABCs".
>
>> nobody knows how to write "hashCode() must be correct *and* usable"
>> in terms that would cover all the classes all the Java programmers
>> have dreamed up and will dream up.  Your hashCode() meets the bare
>> minimum requirement, but is not "usable."  The actual hashCode()
>> provided by Object also meets the bare minimum requirement, and *is*
>> usable as it stands, until (and unless; you don't HAVE to) you
>> choose to implement other equals() semantics, and a hashCode() to
>> match them.
>
> As Arne states, "correct" means "fulfills the specification". The
> specification for Java API methods is the standard Javadocs, which do
> impose performance considerations on 'hashCode()'.
>
> One understands that the spec isn't always fully enforceable by the
> compiler. [1] It is correct that the compiler will allow 'return 1;'. It
> is not correct that that fulfills the specification.

It fulfills the spec.

It does not fulfill you bizarre interpretation of "support".

Arne

-+- BBBS/Li6 v4.10 Dada-1
 + Origin: Prism bbs (1:261/38)
-+- 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/38)
-+- 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/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web