Messages in this thread | | | Subject | Re: more on hash functions | Date | Thu, 15 Apr 1999 08:44:01 -0400 | From | Horst von Brand <> |
| |
"Paul F. Dietz" <dietz@interaccess.com> said: > 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.
Take a longer random table (12, i.e. 16 bits in this case), and shift _down_. -- Dr. Horst H. von Brand mailto:vonbrand@inf.utfsm.cl Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
- 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/
| |