Re: Hash functions (was Re: 2.2.6_andrea2.bz2)

Peter Steiner (p.steiner@t-online.de)
Mon, 10 May 1999 10:49:13 +0200

>>Since my hash table size is 16384 and thus (32 - HASH_BITS) = 18 the
>>'normalized' hashfn is:
>>
>> i = ((k * 2654435761UL) >> 11) & bh_hash_mask
>> = ((k * 2654435761UL) << ((32 - HASH_BITS) - 11)) >> (32 - HASH_BITS)
>
>I don't think the above is correct. If you don't shift left for (32 -
>HASH_BITS) at least at once, then you may have still some bit set to 1 in
>the high part of `i'.

No, the shift *right* clears the bits.

Here's a 32 bit unsigned int:

xxxxxxxx.xxxxxxxx.xxxxxxxx.xxxxxxxx

<< (18 - 11)

xxxxxxxx.xxxxxxxx.xxxxxxxx.x0000000

>> 18

00000000.00000000.00xxxxxx.xxxxxxxx

The bh_hash_mask is

00000000.00000000.00111111.11111111

So it is not needed.

Peter

-- 
   _   x    ___
  / \_/_\_ /,--'  p.steiner@t-online.de (Peter Steiner)
  \/>'~~~~//
    \_____/   signature V0.2 alpha


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