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

where r1 and r2 are two preselected random numbers in
the range 0..255. This way, for any two distinct keys,
it becomes unlikely that they access the same set of table
locations (again, randomizing the hash function rather
than depending on the randomness of the key distribution.)

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.045 / U:0.100 seconds]
©2003-2011 Jasper Spaans. Advertise on this site