Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: hashCode
Date: Wed, 29 Aug 2012 14:49:15 -0400
Organization: A noiseless patient Spider
Lines: 78
Message-ID: <k1lo7d$835$1@dont-email.me>
References: <563f186a-edb3-4311-ae48-3af7decfce2c@googlegroups.com> <k03d6p$2bt$1@dont-email.me> <6ac6c252-c370-4f74-b29d-ce5368019977@googlegroups.com> <502598d0$0$287$14726298@news.sunsite.dk> <a8pv38F9ouU1@mid.individual.net> <5028191b$0$290$14726298@news.sunsite.dk> <a8sr5sFropU1@mid.individual.net> <50317b03$0$281$14726298@news.sunsite.dk> <slrnk36phl.u9l.avl@gamma.logic.tuwien.ac.at> <503bfd0f$0$282$14726298@news.sunsite.dk> <CNT_r.5387$pd4.3890@newsfe21.iad> <k1h1sp$qdf$1@dont-email.me> <PPadnUGBC8NIuKHNnZ2dnUVZ_gudnZ2d@earthlink.com> <k1hgt4$vk5$1@dont-email.me> <BbednWMHAfFh5qHNnZ2dnUVZ_r-dnZ2d@earthlink.com> <k1ir2n$au0$1@dont-email.me> <3zc%r.5945$pd4.2658@newsfe21.iad> <k1jm6i$s5k$1@dont-email.me> <zSs%r.2724$Wh5.2588@newsfe14.iad>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 29 Aug 2012 18:49:17 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="ffb8f7085759b339c1002252b48331a4"; logging-data="8293"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/iTpJRjPyMHiCwJ4//PJeT"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:15.0) Gecko/20120824 Thunderbird/15.0
In-Reply-To: <zSs%r.2724$Wh5.2588@newsfe14.iad>
Cancel-Lock: sha1:AzP6T7J9iQ2f0pGtxuG/VstX9sA=
Xref: csiph.com comp.lang.java.programmer: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