Re: more on hash functions

Horst von Brand (vonbrand@inf.utfsm.cl)
Thu, 15 Apr 1999 08:33:51 -0400

"Paul F. Dietz" <dietz@interaccess.com> said:
> Iain McClatchie wrote:
> > Point 2
> > -------
> > Paul, you seem to suggest using separate random tables for each
> > of the key load lookups. I can't see why that would be necessary.
> > Why is it that one table will not do? Are byte permutations of
> > the keys really frequent?

> I don't know if they are frequent, so I can't say that
> a single table would necessarily be good.

If you worry about that, shift (or roll) the table entries you get by a few
bits each time.

> If you do reuse tables, it would probably be a good idea to
> add rather than xor the keys, so that table[i]+table[i] is
> less likely to equal table[j]+table[j] mod the hash table
> size. You might also consider this:
>
> hash = (table[byte0] + table[(byte1+r1) & 0xff] +
> table[(byte2+r2) & 0xff]) mod PAGE_HASH_SIZE

hash = (table[byte0] ^ (table[byte1] >> 3) ^ (table[byte2] >> 6)
& ~(PAGE_HASH_SIZE - 1)

This gives you in essence bigger tables at probably less cost

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