Take the 2-minute tour ×

I'm trying to determine a key for map 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.

share|improve this question
See this similar question: stackoverflow.com/questions/2634690/… –  pilotcam Oct 6 '12 at 23:10
Why not just use std::pair<int, int> as your key type? –  tenfour Oct 6 '12 at 23:52
yeah, std::map<std::pair<int, int>, int> would be effective. –  andre Oct 7 '12 at 0:04
add comment

2 Answers

up vote 3 down vote accepted

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


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 (11, 0), both their hashes will be equal to 110, which is not good for you in this situation.

share|improve this answer
So something like this: pair (1, 3) = hash(1, 3) = 1 + (3*181.312) –  Chen Li Oct 6 '12 at 23:35
If 181.312 == 181312 == 181 thousand plus 312 and that's your N then yes, this is right. :) –  dreamzor Oct 6 '12 at 23:36
why 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 –  Chen Li Oct 6 '12 at 23:41
@ChenLi updated my post, added info about collisions. –  dreamzor Oct 7 '12 at 16:24
add comment

You should ideally have a KeyValuePair<int, int> as your key. I don't think writing more code than that can be helpful. If you cant have that for some reason, then hashing the pair to give a single key depends on what you're trying to achieve. If hashes are meant for hash structures like Dictionary, then you have to balance collision rate and speed of hashing. To have a perfect hash without collision at all it will be more time consuming. Similarly the fastest hashing algorithm will have more collisions relatively. Finding the perfect balance is the key here. Also you should take into consideration how large your effective hash can be and if hashed output should be reversible to give you back the original inputs. Typically priority should be given to speed up pairing/hashing/mapping than minimizing collision probability (a good hash algorithm will have less collision chances). To have perfect hashes you can see this thread for a plethora of options..

share|improve this answer
add comment

Your Answer


