A hash function for a 2D hash table with a scattering property?

Question

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?

Answer 1

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.