Good Hash function with 2 integer for a special key
Go for N'ary numerical system, where N is the maximum possible value of the number in pair.
Like this:
hash(a, b) = a + b * N
then
a = hash(a, b) % N
b = hash(a, b) / N
This will guarantee that for every pair (a, b) there is its own unique hash(a, b). Same things happens to numbers in decimal: imagine all numbers from 0 (we write them as 00, 01, 02, ...) to 99 inclusive are your pairs ab. Then, hash(a, b) = a * 10 + b, and visa-versa, to obtain first digit you have to divide the number by 10, second - get it modulo 10.
Why can't we pick any N, maybe smaller than the maximum of a/b? The answer is: to avoid collision.
If you pick any number and it happens to be smaller than your maximum number, it is highly possible that same hash function will be provided by different pairs of numbers. For example, if you pick N = 10 for pairs: (10, 10) and (0, 11), both their hashes will be equal to 110, which is not good for you in this situation.
Chen Li
Updated on August 21, 2022Comments
-
Chen Li almost 2 years
I'm trying to determine a key for
map<double, double>
type. But the problem is that the key I want will be generated by a pair of 2 numbers. Are there any good functions which could generate such key for pairs like (0, 1), (2, 3), (4, 2) (0, 2), etc.-
pilotcam over 11 yearsSee this similar question: stackoverflow.com/questions/2634690/…
-
tenfour over 11 yearsWhy not just use
std::pair<int, int>
as your key type? -
andre over 11 yearsyeah, std::map<std::pair<int, int>, int> would be effective.
-
-
Chen Li over 11 yearsSo something like this: pair (1, 3) = hash(1, 3) = 1 + (3*181.312)
-
dreamzor over 11 yearsIf 181.312 == 181312 == 181 thousand plus 312 and that's your
N
then yes, this is right. :) -
Chen Li over 11 yearswhy do I need to keep track of N, can't I use any arbitrary number? But, I'll multiply every entry with the same number