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

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

hashCode

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

Contents

  hashCode bob smith <bob@coolfone.comze.com> - 2012-08-10 08:47 -0700
    Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 12:13 -0400
      Re: hashCode markspace <-@.> - 2012-08-10 10:13 -0700
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 13:38 -0400
          Re: hashCode rossum <rossum48@coldmail.com> - 2012-08-11 10:36 +0100
    Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-10 12:34 -0400
      Re: hashCode bob smith <bob@coolfone.comze.com> - 2012-08-10 15:22 -0700
        Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-10 15:32 -0700
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 19:30 -0400
            Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:24 -0700
              Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:15 -0400
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:29 -0400
                  Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-11 22:43 -0400
                    Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:54 -0400
                      Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 21:46 -0700
                        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 16:53 -0400
                        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 17:00 -0400
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 19:27 -0400
          Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-12 17:06 +0200
            Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 16:59 -0400
              Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-13 19:17 +0200
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-19 19:42 -0400
                  Re: hashCode Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-21 10:30 +0000
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-19 19:47 -0400
                  Re: hashCode Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-21 10:43 +0000
                    Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-27 19:04 -0400
                      Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-27 16:55 -0700
                        Re: hashCode markspace <-@.> - 2012-08-27 17:03 -0700
                          Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-27 17:49 -0700
                          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-27 21:37 -0400
                          Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-27 18:58 -0700
                            Re: hashCode markspace <-@.> - 2012-08-27 21:19 -0700
                              Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-28 01:06 -0700
                                Re: hashCode markspace <-@.> - 2012-08-28 09:19 -0700
                                  Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-28 16:33 -0700
                                    Re: hashCode markspace <-@.> - 2012-08-28 17:02 -0700
                                      Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 11:06 -0700
                                        Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-29 14:49 -0400
                                          Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 13:40 -0700
                                            Re: hashCode Gene Wirchenko <genew@ocis.net> - 2012-08-29 18:02 -0700
                                          Re: hashCode Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2012-08-31 00:52 +0200
                                            Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-30 21:43 -0400
                                              Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-30 21:52 -0400
                                              Re: hashCode Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2012-08-31 04:18 +0200
                                                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 09:08 -0600
                                                  Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-31 11:38 -0400
                                                    Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-31 17:55 +0200
                                                    Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 09:56 -0600
                                                      Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-31 14:32 -0400
                                                        Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 14:38 -0600
                                                      Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-31 15:33 -0700
                                                        Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 16:41 -0600
                                                          Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-31 16:26 -0700
                                                            Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-09-02 11:54 -0600
                                                              Re: hashCode Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2012-09-03 00:47 +0200
                                                                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-09-03 21:44 -0600
                                              Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 09:08 -0600
                                                Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-31 17:58 +0200
                                        Re: hashCode markspace <-@.> - 2012-08-29 11:51 -0700
                                          Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 13:28 -0700
                                            Re: hashCode markspace <-@.> - 2012-08-29 16:05 -0700
                                              Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 16:23 -0700
                                                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-29 20:56 -0400
                                                  Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-30 11:19 +0200
                                                  Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-30 10:03 -0700
                                                    Re: hashCode Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 18:34 +0000
                                              Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-30 08:11 -0600
                                                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-30 10:06 -0700
                                              Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-30 19:16 -0400
                              Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-28 13:58 -0700
                            Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-28 13:56 -0700
                              Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-28 14:07 -0700
                                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-28 14:38 -0700
                        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-27 21:12 -0400
        Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-11 07:58 -0400
          Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:29 -0700
            Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:16 -0400
        Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-12 03:46 -0700
        Re: hashCode Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-08-12 12:23 -0400
          Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-12 09:40 -0700
            Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-12 13:59 -0400
              Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-12 11:17 -0700
            Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 17:02 -0400
          Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-12 19:03 +0200
    Re: hashCode Roedy Green <see_website@mindprod.com.invalid> - 2012-08-10 12:17 -0700
      Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-10 12:45 -0700
        Re: hashCode Roedy Green <see_website@mindprod.com.invalid> - 2012-08-11 04:54 -0700
          Re: hashCode Joerg Meier <joergmmeier@arcor.de> - 2012-08-11 18:25 +0200
            Re: hashCode Mike Winter <usenet@michael-winter.me.invalid> - 2012-08-11 18:53 +0100
          Re: hashCode Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-08-11 09:56 -0700
          Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-11 18:58 +0200
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:40 -0400
        Re: hashCode rossum <rossum48@coldmail.com> - 2012-08-11 18:47 +0100
      Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 19:25 -0400
        Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-11 08:00 -0400
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 09:49 -0400
    Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-11 15:33 +0200
      Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-11 15:34 +0200
      Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:34 -0700
        Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:37 -0700
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:19 -0400
          Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 21:48 -0700
      Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-12 12:08 +0200
        Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-12 12:18 +0200
        Re: hashCode Lew <noone@lewscanon.com> - 2012-08-12 11:27 -0700
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 17:11 -0400

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

