michael-
thanks for your note. if you read Knuth, you'll see that prime-sized hash
tables are not necessary if you use multiplicative hashing. and, you *do*
want multiplicative hashing with overflow because modulus hashing requires
a division operation in the hash function, which is more expensive than a
multiplication operation.
in fact, Knuth proves that multiplicative hashing is at least as good as,
and sometimes better than, modulus hashing on a prime-sized table.
read my report again, and you'll see a histogram that shows an almost
perfect bucket size histogram and an 87+% bucket utilization, all with a
simple multiplicative hash function. that's as good as it gets.
- Chuck Lever
-- corporate: <chuckl@netscape.com> personal: <chucklever@netscape.net> or <cel@monkey.org>The Linux Scalability project: http://www.citi.umich.edu/projects/linux-scalability/
- 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/