Hashing Algorithms – Monotonically Increasing Integer Hash Function

algorithmshashingsorting

I'm looking for a HashFunction(X,Y: Integer): Integer that is monotonically increasing on X, then Y.

So:
HashFunction(x1,y1) > HashFunction(x2,y2) if x1>x2
HashFunction(x,y1) > HashFunction(x,y2) if y1>y2

Does such an animal exist?

Background: This question arises from a comment on
How to create single integer index value based on two integers where first is unlimited?

Best Answer

Without trying to go into proofs, I'd say that such a beast does not exist for generic integers. Your problem would ultimately boil down to finding a hash function H with x>y → H(x) > H(y); with the constraint that the output of H is a finite set, and assuming that x∊ℕ (or in another set S with |S|>|image(H)|), there would necessarily be x₁>x₂∊ℕ with H(x₁)≤H(x₂).

If, however, you have both variables from a finite set, e.g. N-bit integer representations r(x). you could trivially define H(x₁,x₂)=r(x₁)||r(x₂) and satisfy your requirement.

Related Topic