#17792

On 12.08.2012 22:59, Arne Vajhøj wrote:
> 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. :-)

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

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

> 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/

[toc] | [prev] | [next] | [standalone]

#18155

On 8/13/2012 1:17 PM, Robert Klemme wrote:
> On 12.08.2012 22:59, Arne Vajhøj wrote:
>> On 8/12/2012 11:06 AM, Robert Klemme wrote:
>>> 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.

I guess my statement was a bit misleading.

... get O(1) characteristics for getting data similar to
various List implementation.

Arne

[toc] | [prev] | [next] | [standalone]

#18265

Arne Vajhøj <arne@vajhoej.dk> wrote:
>>> It disable the entire hashing functionality and a HashMap get
>>> characteristics of ArrayList.
> I guess my statement was a bit misleading.
> ... get O(1) characteristics for getting data similar to
> various List implementation.

Still is ;-)


O(n), not O(1)

[toc] | [prev] | [next] | [standalone]

#18156

On 8/13/2012 1:17 PM, Robert Klemme wrote:
> On 12.08.2012 22:59, Arne Vajhøj wrote:
>> But the code should actually work.
>
> Yes, sort of - depending on whether O(1) is a requirement or not.

That is a rare functional requirement.

(common non-functional)

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

Actually the more I think about the question the more logical
it sounds!

We are looking at two alternatives:
A) default functions properly but good performance requires an override
B) default gives good performance but may need an override to function 
properly

#A actually sounds more the Java way to me.

Arne

[toc] | [prev] | [next] | [standalone]

#18266

Arne Vajhøj <arne@vajhoej.dk> wrote:
> We are looking at two alternatives:
> A) default functions properly but good performance requires an override
> B) default gives good performance but may need an override to function 
>      properly

C) default hashCode() works perfectly well with default equals(), and only
  those with a specific requirement for equality, who thus need to override
  .equals(), anyway, also need to override hashCode() appropriately for
  their specific equality-relation.

Oh, wait, I think, Java already does it this way...

[toc] | [prev] | [next] | [standalone]

#18335

On 8/21/2012 6:43 AM, Andreas Leitgeb wrote:
> Arne Vajhøj <arne@vajhoej.dk> wrote:
>> We are looking at two alternatives:
>> A) default functions properly but good performance requires an override
>> B) default gives good performance but may need an override to function
>>       properly
>
> C) default hashCode() works perfectly well with default equals(), and only
>    those with a specific requirement for equality, who thus need to override
>    .equals(), anyway, also need to override hashCode() appropriately for
>    their specific equality-relation.

That is just B in another wording.

Arne

[toc] | [prev] | [next] | [standalone]

#18336

On 8/27/12 4:04 PM, Arne Vajhøj wrote:
> On 8/21/2012 6:43 AM, Andreas Leitgeb wrote:
>> Arne Vajhøj <arne@vajhoej.dk> wrote:
>>> We are looking at two alternatives:
>>> A) default functions properly but good performance requires an override
>>> B) default gives good performance but may need an override to function
>>>       properly
>>
>> C) default hashCode() works perfectly well with default equals(), and
>> only
>>    those with a specific requirement for equality, who thus need to
>> override
>>    .equals(), anyway, also need to override hashCode() appropriately for
>>    their specific equality-relation.
>
> That is just B in another wording.

