Looking for monotonically increasing (integer) hash function

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?

• it approximately possible, example, for one argument hash function `HashFunction(x) = 1000000*x + hash(x)` where `hash` is some usual hashing function which maps `x` into 0,...,1000000 set
– Qbik
Feb 17, 2015 at 9:25

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.

If `Integer` is bounded, trivially impossible because of the pigeonhole principle. If it isn't, trivially impossible because `Hash(2,0) - Hash(1,0)` is finite, and yet an infinite number of hash values `Hash(1,y)` must lie in between.

Are you looking for coordinate hashing? The normal equation is:

hash = y * width + x (in your case it would probably be x * height + y)

So if your hash size is a signed 32 bits then sqrt(2,147,483,647) would give the width value, in this case 46340. This defines are min as (-46340, -46340). The max would be (46340, 46340).

-46340 * 46340 + -46340 = -2,147,441,940, and minimum signed int in 32 bits is -2,147,483,648 46340 * 46340 + 46340 = 2,147,441,940 and maximum signed int in 32 bits is 2147483648

For large ranges of x and y you can usually just use a 64 bit.

If you know bitwise operators you can just assign low and high bits to x and y. So in a 64-bit number you'll store the x in the top 32 and y in the lower 32. This will generate a hash that follows your rules.

A few points suggest that either "hash function" isn't the right term for what you want, or that what you want does not exist.

First, a function cannot be strictly increasing unless it is 1-1, and typically by "hash" we mean getting a result that is smaller than the input (usually by many orders of magnitude). In this context the most you could ask for is a weakly increasing function, e.g retain a high-order byte or something similar.

Second, the linked Question suggests to me that what is wanted is to make the results uniformly distributed (at least roughly) while preserving order (monotonicity). It's possible to achieve this for a specific data set (sort and enumerate), but defining a master function to do this for arbitrary input data ("generic integers" as Nicos puts it) is impossible.

Third, a monotone function would be useless as a cryptographic hash function because monotone functions are easy to invert (defeating the purpose of making it difficult to generate a message having a given hash).

• You are right 'hash' may not be the correct term. But I'm leaving it in the question to not have 'dangling' answers. Nov 5, 2013 at 10:08

Have a look at Morton code, also called z-curve. it does exactly what you are (were) looking for. The inverse is not monotonous though.

• Please give a construction that works when `x` is unlimited in size, which is part of the OP's requirements. Nov 28, 2023 at 11:09