Messages in this thread | | | Date | Mon, 12 Apr 1999 17:28:49 -0500 | From | "Paul F. Dietz" <> | Subject | Re: more on hash functions |
| |
Chuck Lever wrote:
> actually, this was my first implementation choice. i found that the hash > function didn't work very well with 3 8-bit tables -- it had poor > bucket size distribution characteristics. how does one combine 3 8-bit > values appropriately to get, say, a 14-bit table index?
[...]
> however, i think we're making different assumptions about what goes in the > random table. i assumed they were random numbers from 0 to table_size, > whereas some of your comments indicate you assume that the random table is > filled with random numbers from 0 to 2^16.
Whoa! The size of the *random* tables is not related to the size of the *hash* table. Why should it be? The sizes of the random tables depend on the number of bits in each of the key fragments.
As I said in the original message, the values stored in the random tables are in the range 0..PAGE_HASH_SIZE-1. If you've been picking only smaller values, no wonder the hash has been performing poorly!
You were earlier perfectly correct that this kind of scheme has a large cache footprint. On a modern processor with a fast multiply, it would not be competitive.
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/
| |