However you word it.

The truth is that equals/hashCode should probably be overridden 
together, or together remain default.

I find it somewhat disappointing that there are Comparable/Comparator 
interfaces, but no Hashable/Hasher interfaces.

As it turns out, usually equals doesn't work well with subclasses 
anyway, so to have an external "equals" predicate makes for a cleaner 
abstraction.

[toc] | [prev] | [next] | [standalone]

#18337

On 8/27/2012 4:55 PM, Daniel Pitts wrote:

> I find it somewhat disappointing that there are Comparable/Comparator
> interfaces, but no Hashable/Hasher interfaces.


I think -- I'm not sure, but I believe -- the the ability to hash 
something into a hash table (a symbol table, in some terminologies) was 
considered so important and so fundamental to so many algorithms that it 
was deemed intrinsic to the system.  And therefore mandated for all objects.

For example, in C, one can always hash based on memory address.  In Java 
we don't have that option, so hashcode() takes the place of the 
intrinsic property of an address.

Whereas the ability to sort or order objects was recognized as not being 
intrinsic to all objects, so it was separated out.  Sorting a list, or 
ordering a tree, isn't something you can always do by default.

Just my two nickels here, and of course I'm guessing as to why 
hashcode() is included in Object and not an interface.

[toc] | [prev] | [next] | [standalone]

#18339

On Monday, August 27, 2012 5:03:37 PM UTC-7, markspace wrote:
> Daniel Pitts wrote:
>> I find it somewhat disappointing that there are Comparable/Comparator
>> interfaces, but no Hashable/Hasher interfaces.
> 
> I think -- I'm not sure, but I believe -- the the ability to hash 
> something into a hash table (a symbol table, in some terminologies) was 
> considered so important and so fundamental to so many algorithms that it 
> was deemed intrinsic to the system.  And therefore mandated for all objects.

Right or wrong, that's plausible.

And a separate Hasher interface would be kludgey.

> For example, in C, one can always hash based on memory address.  In Java 
> we don't have that option, so hashCode() takes the place of the 
> intrinsic property of an address.

That really makes sense. We have a nearly unique code for every object, and 
in practical terms one is vanishingly unlikely to get duplicate identity hashes 
within any given run.

> Whereas the ability to sort or order objects was recognized as not being 
> intrinsic to all objects, so it was separated out.  Sorting a list, or 
> ordering a tree, isn't something you can always do by default.
> 
> Just my two nickels here, and of course I'm guessing as to why 
> hashcode() is included in Object and not an interface.

So to cap this topic, we have a default identity hash in the 'Object#hashCode()' 
implementation that does a good job of distributing things in 'HashMap' and 
the like, and matches the semantics of the default identity 'equals()'. The OP's 
question as to whether one should substitute the degenerate hash gets a 
resounding "NO!" One overrides 'hashCode()' for consistency with 'equals()' 
exactly when the latter is overridden. If the type in question implements 
'Comparable' then the 'compareTo()' method likewise should match, as should 
'toString()' (in a somewhat looser sense of "match", perhaps, but not too loose).

All four methods speak to the semantics of sameness for the type in question, 
and should be consistent with each other.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#18341

On 8/27/2012 8:03 PM, markspace wrote:
> On 8/27/2012 4:55 PM, Daniel Pitts wrote:
>
>> I find it somewhat disappointing that there are Comparable/Comparator
>> interfaces, but no Hashable/Hasher interfaces.
>
>
> I think -- I'm not sure, but I believe -- the the ability to hash
> something into a hash table (a symbol table, in some terminologies) was
> considered so important and so fundamental to so many algorithms that it
> was deemed intrinsic to the system.  And therefore mandated for all
> objects.

Using Object as key is in my opinion rarely a good design.

And relevant more specific types defined in the Java library
could implement Hashable.

> Just my two nickels here, and of course I'm guessing as to why
> hashcode() is included in Object and not an interface.

It is a plausible explanation.

I think the Hashable interface would have been
good.

But the decision was made many years ago.

And .NET made the same decision!

Arne

[toc] | [prev] | [next] | [standalone]

#18345

