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.021 / U:0.140 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site