Formula for Unique Hash from Integer Pair

问题:

I think I can use Cantor's to create a unique hash n = ((x + y)*(x + y) + x - y)/2...

but can I reverse this hash? And if not, can someone provide a similar formula pair for a reversible hash?

Thanks.

回答1:

if x and y and n are all the same data types.

n = ((x + y)*(x + y) + x - y)/2...

when x and y are near the datatype::max n will overflow and you will lose information and not be able to recover x and y.

If on the other hand if x and y are always within a range let say 0-FOO

n = Foo * x + y 

can be a recoverable hash provided again n has not overflown

   n % Foo

will give you y. Once y is known (n-y)/Foo will give you x

回答2:

Here's a unique, reversible, and completely impractical hash for two integers:

for two numbers x and y, return the product of the xth and yth prime numbers. This is unique and reversible if you assume the order does not matter. If they do, then you can add a character denoting which of the two prime factors of your "hash" is x or y.

Note that your hash space is larger than your input space. Oh well. That's what you get for trying to store more than one bit in a bit.

回答3:

You should specify if you have control over the upper bound of inputs, and if so what size your inputs are, what size your output should be, if inputs and output are signed or not etc (and of course if function should be reversible or not). A good answer would depend on all that. In this link you find a good solution to encode two positive numbers uniquely and decode them back.