Search code examples
hashdouble-hashing

Determing the Double Hashing functions given key -> hash location values


Given a bunch of keys and their hashed values, how can I determine the double hash function?

UPDATE

I think h(x) = k % 13 + 1


Solution

  • h(x) = (x+1) % 13
    

    what you had, but you want the modulo after adding one so the resultant values are range [0,12] not [1,13] ... but you had it right.

    the best I could come up with for r(x) was:

    r(x) = (x+6) % 19
    

    this really makes no sense to me why it would be this, but the way that I came to this was that the modulo divisor must have increased the shift by 6 because of the values given (38 and 101 have a difference of 1 for modulo 13 and they were six spaces apart). I feel like the modulo 19 really makes this break, so while this seems to fit, I would seek a better answer, but that's what I came up with and I feel like I kind of had a method over guess and check.

    Best of luck, feel free to drop comments if you have any questions about this.