Re: Libgit2 on the Summer of Code

From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Date: May 27, 2010, 18:35 UTC
Message-ID: <20100527183534.GA10414@LK-Perkele-V2.elisa-laajakaista.fi>
In-Reply-To: <20100527180554.GM16470@spearce.org>

On Thu, May 27, 2010 at 11:05:54AM -0700, Shawn O. Pearce wrote:

Show 12 quoted lines

> Ilari Liusvaara <ilari.liusvaara@elisanet.fi> wrote:
> > * Where algorithm in git_revpool_table__hash() is from? Since it appears to
> > hash binary object IDs, wouldn't just simple sum/xor over words be sufficient
> > (all SHA-1 output bits are very nearly independent). Or do you need to be
> > compatible with some other implementation (doesn't appear so, because hash
> > is computed differently depending on endianess)?
> 
> If you need a hash value for a SHA-1, why not just cast the unsigned
> char* to unsigned int* and load the first int as the hash code?
> The output of SHA-1 is pretty evenly distributed, using the first
> few bytes as an int should yield a sufficient distribution throughout
> the hashtable.

Yeah, With pseudorandom function[*], all ways of reducing the output to n bits are at most as good as just taking first n bits. But if reducing output to [0, m), the best way (distribution-wise, not speed-wise) is to take remainder of the whole value divided by m...

[*] SHA-1 is not pseudorandom function, but for virtually all practical purposes it is.

-Ilari