[lkml]   [1999]   [Apr]   [15]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: more on hash functions
    On Wed, 14 Apr 1999, Paul F. Dietz wrote:
    > > my random tables were constructed such that, for a 256 entry random table,
    > > the table contained unique random values from 0 to 255. making these 16
    > > bit numbers would only add some hash tablesize flexibility, but i don't
    > > believe it would help the hash function generate better randomness.
    > If the hash table itself has more than 256 entries, then it
    > would certainly produce better randomness. The small random
    > table entries would mean you are only hashing to the low
    > end of the hash table.

    i was using the random tables to mix up the bits in each byte, like so:

    unsigned char rand1[256] = { ... };
    unsigned char rand2[256] = { ... };

    #define FIRSTBYTE(x) (0xff & (x))
    #define SECNDBYTE(x) (0xff & ((x)>>8))
    #define THIRDBYTE(x) (0xff & ((x)>>16))

    #define hashfn(key) ( (rand1[FIRSTBYTE(key)] << 4) ^ \
    (rand2[SECNDBYTE(key)] << 2) ^ \
    (rand1[THIRDBYTE(key)]) )

    to generate a 12-bit hash table index. this way i don't have to mask off
    extra bits as the final step, and i can use daintily sized random tables.

    > In Linux x86, the size of the hash table is 2048 (1 << PAGE_HASH_BITS),
    > so your hash function, as implemented, would be very bad.

    the page cache hash function, btw, already works very well, and i don't
    believe replacing it with any other kind of function will help. the only
    hash function we should be concerned with improving is the buffer cache
    hash function: see fs/buffer.c, ll. 425-30.

    i re-read Knuth over dinner last night. unfortunately, he is discussing
    hashes where you store data elements right in the hash table, and can then
    easily do linear probing [i heard that, you in the second row]. i can't
    think of a good way to apply his double hashing algorithm (algorithm D, p.
    528) or Brent's variation (p. 532) to help improve the hash function
    without using a multiplicative hash.

    - Chuck Lever
    corporate: <>
    personal: <> or <>

    The Linux Scalability project:

    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 13:51    [W:0.022 / U:6.768 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site