Designing a hash function from a 3 integer tuple

Question

I have a set of keys $K$ where each key is a 3 tuple of integers (both negative and positive).

The keys are clustered, meaning that if $(i,j,k) \in K$ then there is a high likelihood of any of $(i\pm 1, j ,k), (i,j\pm 1,k), (i,j,k \pm 1)$ to also be a key, and conversely, if a 3 tuple is not a key then its surrounding 3 tuples are also unlikely to be keys.

The goal is to spread the keys uniformly on a range $[0, m)$ with $m$ large enough such that all keys can fit in the interval with some space to spare.

Which means close values of i,j,k must map to wildly different indices.

The actual problem that prompted this question is: I have a 3D grid and I am trying to compress its memory footprint in a computer because most of the grid is filled with empty values. For reasons too long to explain here, I have to design my own data structure and cannot rely on a prior implementation.

So basically I have a 3D array where some cells are empty, some have values. And I am trying to map that to a 1D array such that the total memory use of the 1D array is less than that of the 3D array.

For this I need a function $F(i, j, k)$ that maps onto the range $[0, m)$ for some hyper parameter $m$ almost uniformly.

Answer 1

You'll probably get really far with lots of hash functions. A quickly compute hash function might involve three large-ish primes $p, q, r$ and computing $$ h(i,j,k) = (ip + jq + kr) \bmod m.$$

If this is a practical hash, then I'll note that there is a fairly typical way of hashing tuples of individually-hashable items. For this, choose your favorite hash function $H$ on integers. Then to compute the hash of the tuple $(i, j, k)$, choose some fixed multiplier $m$ (often a binary representation of digits of an irrational number) and initial hash value X0 (like 0x123456), and then compute

define compute_hash(i, j, k):
    X0 = INITIAL_VALUE
    X1 = (H(i) XOR X0) * m
    X2 = (H(j) XOR X1) * m
    X3 = (H(k) XOR X2) * m
    return X3

That is, you iteratively compute hashes on the individual elements, xor them with a previous value, and then jumble the digits by multiplying by $m$. Then you quotient the result by whatever size of hash table you want in the end.

This is what's done (essentially) in CPython's tuple hashing, for example.