Re: Question about tcp hash function tcp_hashfn()

[Evgeniy Polyakov <johnpol@2ka.mipt.ru>]

On Wed, May 31, 2006 at 12:29:55PM -0600, Brian F. G. Bidulock (bidulock@openss7.org) wrote:
> Evgeniy,
> 
> On Wed, 31 May 2006, Evgeniy Polyakov wrote:
> > > > >   Worse: he folded the jenkins algorith result with
> > > > > 
> > > > >    h ^= h >> 16;
> > > > >    h ^= h >> 8;
> > > > > 
> > > > >   Destroying the coverage of the function.
> > > > 
> > > > It was done to simulate socket code which uses the same folding.
> > > > Leaving 32bit space is just wrong, consider hash table size with that
> > > > index.
> > 
> > Btw, that probably requires some clarification.
> > Since hash table size is definitely less than returned hash value, so
> > higher bits are removed, for that case above folding is done both in
> > XOR hash and my test case. 
> > It is possible to just remove higher bits, but fairly ditributed parts
> > being xored produce still fairly distributed value.
> 
> > > > >    h ^= h >> 16;
> > > > >    h ^= h >> 8;
> 
> This does not remove high order bits in either function.
> Your comparison results are simply invalid with these two lines in place.

It is hash function, but not function which creates index inside hash
table. Index is created by removing high order bits with (& 0xffff).

I've present the new simple code and test results which show
that folded and not folded Jenkins hashes _do_ produce _exactly_ the
same distribution.

I think I've already said that fairly distributed values being xored
produce still fairly distributed value, so parts of 32bit fairly
distributed hash after being xored with each other still produce fairly
distributed 32bit space.

> --brian

-- 
	Evgeniy Polyakov
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/