1
$\begingroup$

I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. The additional property I'm looking for is that any two close input values should map to matrix indices that are far apart (in, say, the L1 norm). Thus, for a reasonably small set of integers $\{k,k+1,k+2,\ldots,k+d\} \subset [n^2]$, we should have that $\{h(k), h(k+1), h(k+2), \ldots, h(k+d)\}$ are a scattered set of matrix indices, none of which are close to each other.

I know that in the one dimensional version of this problem, where we have a length $n$ array instead of a matrix, we can get this scattering property using Fibonacci hashing: $$h(k) = \left\lfloor n \left(k\varphi \pmod{1}\right)\right\rfloor,$$

where $\varphi$ is the golden ratio, $\varphi=\tfrac{\sqrt5-1}{2}$. This is according to Knuth (The Art of Computer Programming Vol 3, 2nd edition, p. 514).

Might there be a way to extend Fibonacci hashing to a function with a similarly nice scattering property in two dimensions?

$\endgroup$

1 Answer 1

2
$\begingroup$

A random bijective function should satisfy this property with high probability for any specific set of indices. So, I suggest you use a random bijection on $[n^2]$.

If $n$ is very large, you can compute this random bijection efficiently using format-preserving encryption, or by using a Feistel network with arithmetic modulo $n$ instead of XOR (treat the cipher as working on $[n]^2$; then each block has a left half and a right half; and do at least 6 rounds of Feistel encryption using a pseudorandom function as the F function).

Another option is to construct a bijective function $[n]^2 \to [n]^2$ by separately applying Fibonacci hashing (or some similar one-dimensional solution) separately to the row index and the column index. That ensures that two close inputs will lead to two outputs that are distant. It won't be optimal but it might be good enough, if you prioritize guarantees and simplicity.

$\endgroup$
5
  • $\begingroup$ Further to that last sentence, a Feistel network would probably work very well here, using mod-$n$ arithmetic instead of exclusive or. $\endgroup$
    – Pseudonym
    Nov 15, 2021 at 7:40
  • $\begingroup$ As I noted, $n$ doesn't need to be a power of two if you use mod-$n$ arithmetic instead of exclusive or. $\endgroup$
    – Pseudonym
    Nov 15, 2021 at 14:00
  • $\begingroup$ I'm looking for something a bit stronger, I want a function that guarantees that close inputs are mapped to distant outputs (I recognize this description is lacking some rigor). $\endgroup$
    – RJL
    Nov 15, 2021 at 20:13
  • $\begingroup$ @Pseudonym oh good point, sorry that I didn't understand your original suggestion. I've added that to my answer. $\endgroup$
    – D.W.
    Nov 15, 2021 at 21:20
  • $\begingroup$ @RJL, ok, see the last paragraph of the edited answer. $\endgroup$
    – D.W.
    Nov 15, 2021 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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