On 8/27/2012 5:03 PM, markspace wrote:
...
> For example, in C, one can always hash based on memory address.  In Java
> we don't have that option, so hashcode() takes the place of the
> intrinsic property of an address.
...

In Java we have System.identityHashCode() which provides an address-like
hash code for any object.

Patricia

[toc] | [prev] | [next] | [standalone]

#18348

On 8/27/2012 6:58 PM, Patricia Shanahan wrote:
> On 8/27/2012 5:03 PM, markspace wrote:
> ...
>> For example, in C, one can always hash based on memory address.  In Java
>> we don't have that option, so hashcode() takes the place of the
>> intrinsic property of an address.
> ...
>
> In Java we have System.identityHashCode() which provides an address-like
> hash code for any object.


I think System.identityHashCode() is the (same as the) default 
implementation for Object::hashCode(), yes?

So there's a small bit of evidence in support of the idea that 
Object::hashCode() is meant to mimic the idea of just hashing on address.

[toc] | [prev] | [next] | [standalone]

#18351

On 8/27/2012 9:19 PM, markspace wrote:
> On 8/27/2012 6:58 PM, Patricia Shanahan wrote:
>> On 8/27/2012 5:03 PM, markspace wrote:
>> ...
>>> For example, in C, one can always hash based on memory address.  In Java
>>> we don't have that option, so hashcode() takes the place of the
>>> intrinsic property of an address.
>> ...
>>
>> In Java we have System.identityHashCode() which provides an address-like
>> hash code for any object.
>
>
> I think System.identityHashCode() is the (same as the) default
> implementation for Object::hashCode(), yes?

Yes, but it could have been written, with a slightly different
explanation, without putting hashCode() in Object.

>
> So there's a small bit of evidence in support of the idea that
> Object::hashCode() is meant to mimic the idea of just hashing on address.

I don't think you need such indirect evidence:

"As much as is reasonably practical, the hashCode method defined by
class Object does return distinct integers for distinct objects. (This
is typically implemented by converting the internal address of the
object into an integer, but this implementation technique is not
required by the JavaTM programming language.) "

[From the Object API documentation.]

Patricia

[toc] | [prev] | [next] | [standalone]

#18355

On 8/28/2012 1:06 AM, Patricia Shanahan wrote:

> On 8/27/2012 9:19 PM, markspace wrote:
>> I think System.identityHashCode() is the (same as the) default
>> implementation for Object::hashCode(), yes?

>
> Yes, but it could have been written, with a slightly different
> explanation, without putting hashCode() in Object.


And then you get into situations like this:

if( object instanceof Hasher )
   hash = ((Hasher) o).hashCode();
else
   hash = System.identityHashCode( object );

And I think we all know to use polymorphism instead here.  This is kind 
of what I'm saying.  The usefulness of a hash code was consider 
intrinsic to any object, and they wanted to avoid the code above. 
Therefore, Object::hashCode() becomes the design spec.


> I don't think you need such indirect evidence:
>
> "As much as is reasonably practical, the hashCode method defined by
> class Object does return distinct integers for distinct objects. (This
> is typically implemented by converting the internal address of the
> object into an integer, but this implementation technique is not
> required by the JavaTM programming language.) "


It doesn't really inform the reasons why hashCode() is part of Object 
though.  On that front, I'm speculating (i.e., making stuff up).

[toc] | [prev] | [next] | [standalone]

#18370

On 8/28/12 9:19 AM, markspace wrote:
> On 8/28/2012 1:06 AM, Patricia Shanahan wrote:
>
>> On 8/27/2012 9:19 PM, markspace wrote:
>>> I think System.identityHashCode() is the (same as the) default
>>> implementation for Object::hashCode(), yes?
>
>>
>> Yes, but it could have been written, with a slightly different
>> explanation, without putting hashCode() in Object.
>
>
> And then you get into situations like this:
>
> if( object instanceof Hasher )
>    hash = ((Hasher) o).hashCode();
> else
>    hash = System.identityHashCode( object );
>
> And I think we all know to use polymorphism instead here.  This is kind
> of what I'm saying.  The usefulness of a hash code was consider
> intrinsic to any object, and they wanted to avoid the code above.
> Therefore, Object::hashCode() becomes the design spec.
The polymorphism shouldn't have been on the object itself, Think about 
how TreeSet needs either Comparable objects, or a Comparator.

