lkml.org 
[lkml]   [1999]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: more on hash functions
Chuck Lever wrote:

> #define FIRSTBYTE(x) (0xff & (x))
> #define SECNDBYTE(x) (0xff & ((x)>>8))
> #define THIRDBYTE(x) (0xff & ((x)>>16))
>
> #define hashfn(key) ( (rand1[FIRSTBYTE(key)] << 4) ^ \
> (rand2[SECNDBYTE(key)] << 2) ^ \
> (rand1[THIRDBYTE(key)]) )
>
> to generate a 12-bit hash table index. this way i don't have to mask off
> extra bits as the final step, and i can use daintily sized random tables.


This is also clearly bad. Suppose you're hashing keys that
have a common third byte? The low two bits of your hash
values will be constant.

You really have to make every bit of the result depend on
every bit in the key.

Paul

-
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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.077 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site