Mailing-List: contact harmony-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: harmony-dev@incubator.apache.org
Received-SPF: pass (asf.osuosl.org: domain of alex.blewitt@gmail.com
 designates 64.233.182.190 as permitted sender)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=alefftYCNNOaC++ZmO2WG6M3CNLyKy/OP5rLztptSejgct+A9yUEgG0+kwVB9nUyZo9JV/tJWKfPnhnWCNAdExD3J+uZQH1gkrA0IWpTUdG0rrs4+8DsUpagdV4qdLbQZ8mfXEM2v4tTljlUvgQ2/EVFHwep0ov/0umXXxvnQ+Q=
Message-ID: <636fd28e0607261256x7db7550apf6ea0f1224382670@mail.gmail.com>
Date: Wed, 26 Jul 2006 20:56:34 +0100
From: "Alex Blewitt" <alex.blewitt@gmail.com>
To: harmony-dev@incubator.apache.org
Subject: Re: Re: [optimization] Algorithmic tricks
In-Reply-To: <834b3bd50607260726u73308b69v2efe2d54721dfb1a@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <ddda44ee0607250318l14042f9eu4b8be1ff520c94e@mail.gmail.com>
	 <44C64333.60503@apache.org>
	 <834b3bd50607260220o60761f85la8fc7d3f312e697a@mail.gmail.com>
	 <ddda44ee0607260403k1e933a73wd03593bb344e93c4@mail.gmail.com>
	 <834b3bd50607260726u73308b69v2efe2d54721dfb1a@mail.gmail.com>

On 26/07/06, Denis Kishenko <dkishenko@gmail.com> wrote:
> Frequently hash code is a sum of several other hashes. Such implementation
> kill hash idea, it's terrible.

I agree that simple addition is not a good thing. However, exclusive
or can work just as well, as can a simple multiplication of numbers by
primes.

> and many others... also I have found such "algorithms" =)>
>     private long* *token;
>
>      public int hashCode() {
>         return (int) token;
>     }

This isn't an incorrect hash function, and if there's only one token,
it doesn't really matter that much. Even if the token itself isn't
widely distributed, chances are the bottom few bits are going to be
distributed fairly evenly, and often it's the bottom part of a
hashcode that's considered rather than the top part. So, it's not
optimal, but shifting some bits around doesn't make that much
difference.

> The most of hashCode() functions are implemented in different ways. It's not
> problem, but it looks like scrappy, there is no single style. And finally we
> have class *org.appache.harmony.misc.HashCode *for this aim!

Interesting, but I wonder what the impact is of using an additional
class to calculate the hash from each time is going to be. Hopefully a
decent JIT will remove much of the problem, but bear in mind that the
hashCode may get called repeatedly during a single operation with a
collection (and in the case that it's already in the collection, may
be called by every other operation on that collection too. You might
find that even a simple (say) sort of a list would easily overwhelm
the nursery generation of a generational GC.

Of course, it's difficult to say without measuring it and knowing for sure :-)

> But only several classes are using it. I suggest integrate HashCode in
> all hashCode() implementations (about 200 files), I can do this. Anybody
> else can improve HashCode work.
>
> Any comments?

There are other approaches that could be used instead of this. For
example, the value of the hashCode could be cached in a private
variable and then invalidated when any setValue() methods are called.
One could even imagine a superclass performing this caching work:

public abstract class HashCode {
  private boolean valid = false;
  private int hash;
  public final int hashCode() {
    if (!valid) {
      hash = recalculateHashCode();
      valid = true;
    }
    return hash;
  }
  protected abstract int recalculateHash();
  protected void invalidate() { valid = false; }
}

Of course, you could use the HashCode object to calculate the hash value :-)

Such an approach won't work when the class hierarchy cannot be
changed, of course.

Lastly, an easier approach is to use a tool (such as Eclipse) to
generate the implementation of hashCode() automatically based on the
non-static, non-final variables of a class. This one sounds like (a)
the easiest, and (b) all-round better performant than any of the
above.

Alex.

---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org