Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer
    
You are right 'hash' may not be the correct term. But I'm leaving it in the question to not have 'dangling' answers. –  Jan Doggen Nov 5 '13 at 10:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.