interface Hasher<Type> {
    int hash(Type t);
    boolean isEqual(Type l, Type r);
}

So, that would change HashMap to take a Hasher<? super K> instance in 
its constructor.  A default Hasher<Object> could be implemented to use 
System.identityHashCode and == for the common use-case.

This allows you to define different hashes and equality for the same set 
of object classes. It also forces you to implement hash and isEqual 
together.

It is, however, too late to "fix" the language in this way.

[toc] | [prev] | [next] | [standalone]

#18373

On 8/28/2012 4:33 PM, Daniel Pitts wrote:
>
> interface Hasher<Type> {
>     int hash(Type t);

Not really seeing how this is a good idea.  How would you implement this?


> So, that would change HashMap to take a Hasher<? super K> instance in
> its constructor.

This is the problem; Map (and HashMap) were desired to be spec'd as 
taking Object, not a subclass.

> A default Hasher<Object> could be implemented to use
> System.identityHashCode and == for the common use-case.


Again not seeing how you'd actually use that to put an object in a Map.

[toc] | [prev] | [next] | [standalone]

#18401

On 8/28/12 5:02 PM, markspace wrote:
> On 8/28/2012 4:33 PM, Daniel Pitts wrote:
>>
>> interface Hasher<Type> {
>>     int hash(Type t);
>
> Not really seeing how this is a good idea.  How would you implement this?
>
>
>> So, that would change HashMap to take a Hasher<? super K> instance in
>> its constructor.
>
> This is the problem; Map (and HashMap) were desired to be spec'd as
> taking Object, not a subclass.
Actually, they are Generic, so they are not spec'd to take Object, but 
to take a specific subtype defined at compile time. At least, now that 
they have the addition of Generics. Pre-generics, they still had 
Comparators which had the same behavior that I'm describing, but instead 
of defining buckets, they define an ordering. See below.
>
>> A default Hasher<Object> could be implemented to use
>> System.identityHashCode and == for the common use-case.
>
>
> Again not seeing how you'd actually use that to put an object in a Map.

Example usage:
++++
// MyKeyHasher implements Hasher<MyKey>
Map<MyKey, MyValue> map=new HashMap<MyKey,MyValue>(new MyKeyHasher());

map.put(myFirstKey, myFirstValue);
map.put(mySecondKey, mySecondValue);
++++

This is directly analogous to how TreeMap and Comparator currently work 
together:

++++
Map<MyKey, MyValue> map =
         new TreeMap<MyKey, MyValue(new MyKeyComparator());

map.put(myFirstKey, myFirstValue);
map.put(mySecondKey, mySecondValue);
++++



Now, it would be my opinion that the standard library should provide a 
IdentityHasher implementation as such:
++++
public final class IdentityHasher<T> implements Hasher<T> {
    public int hash(T object) {
       return System.identityHashCode(object);
    }
    public boolean isEqual(T l, T r) {
       return l == r;
    }
}
++++

There could of course be a singleton instance of this, similar to how 
they have a singleton for Collections.emptySet();

Does that make more sense?

[toc] | [prev] | [next] | [standalone]

#18407

On 8/29/2012 2:06 PM, Daniel Pitts wrote:
> On 8/28/12 5:02 PM, markspace wrote:
>> On 8/28/2012 4:33 PM, Daniel Pitts wrote:
>>>
>>> interface Hasher<Type> {
>>>     int hash(Type t);
>>
>> Not really seeing how this is a good idea.  How would you implement this?
>>
>>
>>> So, that would change HashMap to take a Hasher<? super K> instance in
>>> its constructor.
>>
>> This is the problem; Map (and HashMap) were desired to be spec'd as
>> taking Object, not a subclass.
> Actually, they are Generic, so they are not spec'd to take Object, but
> to take a specific subtype defined at compile time. At least, now that
> they have the addition of Generics. Pre-generics, they still had
> Comparators which had the same behavior that I'm describing, but instead
> of defining buckets, they define an ordering. See below.

     Actually, "take" is insufficiently specific.  A Map<K,V>
has a put() method with K,V parameters, and a putAll() method
with a Map<? extends K, ? extends V> parameter.  To that extent,
Map<K,V> "takes" K.

     But Map<K,V> *also* has get() and remove() and containsKey()
methods with Object parameters, not K parameters.  (It also has a
containsValue() method taking Object, not V.)  So insofar as
these methods are concerned, Map<K,V> "takes" Object.

>>> A default Hasher<Object> could be implemented to use
>>> System.identityHashCode and == for the common use-case.
>>
>>
>> Again not seeing how you'd actually use that to put an object in a Map.
>
> Example usage:
> ++++
> // MyKeyHasher implements Hasher<MyKey>
> Map<MyKey, MyValue> map=new HashMap<MyKey,MyValue>(new MyKeyHasher());
>
> map.put(myFirstKey, myFirstValue);
> map.put(mySecondKey, mySecondValue);
> ++++

     This could sort of work, but not very well.  As I wrote some
<hunt, hunt, hunt, ah!> seventeen days ago in this thread:

	I don't think a HashCalculator interface along
	the lines of Comparable would save the day.

The difficulty is that an external Hasher would have no access to
private fields of MyKey.  That may seem a small drawback, since it
is rare to have a contributor to an object's "value" that is not
at the very least accessible through a getter.  The Hasher might
need to make method calls where today's built-in hashCode() just
makes field references, but -- hey, how bad could that be?

     IMHO, it could be pretty bad.  Take java.lang.String, for
example: As things stand today hashCode() inspects the "value"
of the String, and everything it uses would be accessible to a
Hasher<String>.  But hashCode() then caches the computed value
in a private field within String to avoid recomputing it on every
subsequent call!  Could Hasher<String> do the same?  How?

     Okay, so the implementor of String perceives the problem and
decides that String itself will provide a default Hasher<String>
implementation.  (This might be a static nested class, but it'd
probably be more efficient to have String implement Hasher<String>
directly, so every String is its own Hasher.)  And the implementor
of BigInteger does the same, and so does the implementor of URL,
and of File, and of -- Hey, wait a minute!  We're right back where
we began, except with more overhead and more verbiage!

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#18416

On 8/29/12 11:49 AM, Eric Sosman wrote:
> On 8/29/2012 2:06 PM, Daniel Pitts wrote:
>> On 8/28/12 5:02 PM, markspace wrote:
>>> On 8/28/2012 4:33 PM, Daniel Pitts wrote:
>>>>
>>>> interface Hasher<Type> {
>>>>     int hash(Type t);
>>>
>>> Not really seeing how this is a good idea.  How would you implement
>>> this?
>>>
>>>
>>>> So, that would change HashMap to take a Hasher<? super K> instance in
>>>> its constructor.
>>>
>>> This is the problem; Map (and HashMap) were desired to be spec'd as
>>> taking Object, not a subclass.
>> Actually, they are Generic, so they are not spec'd to take Object, but
>> to take a specific subtype defined at compile time. At least, now that
>> they have the addition of Generics. Pre-generics, they still had
>> Comparators which had the same behavior that I'm describing, but instead
>> of defining buckets, they define an ordering. See below.
>
>      Actually, "take" is insufficiently specific.  A Map<K,V>
> has a put() method with K,V parameters, and a putAll() method
> with a Map<? extends K, ? extends V> parameter.  To that extent,
> Map<K,V> "takes" K.
>
>      But Map<K,V> *also* has get() and remove() and containsKey()
> methods with Object parameters, not K parameters.  (It also has a
> containsValue() method taking Object, not V.)  So insofar as
> these methods are concerned, Map<K,V> "takes" Object.
Those are very good points.  I had forgotten about the fact that get() 
takes Object.   The solution I come up with off the top of my head is to 
update get/remove/etc... to all take the appropriate type (K or V). Yes, 
this reduces some "functionality" of the class, but I doubt 99% of 
programmers would care more than 1% of the time.  I have used this 
"feature", but only because proper typing wasn't done on an existing 
legacy project.

Keep in mind, I'm talking about what Map *could* have been, not what it 
could become.

>
>>>> A default Hasher<Object> could be implemented to use
>>>> System.identityHashCode and == for the common use-case.
>>>
>>>
>>> Again not seeing how you'd actually use that to put an object in a Map.
>>
>> Example usage:
>> ++++
>> // MyKeyHasher implements Hasher<MyKey>
>> Map<MyKey, MyValue> map=new HashMap<MyKey,MyValue>(new MyKeyHasher());
>>
>> map.put(myFirstKey, myFirstValue);
>> map.put(mySecondKey, mySecondValue);
>> ++++
>
>      This could sort of work, but not very well.  As I wrote some
> <hunt, hunt, hunt, ah!> seventeen days ago in this thread:
>
>      I don't think a HashCalculator interface along
>      the lines of Comparable would save the day.
>
> The difficulty is that an external Hasher would have no access to
> private fields of MyKey.  That may seem a small drawback, since it
> is rare to have a contributor to an object's "value" that is not
> at the very least accessible through a getter.  The Hasher might
> need to make method calls where today's built-in hashCode() just
> makes field references, but -- hey, how bad could that be?
>
>      IMHO, it could be pretty bad.  Take java.lang.String, for
> example: As things stand today hashCode() inspects the "value"
> of the String, and everything it uses would be accessible to a
> Hasher<String>.  But hashCode() then caches the computed value
> in a private field within String to avoid recomputing it on every
> subsequent call!  Could Hasher<String> do the same?  How?

Nothing would prevent String from having a hashCode method which behaves 
exactly as it does today. The StringHasher class would simply delegate 
to the String.hashCode() method, which allows String to cache as expected.

>
>      Okay, so the implementor of String perceives the problem and
> decides that String itself will provide a default Hasher<String>
> implementation.  (This might be a static nested class, but it'd
> probably be more efficient to have String implement Hasher<String>
> directly, so every String is its own Hasher.)  And the implementor
> of BigInteger does the same, and so does the implementor of URL,
> and of File, and of -- Hey, wait a minute!  We're right back where
> we began, except with more overhead and more verbiage!
Oh no, dreaded letters in my source code. I must reduce it down to as 
little as possible, even if it means having one class be responsible for 
15 things.

Java is verbose, but that shouldn't determine what is good design and 
what isn't.  Also, as I've suggested elsethread, having a Hashable 
interface (similar to Comparable) would allow Objects to define a 
sensible default comparison/hashing algorithm *specific to that class*.

A class with subclasses has no sensible algorithm (unless it takes into 
account the actual type before comparison). This is the use-case where 
Hasher makes the most sense.  The user of the objects of the class can 
specify what they care about in the equality of two objects, even if 
those objects are of different specific types.

[toc] | [prev] | [next] | [standalone]

#18421

On Wed, 29 Aug 2012 13:40:47 -0700, Daniel Pitts
<newsgroup.nospam@virtualinfinity.net> wrote:

>On 8/29/12 11:49 AM, Eric Sosman wrote:

[snip]

>>      Okay, so the implementor of String perceives the problem and
>> decides that String itself will provide a default Hasher<String>
>> implementation.  (This might be a static nested class, but it'd
>> probably be more efficient to have String implement Hasher<String>
>> directly, so every String is its own Hasher.)  And the implementor
>> of BigInteger does the same, and so does the implementor of URL,
>> and of File, and of -- Hey, wait a minute!  We're right back where
>> we began, except with more overhead and more verbiage!

>Oh no, dreaded letters in my source code. I must reduce it down to as 
>little as possible, even if it means having one class be responsible for 
>15 things.

"There are three things a man must do
 before his life is done;
 Write two lines in APL,
 And make the buggers run."
-- Stan Kelly-Bootle, "The Devil's DP Dictionary"
as quoted in http://news.ycombinator.com/item?id=1041500

[snip]

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

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

csiph-web