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